Few Induced Disjoint Paths for H-Free Graphs

Abstract: Paths

P^{1}, l d o t s, P^{k}

in a graph

G = (V, E)

are mutually induced if any two distinct

P^{i}

and

P^{j}

have neither common vertices nor adjacent vertices. For a fixed integer

k

, the

k

-Induced Disjoint Paths problem is to decide if a graph

G

with

k

pairs of specified vertices

(s_{i}, t_{i})

contains

k

mutually induced paths

P^{i}

such that each

P^{i}

starts from

s_{i}

and ends at

t_{i}

. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer

k

, a classical result from the literature states that even

2

-Induced Disjoint Paths is NP-complete. We prove new complexity results for

k

-Induced Disjoint Paths if the input is restricted to

H

-free graphs, that is, graphs without a fixed graph

H

as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where

k

is part of the input.

This page was built for publication: Few Induced Disjoint Paths for $H$-Free Graphs