<p>The reduction is the following. </p>

<p>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).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-06T12:37:05.547Z
Your assumption is correct. Thank you for the demonstration. Quick thinking !
robee19
CC BY-SA 3.0
2016-07-05T01:47:50.680Z
Do you mean from $x_{in}$ to $t$, to avoid going through $x$ twice?
Geoffrey Irving
CC BY-SA 3.0
2016-07-29T10:56:50.133Z
@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
CC BY-SA 3.0
2012-01-06T12:16:13.703Z
2016-07-01T13:04:44.717Z
2016-07-01T13:04:44.717Z
Dmytro Korduban
<p>Try following approach for grapf $G=(V,E)$:</p>

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

<p>To be specific, for simplicity of description, above approach assumes bidirectional graph.</p>

<p>For directed graph it applies as well, after adjusting a little bit.</p>

CC BY-SA 3.0
2012-01-06T13:35:34.937Z
2012-01-06T13:43:04.207Z
2012-01-06T13:43:04.207Z
Grzegorz Wierzowiecki
<p>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.</p>

CC BY-SA 3.0
2012-01-06T11:58:46.890Z
Could you be more specific about your *simple path* definition ?
Grzegorz Wierzowiecki
CC BY-SA 3.0
2012-01-06T12:36:29.557Z
It is a path where no vertex appears twice
robee19
CC BY-SA 3.0
2012-01-07T18:37:15.743Z
This smells like homework.  (I have assigned this problem as homework.)
Jeffε
<ds.algorithms><graph-algorithms><max-flow>
Viapath as a maximum flow problem
robee19
# Viapath as a maximum flow problem

(Asked by: username_0 on 2012-01-06)

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.

**Tags:** ds.algorithms, graph-algorithms, max-flow
> **Comments:**
> **username_1**: Could you be more specific about your *simple path* definition ?  
> **username_0**: It is a path where no vertex appears twice  
> **username_2**: This smells like homework.  (I have assigned this problem as homework.)  

---

## 2 answers

### Answer by username_3 on 2012-01-06. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: Your assumption is correct. Thank you for the demonstration. Quick thinking !  
> **username_4**: Do you mean from $x_{in}$ to $t$, to avoid going through $x$ twice?  
> **username_3**: @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.  

---

### Answer by username_1 on 2012-01-06. Score: 0

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.


---

