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?

  • 1
    $\begingroup$ minimum cost flow $\endgroup$ – Brendan McKay Mar 28 '14 at 21:40
  • $\begingroup$ @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? $\endgroup$ – 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.

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

  • $\begingroup$ 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? $\endgroup$ – Pavel Jun 13 '16 at 11:55
  • $\begingroup$ I might be wrong though, how can one prove this? pp.vk.me/c633723/v633723318/3789a/Aha8E2mQf2g.jpg In this graph there's no simple path from 1 to 4 through 2. But your algorithm will say there is. $\endgroup$ – Pavel Jun 13 '16 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.