# Finding a path in a graph hitting a particular vertex

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, and 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?

• 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. Nov 1, 2021 at 19:51
• FWIW, to me this question seems to be around the level of a homework question in an advanced algorithms class, not research level. Nov 1, 2021 at 23:42
• This is a standard homework question though non-obvious. Nov 2, 2021 at 0:50

• 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}$$.