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?

  • $\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$ Commented Feb 12, 2014 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$ Commented Feb 12, 2014 at 19:06

1 Answer 1


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.