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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Could you be more specific about your simple path definition ? $\endgroup$– Grzegorz WierzowieckiCommented Jan 6, 2012 at 11:58
-
$\begingroup$ It is a path where no vertex appears twice $\endgroup$– robee19Commented Jan 6, 2012 at 12:36
-
5$\begingroup$ This smells like homework. (I have assigned this problem as homework.) $\endgroup$– JeffεCommented Jan 7, 2012 at 18:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ Your assumption is correct. Thank you for the demonstration. Quick thinking ! $\endgroup$– robee19Commented Jan 6, 2012 at 12:37
-
$\begingroup$ Do you mean from $x_{in}$ to $t$, to avoid going through $x$ twice? $\endgroup$ Commented Jul 5, 2016 at 1:47
-
$\begingroup$ @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. $\endgroup$ Commented Jul 29, 2016 at 10:56
$\begingroup$
$\endgroup$
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.
answered Jan 6, 2012 at 13:35