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

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