TY - JOUR

T1 - Few induced disjoint paths for H-free graphs

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

AU - Leeuwen, Erik Jan van

N1 - Publisher Copyright:
© 2022 The Author(s)

PY - 2023/1/4

Y1 - 2023/1/4

N2 - Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj 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 (si,ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. 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.

AB - Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj 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 (si,ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. 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.

KW - Complexity dichotomy

KW - H-free graph

KW - Induced disjoint paths

UR - http://www.scopus.com/inward/record.url?scp=85140958586&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2022.10.024

DO - 10.1016/j.tcs.2022.10.024

M3 - Article

SN - 0304-3975

VL - 939

SP - 182

EP - 193

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -