Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
minimum cost flow –  Brendan McKay Mar 28 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 at 21:50

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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