-3

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?

William4920
  • 5
  • 2

1 Answers1

1

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}$.
Louis
  • 775
  • 6
  • 9
  • 1
    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 Nov 01 '21 at 23:40
  • 1
    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 Nov 02 '21 at 00:52
  • @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 Nov 03 '21 at 11:42
  • 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 Nov 03 '21 at 18:36
  • 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 Nov 03 '21 at 23:03
  • 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 Nov 05 '21 at 00:21