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
  • 5
    This smells like homework. (I have assigned this problem as homework.) – Jeffε Jan 7 '12 at 18:37
up vote 3 down vote accepted

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.