# Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language:

$L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge$ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$.

($G$ is undirected).

This answer to a related question suggests that if we don't limit the path length, then the problem is in $P$.

Also, if we omit the simplicity requirement, it's easy to decide the problem.

Assuming we do care about both length and simplicity, is $L$ decidable in polynomial time?

• minimum cost flow – Brendan McKay Mar 28 '14 at 21:40
• @BrendanMcKay, can you please elaborate? I don't see an easy reduction from this problem to min cost flow. How do you force both a simple path and going through $v$ by min cost flow? – R B Mar 28 '14 at 21:50

I think this reduction to min-cost flow has a chance of working. First we change the graph into a network with directed edges. Each vertex $x$ other than $s,t,v$ is replaced by a pair of vertices $x^+,x^-$ joined by an edge $x^+{\to}x^-$ with capacity 1 and cost 1. Each edge of the original is replaced by two directed edges, each of capacity 1 and cost 0. An edge $x{-}y$ is replaced by directed edges $x^-{\to}y^+$ and $y^-{\to}x^+$. If $x$ is one of $s,t,v$, use $x$ in place of $x^-$ and $x^+$, and similarly for $y$. Now add a new vertex $z$ and two edges $s{\to}z$, $t{\to}z$ of capacity 1 and cost 0.
In this network, find the minimum cost flow of value 2 from $v$ to $z$. I believe that such a flow corresponds to internally-disjoint paths from $v$ to $s$ and $v$ to $t$, with the cost equal to the number of additional vertices those paths contain.
• Your approach doesn't seem to work if $s$ and $t$ are connected. Your maxflow might follow the path $s-t-...$ but you can't have that, so disconnect $s$ and $t$? Can you write a proof that this works? – Pavel Jun 13 '16 at 11:55