0
$\begingroup$

How are these two problems different?

I. Find all paths between a source vertex and destination vertex.
II. Find all paths between a source vertex and all vertices in the graph.

Both of these problems are NP-hard. We would naturally assume (II.) takes longer.

However, I believe we can use a flavor of (II.) to solve (I.) in relatively equal amounts of time.
In other words, can we reduce (I.) to (II.) doing the following:

We are asked to find all paths from a source to a destination vertex. We can trivially use (II.) to solve this problem by augmenting the graph in linear time. We remove all vertices that are NOT decedents of the source and NOT ancestors of the destination in O(|E| + |V|). Then we run our algorithm for (II.) on the augmented graph. Since our graph has been refined down the only the relevant vertices, the returned value for (II.) and (I.) are the same and have been computed in nearly the same amount of time. Am I correct in my thinking?

Why is this relevant? Let's say you have asked to compute every possible path between one source and multiple destinations[0...n]. How do we reduce pointlessly re-computing things? For example, destination[1] could be an ancestor of destination[0]. A naive algorithm would re-compute every path possible path to destination[1] and destination[0]. A smarter solution would use the results from destination[1] to compute destination[0] faster. That solution essentially uses dynamic programming based on the following property:

Property: If you find every possible path from some source to some destination, we would also would have every possible path from the source to any of the vertices that are ancestors of the target.

My solution is using the reduction from before. My solution does not need to use the above property. I believe my solution would run as efficiently as a dynamic programming solution, but be simpler to implement. Still NP-hard of course. Does this sound reasonable?

$\endgroup$
2
  • $\begingroup$ Why do you think these problems are NP-hard? I stopped reading there, as that does not seem correct. $\endgroup$
    – D.W.
    Commented Apr 30, 2020 at 7:48
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Apr 30, 2020 at 7:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.