1
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ Topological sorting can only find a Hamiltonian path in a directed acyclic graph. For directed graphs in general, determining whether or not a Hamiltonian path exists is NP-complete. $\endgroup$ – Misha Lavrov Nov 15 '17 at 21:12
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.