0
$\begingroup$

I saw on Wikipediathat Hierholzer's algorithm has a time complexity of O(E), but won't the dfs used in this algorithm would cause the total time complexity to be O(V+E) instead of only O(E). Assuming we performed the dfs on an Adjacency list. Assume the graph is a connected graph with only one component.

Thanks for the help.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I'm going to assume that you have a reasonable representation of the graph (for example adjacency lists with vertices indexed by small integers).

The only interesting case is $E \in o(|V|)$ (otherwise you already have $O(|V|+|E|) = O(|E|)$).

Then there are at most $O(|E|)$ non isolated vertices. You can find the set $S$ of these vertices (and hence construct the subgraph induced by $S$) in time $O(|E|)$ by simply creating an array (of size at most $2|E|$) containing all endpoints of the edges in $E$, sorting them (in linear time), and dropping the duplicates (again, in linear time).

Then you can apply the algorithm on the remaining subgraph with has $\Theta(|E|)$ vertices and $|E|$ edges (besides, if the number of remaining vertices is larger than $|E|+1$, then the graph has at least two connected components containing at least one edge each, hence no Eulerian path exists).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Are saying that if an Eulerian path exists then E > V hence O(V+E) = O(E) is this assumption right? Lets assume the graph is a connected graph with only one component $\endgroup$
    – African_king
    Feb 10, 2022 at 18:54
  • 1
    $\begingroup$ No, there are graphs with $|E|=o(|V|)$ that admit an Eulerian path. However, these graphs have isolated vertices. Once you remove then then you are left with $V \le 2|E|$, i.e., $|E| \ge |V|/2$ and hence $O(|V|+|E|)=O(|E|)$. $\endgroup$
    – Steven
    Feb 10, 2022 at 18:58
  • $\begingroup$ I See that makes sense. Thanks $\endgroup$
    – African_king
    Feb 10, 2022 at 19:00
  • $\begingroup$ I see that you added "Assume the graph is a connected graph with only one component". In this case you clearly have $|E| \ge |V|-1$ (otherwise the graph won't be connected) and hence $O(|V|+|E|) = O(|E|)$. $\endgroup$
    – Steven
    Feb 10, 2022 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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