World's most popular travel blog for travel bloggers.

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

, ,
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\$.
• 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?

#### 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.