7
$\begingroup$

Let's say we have given simple undirected graph $G$ having $N$ nodes and $M$ bidirectional edges. For given $x$ and $y$ we want to check if in the graph there is only one simple path between them.

What I was thinking for, is that we should find all the cycles in the graph and run bfs from $x$ to $y$, if the path doesn't move through the vertices that are in some cycle, there is only one path, and otherwise there are more.

Is there some other way to check this?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Possible duplicate cs.stackexchange.com/questions/3078/… $\endgroup$
    – Eugene
    Dec 22, 2017 at 16:29
  • $\begingroup$ It is similar question, but my question only asks to check if there is only one or more. $\endgroup$
    – someone12321
    Dec 22, 2017 at 16:39
  • $\begingroup$ @Eugene Very similar, but I think harder. $\endgroup$
    – Raphael ♦
    Dec 22, 2017 at 17:25

4 Answers 4

Reset to default
5
$\begingroup$

Raphael's suggestion to use 2-shortest path is correct but more complex than necessary.

Your approach is unfeasible, the number of cycles is factorial in the size of input.

Here's a sketch of a solution in time $O(|V|+|E|)$.

Find a path $p_1, \dots p_n$ from $x$ to $y$ in $O(|V|+|E|)$. If no such path exists, answer $\textsf{NO}$. Otherwise, mark all the nodes in the path. That path is indeed unique if and only if no node in that path reaches a node that comes after it. Starting from the first node of the path $p_1$, pick a random edge going out from $p_1$ other than the one that connects it to $p_2$ and start a DFS from there. If you reach a marked node, answer $\textsf{NO}$, if you never reach a marked node, cut that branch from the graph and pick another random outgoing edge. Continue in a similar fashion until all outgoing edges are exhausted, then start again with the following node until you reach $p_n$. If you finish the procedure without ever answering $\textsf{NO}$, answer $\textsf{YES}$. The entire procedure has the cost of a DFS, $O(|V|+|E|)$, therefore the overall time is $O(|V|+|E|)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ When you say "cut that branch from the graph" do you mean remove all edges you have traversed? Which wouldn't really be done all at once at the end of the DFS; it would be done on the way back "up" in DFS itself. Right? I made sense of it with a little thought but it could possibly be explained more clearly. $\endgroup$
    – Wildcard
    Dec 22, 2017 at 22:31
  • 1
    $\begingroup$ Which of Raphael's two answers are you referring to? Oh, probably the one that was posted before your answer, rather than the one posted after. :-) Edited to clarify. $\endgroup$
    – David Richerby
    Dec 23, 2017 at 2:02
  • $\begingroup$ @Wildcard: Yeah, you wouldn't actually "cut" anything, I wrote it like that because I felt it gave the idea of what I was trying to do, but in an actual implementation I assume you would just somehow mark those nodes as visited in the DFS itself. $\endgroup$
    – quicksort
    Dec 23, 2017 at 5:32
2
$\begingroup$

Run a k-shortest path algorithm with $k=2$ and observe whether it fails.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Isn't that overkill? Dynamic programming solves it in O(|V|+|E|) $\endgroup$
    – quicksort
    Dec 22, 2017 at 17:26
  • $\begingroup$ @quicksort Ahh, I extended the question to be about shortest paths in my head, sorry. :D Please add another answer! $\endgroup$
    – Raphael ♦
    Dec 22, 2017 at 17:29
2
$\begingroup$

If there exist a path from source $x$ to some cycle it doesn't always contradict the existence of a single simple path. Take a look at the following example: enter image description here

Here there is a cycle that can be reached from $x$ and $y$. This problem can be solved in $O(|V| + |E|)$.

You can run BFS to find shortest distance from $x$ to every vertex on the graph and the same from $y$. One node belong to the shortest path from $x$ to $y$ if and only if $$distance(x,u) + distance(u,y) = distance(x,y)$$ Now, to check if there is a single path, check that valid nodes in shortest path at every distance occurs at most once. This is, if there are at least two nodes that belong to a shortest path from $x$ to $y$ with the same distance to $x$ then, there are at least two shortest path, otherwise it is unique. You can do all post-processing in $O(|V|)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Look, we don't want to have if there are two same distance paths, but only to check if there are two different paths $\endgroup$
    – someone12321
    Dec 22, 2017 at 18:00
  • $\begingroup$ I get it, I don't know why I thought that both path are of minimal length. Anyway, I hope you find useful the example above, it still holds. $\endgroup$
    – Marcelo Fornet
    Dec 22, 2017 at 18:08
0
$\begingroup$

Perform a depth-first search starting in $x$ and annotate edges according to whether they are tree, back, or cross edges (cf. e.g. here).

There is more than one simple path from $x$ to $y$ if and only if there is (at least) one node on the path from $x$ to $y$ using only tree edges (i.e. the path found by DFS) that is incident to a back or cross edge.

Improve this answer
$\endgroup$

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.