# Tag Info

15

I think that whether p>0 can be decided in polynomial time. The problem in question can be easily cast as the edge-disjoint paths problem, where the underlying graph is a planar graph consisting of m+1 layers each of which contains n vertices, plus m degree-4 vertices to represent the possible adjacent swaps. Note that the planarity of this graph ...

8

We just answered this for $k=2$: Andreas Björklund and Thore Husfeldt, Shortest two disjoint paths in polynomial time, ICALP 2014, to appear. PDF of proceedings version, rev. e5d5661

6

The problem becomes NP-complete ... this is a "graphical" :-) reduction from 3-SAT ... it should be self-explanatory (... if not let me know). Two notes: +X1a, -X1a, +X1b, -X1b,...,+X2a,-X2a, ...,dum1,...,dum4 are all distinct labels; in the figure each label appears $\leq 2$ times; but it is straightforward to make each label appears exactly 2 times ...

6

I just found a reduction from the two disjoint paths problem. Given a directed graph $G = (V, E)$ and two pairs $(s_1, t_1)$ and $(s_2, t_2)$, we can add a new vertex $w$ to the graph and an edge from $t_1$ to $w$ and from $w$ to $s_2$. The new graph admits a simple path from $s_1$ to $t_2$ through $w$ if and only if the original graph admits two disjoint ...

5

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 ...

4

Here's what I know. 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. 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$: ...

1

I found a replacement path allocation for $𝐾_𝑛$ in a more general setting. Consider an edge $𝑒_1$ that uses edge $𝑒_2$ on its path. The allocation induces a dependency from $𝑒_1$ to $𝑒_2$. Mutual exclusion defined above corresponds to a cycle of 2 such dependencies. Now consider the more general setting: a cycle of $𝑛$ dependencies induced by a path ...

Only top voted, non community-wiki answers of a minimum length are eligible