6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How do you enforce the flow to only consist of two disjoint paths? Even with capacity 1 that doesn't mean the flow won't be split into a fractional amount. $\endgroup$ – Nicholas Mancuso Feb 12 '14 at 18:41
  • 1
    $\begingroup$ @NicholasMancuso I don't think that is the issue. If there is a fractional flow of 2, there should be an integral flow of 2 (by total unimodularity). Anyways, Ford-Fulkerson finds an integral flow when the data is integral. $\endgroup$ – Austin Buchanan Feb 12 '14 at 19:06
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Raphael The system has blocked me from accepting it for the next 15 hours. I think there is a 2-day wait period. $\endgroup$ – Austin Buchanan Feb 14 '14 at 3:27
  • 1
    $\begingroup$ @AustinBuchanan It should be possible now :-) $\endgroup$ – Juho Feb 16 '14 at 21:02

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.