Hey Guys I am aware that we can find if there exists a hamilton path in a directed graph in O(V+E) time using topological sorting.
I was wondering if hamilton cycles, euler paths and euler cycles can also be found in O(V+E) time. If so, how do we find them? Also in case of undirected graphs, how do we go about getting these 4 properties from a graph in O(V+E) time?
Thanks in advance!
See the following theorems of a lecture “Round Trips” of our blockcourse “Algorithmic Graph Theory” by Joachim Spoerhase and Alexander Wolff.
Theorem. Let $G = (V,E)$ be an undirected and connected graph.
(i) We can test in $O(E)$ time, if $G$ is Eulerian.
(ii) If $G$ is Eulerian, we can find in $O(E)$ time an Eulerian cycle.
A problem to find an Eulerian path can be reduced to a problem to find an Eulerian cycle as follows. If we have a graph $G$ for which exists an Eulerian path then $G$ has exactly two vertices of odd degree. Add an edge $e$ between these vertices, find an Eulerian cycle on $G+e$ and then remove $e$ from the cycle, obtaining an Eulerian path in $G$.
Theorem. Let $G = (V,E)$ be an directed and weakly connected graph.
(i) We can test in $O(E)$ time, if $G$ is Eulerian.
(ii) If $G$ is Eulerian, we can compute in $O(E)$ time an Eulerian cycle.
Theorem. [Karp, 1972] (Un)directed Hamiltonian cycle and path are NP-hard.