Timeline for Finding all paths on undirected graph
Current License: CC BY-SA 2.5
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2019 at 23:45 | comment | added | Jérôme JEAN-CHARLES | @Boris Correct if you need to output each paths, but if you need only to count them then the argument is not enough: counting this number is not known to be polynomial. Yet it is often confused with counting the number of walks ( allows the resuse of vertex 1 or more times) which is in P ( use powers of the incidence matrix of the graph). | |
| May 23, 2019 at 18:56 | review | Suggested edits | |||
| May 23, 2019 at 19:25 | |||||
| Jun 26, 2013 at 19:26 | history | protected | CommunityBot | ||
| Apr 27, 2012 at 5:53 | answer | added | Ernest | timeline score: 4 | |
| Apr 26, 2012 at 21:33 | answer | added | Paul Wollan | timeline score: 7 | |
| Apr 19, 2012 at 16:42 | comment | added | Tony Huynh | I don't think polynomial in the number of paths is possible. Consider the disjoint union of two large cliques with $u$ in one clique and $v$ in the other. Then there are a constant number of $u-v$ paths (zero of them), but we have to at least look at the entire graph to determine so. | |
| Nov 10, 2010 at 22:20 | comment | added | Warren Schudy | Computing the number of such paths appears to be NP-hard and is likely #P-complete, so there's no very little hope of even computing the number of such paths in polynomial time. | |
| Mar 20, 2010 at 3:53 | comment | added | Suresh Venkat | in fact my soln included the backtracking that rgrig mentions. I should have been more specific. as for the other problem with the clique example, that's a good point. | |
| Mar 19, 2010 at 17:52 | comment | added | rgrig | MRA, that's a good point. You could do the backtracking and then from each node try BFS/DFS to see if the target is still reachable. If not, backtrack. If there are $p$ paths from $s$ to $t$ in a graph with $n$ nodes and $m$ edges this works in $O(np(n+m))$, which is worse than $O(np)$. I don't know how to do better. | |
| Mar 19, 2010 at 16:53 | comment | added | MRA | @rgig: Ok, I see. But wouldn't you then loose the "time linear in the total length of all the output paths" property Suresh aims for? Consider the following counterexample: The graph consists of $n+1$ nodes, more precisely, a $K_n$ containing the start node, and the single target node which is only adjacent to the start node. Then the number (and length) of all output paths is 1, while the backtracking has to search through all the exponentially many paths within the $K_n$. | |
| Mar 19, 2010 at 15:20 | comment | added | rgrig | @MRA, you can modify DFS to do what Suresh says very easily. I guess you can call the resulting algorithm 'backtracking'. | |
| Mar 19, 2010 at 12:50 | comment | added | MRA | @Suresh: Are you sure a DFS will find all paths? Asssume two $K_n$ connected by a single bridge edge, with the source node in one $K_n$ and the target node in the other. DFS will traverse the bride edge exactly once, while there is certainly a much larger number of distinct paths from source to target that are crossing this edge. | |
| Mar 19, 2010 at 12:44 | answer | added | MRA | timeline score: -1 | |
| Mar 19, 2010 at 1:42 | answer | added | Joseph Malkevitch | timeline score: 2 | |
| Mar 18, 2010 at 18:31 | answer | added | rgrig | timeline score: 8 | |
| Mar 18, 2010 at 17:31 | comment | added | Suresh Venkat | @mikael that's not a problem. start at the first node, and do a DFS. Each time you reach the second node, spit out the current path, and note which edge on the stack got you there. So overall the time taken is linear in the total length of all the paths, which is at most n times the number of paths. | |
| Mar 18, 2010 at 16:49 | comment | added | Mikael Vejdemo-Johansson | @Boris Is it possible, though, to get some nicer estimates on the complexity of enumerating all paths in terms of how many such paths there are? It won't be polynomial in the number of nodes of the graph, but the enumeration might be polynomial in the number of paths it outputs, or something like that? Or is there an obstruction to such an algorithm as well? | |
| Mar 18, 2010 at 15:34 | comment | added | Boris Bukh | It cannot be done in polynomial time: in the complete graph $K_n$ there are approximately $n!$ paths between every pair of vertices. Just outputing all these paths would take longer than a polynomial in n. | |
| Mar 18, 2010 at 15:31 | history | asked | JesseStimpson | CC BY-SA 2.5 |