2
$\begingroup$

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows:

Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.

Question: Does there exist $k$-pairwise vertex-disjoint paths $P_1,\ldots,P_k$, such that $P_i$ goes from $s_i$ to $t_i$?

The problem, for general $k$, is known to be NP-complete even for planar graphs of max degree 3.

That said, $2$-$\text{DPP}$ admits a nearly linear algorithm for general undirected graphs.

Is there anything known for any higher value of $k$ (assuming fixed $k$ value)? What about $k=3$?

$\endgroup$
6
$\begingroup$

For undirected graph problem admits a FPT algorithm for any fixed $k$. Robertson and Seymour, Graph Minor XIII. Their algorithm runs in time $2^{2^{2^{2^{O(k)}}}} P(n)$ which means for $k = O(\log\log\log\log n)$ is polynomial. But it's not known whether there is better bound for $k$ or not. In special cases like undirected planar case and recently bounded genus case, running time improved.

For directed graph it's NP-Complete even case of 2-disjoint path problem. But in planar graphs is FPT by result of Marx et al., in graphs of bounded genus is at least in XP (not known whether is FPT or not), in directed acyclic graphs is $W[1]$-hard by result of Slivkins, for tournaments is NP-complete (not known if is FPT or even XP, edge disjoint version admits XP algorithm by result of Seymour et al).

$\endgroup$
4
$\begingroup$

Here's what I know.

  1. For undirected graphs, the problem admits a 'nonconstructive' FPT algorithm based on Robertson-Seymour theory. The running time is $f(k) n^3$ where $f$ is a fast-growing function.

  2. For directed graphs, the problem is $\sf{NP}$-complete for any constant $k \geq 3$. In the case of planar directed graphs, it is polynomial for fixed $k$: there is a relatively simple $n^{O(k)}$ algorithm due to Schrijver ('Finding k Disjoint Paths in a Directed Planar Graph', SICOMP) and a more involved FPT algorithm with running time $f(k) poly(n)$ due to Cygan et al., where $f(k)$ is a double-exponential function ('The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable', FOCS 2013).

Also, if I remember right there are some cases where the edge-disjoint version is easier, but I couldn't recollect the details.

$\endgroup$

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.