<p>here is a sketch of the idea:</p>
<ul>
<li>If you don't have the constraint that the path is simple (i.e. no edge is used twice) then you just have to find a path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> and one from <span class="math-container">$v$</span> to <span class="math-container">$w$</span>.</li>
<li>If you have the constraint that the path is edge-simple (i.e. no edge used twice) then you can use a flow algorithm in the following way: you have one source which is <span class="math-container">$v$</span> of capacity 2 and two targets <span class="math-container">$u$</span> and <span class="math-container">$w$</span> both of capacity 1. Each edge has capacity 1. If there is a flow of capacity 2 in this graph then you can retrieve two paths from <span class="math-container">$v$</span> to both <span class="math-container">$u$</span> and <span class="math-container">$w$</span> which gives you the expected path.</li>
<li>If you have the constraint that the path is vertex-simple then you can create an oriented graph where there are two copies <span class="math-container">$(n_{in},n_{out})$</span> of each node <span class="math-container">$n$</span>. Then you replace each edge (<span class="math-container">$a,b$</span>) to the pair <span class="math-container">$(a_{out},b_{in})$</span> and <span class="math-container">$(b_{out},a_{in})$</span> and you create one edge <span class="math-container">$(a_{in},a_{out})$</span> for each vertex. In this graph you set the capacity of each edge to be 1 and you look for a flow of capacity 2 between the source <span class="math-container">$v_{out}$</span> and the targets <span class="math-container">$u_{out}$</span> and <span class="math-container">$w_{out}$</span>.</li>
</ul>

CC BY-SA 4.0
2021-11-01T23:40:27.887Z
note that, in the second bullet point, in the reduction to flow, you should use not just any flow of value 2, but an acyclic flow.  otherwise the final path might not be simple.
Neal Young
CC BY-SA 4.0
2021-11-02T00:52:35.217Z
At a high-level you want to find node-disjoint paths from w to u and v which is conceptually easier to think about and then implement via flow.
Chandra Chekuri
CC BY-SA 4.0
2021-11-03T11:42:30.863Z
@NealYoung, I agree that, if you want to retrieve the path, you cannot take any flow (for instance, you need an integral flow) but I am not sure why you would need an acyclic one. 
That being said if I wanted to actually implement this algorithm I would not use a flow but directly retrieve one path from  to  and then a second path from  to  but where the edges used in the path from  to  can only be traversed in the direction that is not used in the first path.
Louis
CC BY-SA 4.0
2021-11-03T18:36:16.820Z
Lous, you need it because the problem asks for a *simple* path from u to v.  If you start with a flow that sends flow along an edge (x, y) (say, in getting from w to u) and flow along (y, x) (in getting from w to v), the path you get by composing the two paths will not be simple.
Neal Young
CC BY-SA 4.0
2021-11-03T23:03:56.347Z
I understand why I was not understanding your comment. For me (and for wikipedia) a flow is (unless explicitly stated otherwise) skew symmetric meaning that for any pair (u,v) the flow from u to v is the opposite of the flow from v to u. I agree that I need that the flow is skew symmetric. Apart from this classical notion I don't think I need acyclicity. If you have a loop of flow with no source or target then the algorithm still works and the loop will just not be used in the path. Maybe we have not the same notion of acyclicity?
Louis
CC BY-SA 4.0
2021-11-05T00:21:43.033Z
I agree that skew symmetry is also enough to make the paths edge-disjoint.  Also, by default I think most people think of flows as acyclic.  My point was really a minor technical nitpick.
Neal Young
CC BY-SA 4.0
2021-11-01T21:52:25.607Z
2021-11-01T21:52:25.607Z
Louis
<p>Problem: Given three vertices <span class="math-container">$u, v$</span> and <span class="math-container">$w$</span> from an undirected graph. Find a path (where vertices are not repeated) from <span class="math-container">$u$</span> to <span class="math-container">$w$</span> that passes through <span class="math-container">$v$</span>. This problem has been mentioned in <a href="https://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809">Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph</a>, and <a href="https://cstheory.stackexchange.com/questions/25077/shortest-path-hitting-a-given-vertex">Shortest path hitting a given vertex</a>. It is said that it can be solved with minimum cost flow, but I don't see exactly how. Could anybody please elaborate on this?</p>

CC BY-SA 4.0
2021-11-01T19:51:44.557Z
I'm sorry about the downvotes that you're getting. It seems like a nontrivial question and this should be a good place to ask.
smapers
CC BY-SA 4.0
2021-11-01T23:42:33.680Z
FWIW, to me this question seems to be around the level of a homework question in an advanced algorithms class, not research level.
Neal Young
CC BY-SA 4.0
2021-11-02T00:50:04.810Z
This is a standard homework question though non-obvious.
Chandra Chekuri
<graph-algorithms><flow-problems>
Finding a path in a graph hitting a particular vertex
William4920
# Finding a path in a graph hitting a particular vertex

(Asked by: username_0 on 2021-11-01)

Problem: Given three vertices $u, v$ and $w$ from an undirected graph. Find a path (where vertices are not repeated) from $u$ to $w$ that passes through $v$. This problem has been mentioned in [Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph](https://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809), and [Shortest path hitting a given vertex](https://cstheory.stackexchange.com/questions/25077/shortest-path-hitting-a-given-vertex). It is said that it can be solved with minimum cost flow, but I don't see exactly how. Could anybody please elaborate on this?

**Tags:** graph-algorithms, flow-problems

> **Comments:**
> **username_1**: I'm sorry about the downvotes that you're getting. It seems like a nontrivial question and this should be a good place to ask.  
> **username_2**: FWIW, to me this question seems to be around the level of a homework question in an advanced algorithms class, not research level.  
> **username_3**: This is a standard homework question though non-obvious.  

---

## 1 answers

### Answer by username_4 on 2021-11-01. Score: 1 | Accepted answer

here is a sketch of the idea:

* If you don't have the constraint that the path is simple (i.e. no edge is used twice) then you just have to find a path from $u$ to $v$ and one from $v$ to $w$.
* If you have the constraint that the path is edge-simple (i.e. no edge used twice) then you can use a flow algorithm in the following way: you have one source which is $v$ of capacity 2 and two targets $u$ and $w$ both of capacity 1. Each edge has capacity 1. If there is a flow of capacity 2 in this graph then you can retrieve two paths from $v$ to both $u$ and $w$ which gives you the expected path.
* If you have the constraint that the path is vertex-simple then you can create an oriented graph where there are two copies $(n\_{in},n\_{out})$ of each node $n$. Then you replace each edge ($a,b$) to the pair $(a\_{out},b\_{in})$ and $(b\_{out},a\_{in})$ and you create one edge $(a\_{in},a\_{out})$ for each vertex. In this graph you set the capacity of each edge to be 1 and you look for a flow of capacity 2 between the source $v\_{out}$ and the targets $u\_{out}$ and $w\_{out}$.

> **Comments:**
> **username_2**: note that, in the second bullet point, in the reduction to flow, you should use not just any flow of value 2, but an acyclic flow.  otherwise the final path might not be simple.  
> **username_3**: At a high-level you want to find node-disjoint paths from w to u and v which is conceptually easier to think about and then implement via flow.  
> **username_4**: @NealYoung, I agree that, if you want to retrieve the path, you cannot take any flow (for instance, you need an integral flow) but I am not sure why you would need an acyclic one.  That being said if I wanted to actually implement this algorithm I would not use a flow but directly retrieve one path from  to  and then a second path from  to  but where the edges used in the path from  to  can only be traversed in the direction that is not used in the first path.  
> **username_2**: Lous, you need it because the problem asks for a *simple* path from u to v.  If you start with a flow that sends flow along an edge (x, y) (say, in getting from w to u) and flow along (y, x) (in getting from w to v), the path you get by composing the two paths will not be simple.  
> **username_4**: I understand why I was not understanding your comment. For me (and for wikipedia) a flow is (unless explicitly stated otherwise) skew symmetric meaning that for any pair (u,v) the flow from u to v is the opposite of the flow from v to u. I agree that I need that the flow is skew symmetric. Apart from this classical notion I don't think I need acyclicity. If you have a loop of flow with no source or target then the algorithm still works and the loop will just not be used in the path. Maybe we have not the same notion of acyclicity?  
> **username_2**: I agree that skew symmetry is also enough to make the paths edge-disjoint.  Also, by default I think most people think of flows as acyclic.  My point was really a minor technical nitpick.  

---

