# Why can't you write the 2-paths problem as a max-flow problem?

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?

• 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. – Nicholas Mancuso Feb 12 '14 at 18:41
• @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. – Austin Buchanan Feb 12 '14 at 19:06

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.