2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ minimum cost flow $\endgroup$
    – Brendan McKay
    Mar 28, 2014 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, 2014 at 21:50

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2016 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, 2016 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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