### 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(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 3) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.

Original language | English |
---|---|

Pages (from-to) | 140-159 |

Journal | Theory of computing systems |

Volume | 57 |

DOIs | |

Publication status | Published - 2015 |

Externally published | Yes |

## Fingerprint Dive into the research topics of 'Finding disjoint paths in split graphs'. Together they form a unique fingerprint.

## Cite this

Heggernes, P., van 't Hof, P., van Leeuwen, E. J., & Saei, R. (2015). Finding disjoint paths in split graphs.

*Theory of computing systems*,*57*, 140-159. https://doi.org/10.1007/s00224-014-9580-6