CODEWITHSUNDEEP
graph-theory
salvador p
salvador p

Reputation: 3025

How can I determine if a directed graph has a path that consumes all edges starting from a certain node?

There's no restrictions that you have to cross each edge only once, or each vertex.

Is there some property of the graph that is necessary and sufficient for the existence of such a path (like the degrees of nodes for the existence of the Eulerian path), or some known algorithm that proves there is or there isn't one (perhaps finding the minimum path through all edges from the starting one)?

I have considered several possibilities, the strongest of which is collapsing strongly connected components into single supernodes, then check if the resulting graph is simply a "linked list"-like graph covering all edges (which is simple, just walking from the starting node/supernode always talking a single edge from the current node, counting the outgoing edge (and any internal edges if it is a supernode) as visited and when you reach a leaf node see if all edges were counted). In this solution it is important to conserve all the original edges even if they become redundant (for example, if after collapsing the connected component A, B, C into supernode S, edges from F to A, F to B, F to C must all be conserved even though they point to the same supernode S in the simplified graph). Sorry if it's not expressed correctly, I will be trying to implement this solution while I wait for answers.

Is there an easier way? Or some better algorithm to handle cycles/connected components? Because when the graph is acyclic it seems very easy to solve.

Upvotes: 2

Views: 1283

Answers (1)

nbrooks
nbrooks

Reputation: 18233

If the graph is strongly-connected, then you can get to every node from every other node. Since you are allowed to reuse edges in this path, it must be the case that you can use every edge. Take some edge, e. e leads to a node v, from which you can subsequently get to every other vertex and, therefore, get to every other edge. From those, you can get back to v. Repeat as needed.

Thus to answer the question Is there some property of the graph that guarantees the existence of such a path... I would say yes, if the graph is strongly-connected. (Note, this isn't required for such a path though—example, in the case of a single one-directional path with no branches). But that seems to be the single edge-case (that I can think of).

Testing for strong-connectedness can be done by the brute-force, check-all method trivially. You can also adapt the max-flow, min-cut algorithm for this as well I believe.

Upvotes: 2

Related Questions