World's most popular travel blog for travel bloggers.

[Solved]: Why can't you write the 2-paths problem as a max-flow problem?

, , No Comments
Problem Detail: 

This is a follow-up question to this. Consider the 2-paths problem:

Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and $P_2=(s_2,\dots,t_2)$ such that $P_1$ and $P_2$ are vertex-disjoint?

This problem has been shown to be NP-complete (references here). This struck me as unusual, because there seems to be a natural way to formulate this as a max flow problem:

  • Add new vertices $s$ and $t$ to $D$.
  • Add arcs $(s,s_1),(s,s_2),(t_1,t),(t_2,t)$.
  • Let all vertices have capacity one (besides $s$ and $t$).

It seems to me that the max $s-t$ flow of this new graph (call it $D'$) should be two iff $D$ has those desired paths $P_1$ and $P_2$. Surely there must be some mistake here, because this seems to imply that an NP-complete problem can be solved in polytime. Where is the mistake?

Asked By : Austin Buchanan

Answered By : Austin Buchanan

The proposed construction does find two vertex disjoint paths from s to t (if they exist). HOWEVER, the paths might be $P_1=(s_1,…,t_2)$ and $P_2=(s_2,…,t_1)$, which is not what we want.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21574

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback