Few Induced Disjoint Paths for H-Free Graphs
Barnaby Martin  1@  , Daniel Paulusma  1@  , Siani Smith  1@  , Erik Jan Van Leeuwen  2@  
1 : Durham University
2 : Utrecht University

Paths P_1,... , 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. 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.


Online user: 2 Privacy
Loading...