2022/02/23 by Barnaby Martin, Daniël Paulusma, Martin, Barnaby +5
Computer Science · Engineering · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2202.11595
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. The 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. This is a classical graph problem that is NP-complete even for k=2. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.