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?
3
-
$\begingroup$ 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. $\endgroup$– smapersCommented Nov 1, 2021 at 19:51
-
$\begingroup$ FWIW, to me this question seems to be around the level of a homework question in an advanced algorithms class, not research level. $\endgroup$– Neal YoungCommented Nov 1, 2021 at 23:42
-
$\begingroup$ This is a standard homework question though non-obvious. $\endgroup$– Chandra ChekuriCommented Nov 2, 2021 at 0:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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}$.
-
1$\begingroup$ 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. $\endgroup$ Commented Nov 1, 2021 at 23:40
-
1$\begingroup$ 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. $\endgroup$ Commented Nov 2, 2021 at 0:52
-
$\begingroup$ @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. $\endgroup$– LouisCommented Nov 3, 2021 at 11:42
-
$\begingroup$ 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. $\endgroup$ Commented Nov 3, 2021 at 18:36
-
$\begingroup$ 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? $\endgroup$– LouisCommented Nov 3, 2021 at 23:03