# Viapath as a maximum flow problem

Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \$ different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a maximum flow problem. Does anyone have a pointer for this ? Also any references to problems that can be reformulated, in not completely obvious ways, to maximum flow problems would be valued.

• Could you be more specific about your simple path definition ? – Grzegorz Wierzowiecki Jan 6 '12 at 11:58
• It is a path where no vertex appears twice – robee19 Jan 6 '12 at 12:36
• This smells like homework. (I have assigned this problem as homework.) – Jeffε Jan 7 '12 at 18:37

The reduction is the following.

Consider a graph as directed (that means, each edge $(u,v)$ is actually a pair of arcs pointing in the opposite directions). Split each vertex $v \in V$ to 2 different vertices $v_{in}$ and $v_{out}$ and fix the adjacent edges such that all in-arcs ends in $v_{in}$ and all out-arcs starts from $v_{out}$. Also add an arc $(v_{in}, v_{out})$ of unit capacity for each such pair. This guarantees that the flow will not pass through any original vertex more than once (which is necessary for path simplicity).

Then add a sink $t$ and arcs $(a_{out},t)$ and $(b_{out}, t)$ of unit capacity. Find a maximum flow from $x_{out}$ to $t$. If a simple path $a-x-b$ exists in the original graph, the parts $x-a$ and $x-b$ will not share a vertex (except from $x$) and the maximum flow will have size 2 so you will be able to reconstruct the answer from the flow. The opposite is true, too.

Upd.: The aforesaid was written under assumption that "simple path" means "a path with no repeated vertices". In other case there is no need for vertices splitting.

• Your assumption is correct. Thank you for the demonstration. Quick thinking ! – robee19 Jan 6 '12 at 12:37
• Do you mean from $x_{in}$ to $t$, to avoid going through $x$ twice? – Geoffrey Irving Jul 5 '16 at 1:47
• @GeoffreyIrving Just make sure $(x_{in}, x_{out})$ capacity is 2. Well, basically it's the same thing (you can cancel loops through $x$ easily). I guess I was thinking about shortest path problem, where loops are impossible so it doesn't matter. – Dmytro Korduban Jul 29 '16 at 10:56

Try following approach for grapf $G=(V,E)$:

• Create new sink $V'=V \cup t$, and edges $E' = E \cup \{ (a,t), (b,t) \}$.
• make all edges' capacity 1 unit (I assume discrete maxflow).
• Make $x$ your source.
• Maximal flow $F$ will be 2 iff path from $a$ to $b$ exist. Searched path will be:$P = F - { (a,t),(b,t) }$

To be specific, for simplicity of description, above approach assumes bidirectional graph.

For directed graph it applies as well, after adjusting a little bit.