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](https://stackoverflow.com/questions/10825249/find-all-vertices-on-all-simple-paths-between-two-vertices-in-an-undirected-gr/10828138#10828138) 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?



Is undirected short-simple-path-through-3-vertices decidable in polynomial time?
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.


I didn't try to prove this formally so there might some some twist that I've overlooked.


