## Finding disjoint paths in split graphs

*Pinar Heggernes, Pim van 't Hof, Erik Jan van Leeuwen and Reza Saei*

*Theory of Computing Systems*, *Theory of Computing Systems*, vol. 57, no. 1, pp. 140-159, 2015.

[__DOI__][__Preprint__]

This paper appeared in the proceedings of SOFSEM 2014, the 40th International Conference on Current Trends in Theory and Practice of Computer Science (held on January 25-30, 2014 in Nový Smokovec, Slovakia), *Lecture Notes in Computer Science*, vol. 8327, pp. 315-326, 2014.

[__DOI__]

### 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 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*(*k ^{2}*) 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*(

*k*) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.

^{3}