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.

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

2 Answers 2


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.

  • $\begingroup$ Your assumption is correct. Thank you for the demonstration. Quick thinking ! $\endgroup$
    – robee19
    Commented Jan 6, 2012 at 12:37
  • $\begingroup$ Do you mean from $x_{in}$ to $t$, to avoid going through $x$ twice? $\endgroup$ Commented Jul 5, 2016 at 1:47
  • $\begingroup$ @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. $\endgroup$ Commented Jul 29, 2016 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.


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.