Name
Abstract | ||
|---|---|---|
The well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to be NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP ⊆ coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k2) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k3) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00224-014-9580-6 | conference on current trends in theory and practice of informatics |
Keywords | Field | DocType |
Disjoint paths,Computational complexity,Parameterized complexity,Polynomial kernel,Split graphs | Kernelization,Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Clique-sum,Cograph,Pathwidth,Metric dimension,Mathematics,Split graph | Conference |
Volume | Issue | ISSN |
57 | 1 | 0302-9743 |
Citations | PageRank | References |
2 | 0.40 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pinar Heggernes | 1 | 845 | 72.39 |
| Pim van 't Hof | 2 | 209 | 20.75 |
| Erik Jan van Leeuwen | 3 | 275 | 25.89 |
| Reza Saei | 4 | 24 | 3.62 |