3
$\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?

$\endgroup$
2
  • 1
    $\begingroup$ minimum cost flow $\endgroup$ Commented 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$ Commented Mar 28, 2014 at 21:50

2 Answers 2

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.

$\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$ Commented Jun 13, 2016 at 11:55
  • 1
    $\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$ Commented Jun 13, 2016 at 12:06
1
$\begingroup$

I was not able to verify the approach proposed by Brendan McKay's answer (in particular because of Pavel's comments), but I think there is a randomized PTIME algorithm using a recent result on the shortest two disjoint paths problem.

By this paper (see also this answer), the following is in randomized PTIME: given an undirected graph $G$ and vertices $s_1, t_1, s_2, t_2$, find vertex-disjoint paths connecting $s_1$ and $t_1$ and $s_2$ and $t_2$ whose total length is minimal. (Note that this shouldn't be confused with the problem of finding two disjoint paths that are individually shortest paths, as studied, e.g., here (Tali Eilam-Tzoreff, The disjoint shortest paths problem).)

To solve the problem in the question, we can simply use this algorithm, but cheating a bit to ensure that the endpoints of the paths are pairwise distinct so that the paths are really vertex-disjoint. For this, consider every possible neighbor $v'$ of $v$, and call the algorithm for the problem above, with $s_1 := s$, $t_1 := v'$, $s_2 := v$, and $t_2 := t$. Every solution of length $l$ given by the algorithm gives a solution of length $l+1$ to the original problem (to account for the edge $(v,v')$). Conversely, any solution to the original problem will go through $v$ and some neighbor of $v'$ just before, giving a solution to the shortest two disjoint paths problem.

Note that I'm assuming that in your questions the vertices $s$, $t$, and $v$ are distinct. If $s=v$ or $t=v$ then the problem is trivial. If $s=t$ but $v$ is distinct from $s$ and $t$, then you want a cycle of shortest length involving $s=t$ and $v$; we can do something similar to the above paragraph, by setting $t_2$ to be every possible choice $t'$ of neighbor of $t$.

(It may look like invoking the result on the shortest two disjoint paths problem is using a sledgehammer to crack a nut. But in fact I think the shortest two disjoint paths problem reduces to the problem in the original question, so probably there's no easier answer to the question than to the shortest two disjoint paths problem. Indeed, given an instance $G$ with vertices $s_1$ $t_1$ $s_2$ $t_2$, build $G'$ by adding a fresh 2-path to $G$ connecting $t_1$ and $s_2$, with a fresh vertex $v$ in the middle. Then solving the problem posed in the original question on $G'$ with $s:=s_1$ and $t:=t_2$ amounts to finding a simple path of minimal length $l$ that goes from $s$ to $t$ via $v$i in $G'$, and this precisely amounts to finding vertex-disjoint paths of minimal total length $l-2$ that go from $s_1$ to $t_1$ and from $s_2$ to $t_2$ in $G$.)

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.