# Is the enumeration of all paths between source and sink in a DAG NP-hard?

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?

• An NP-complete problem must be a decision problem. Enumerating all the paths in a directed graph is not a decision problem. – Kyle Jones Jan 8 '18 at 22:00
• 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. – neo4k Jan 8 '18 at 22:20
• We can't answer your question until you do just that, turn the function problem into a particular decision problem. – Kyle Jones Jan 9 '18 at 0:56
• Done! Thanks for your comment. – neo4k Jan 9 '18 at 1:25

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.