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?