3
$\begingroup$

Given a directed acyclic graph (DAG), is there a known polynomial time algorithm for enumerating all paths between a source and a sink node?

I can understand that there may be exponential number of paths between the source and the sink, so a polytime algorithm for enumerating them is difficult.

In that case what is the proof that enumerating all paths between source and sink in a DAG is NP-hard?

$\endgroup$
4
  • $\begingroup$ An NP-complete problem must be a decision problem. Enumerating all the paths in a directed graph is not a decision problem. $\endgroup$ – Kyle Jones Jan 8 '18 at 22:00
  • $\begingroup$ Agreed, but we can easily formulate this problem as deciding if there are k paths between source and sink to make it a decision problem. $\endgroup$ – neo4k Jan 8 '18 at 22:20
  • $\begingroup$ We can't answer your question until you do just that, turn the function problem into a particular decision problem. $\endgroup$ – Kyle Jones Jan 9 '18 at 0:56
  • $\begingroup$ Done! Thanks for your comment. $\endgroup$ – neo4k Jan 9 '18 at 1:25
1
$\begingroup$

The number of paths in a DAG may be exponential, but it can be represented in polynomial space.

In fact, it is easy to calculate: Just run through all of the vertices in topologically-sorted order and for each vertex compute how many paths end there. This is $1$ (for the single-vertex path) plus the sum of the number of paths that end at each of its predecessors. So counting them is in P.

If there are many different paths, you cannot hope to enumerate them all in polynomial time. You can enumerate them in linear space (just enumerate all subsets of vertices and check whether each of them form a path). Or you can number the paths sequentially and convert an arbitrary sequence number to a path in something like $O(n\log n)$ time.

$\endgroup$
8
  • $\begingroup$ Thanks! I understand this and I should rather change my question. Is the problem of enumerating all paths between source and sink NP-hard, and if so, what is the proof? $\endgroup$ – neo4k Jan 9 '18 at 3:13
  • $\begingroup$ @Ain: "NP-hard" applies only to decision problems. You can't even ask that unless you change the question to be about some decision problem. $\endgroup$ – hmakholm left over Monica Jan 9 '18 at 3:25
  • $\begingroup$ That is not true, I believe. Read definition here en.wikipedia.org/wiki/NP-hardness $\endgroup$ – neo4k Jan 9 '18 at 3:26
  • $\begingroup$ @Ain: See the first three words in the "Definition" section of the article you link to. $\endgroup$ – hmakholm left over Monica Jan 9 '18 at 3:27
  • $\begingroup$ And you can read the last sentence. "Another definition is to require that there is a polynomial-time reduction from an NP-complete problem G to H. As any problem L in NP reduces in polynomial time to G, L reduces in turn to H in polynomial time so this new definition implies the previous one. Awkwardly, it does not restrict the class NP-hard to decision problems, for instance it also includes search problems, or optimization problems." $\endgroup$ – neo4k Jan 9 '18 at 3:29

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.