Abstract
Paths P1,..., Pk in a graph G = (V, E) are mutually induced if any two distinct Pi
and P j 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 almostcomplete 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
and P j 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 almostcomplete 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
| Original language | English |
|---|---|
| Pages (from-to) | 2580-2604 |
| Journal | Algorithmica |
| Volume | 85 |
| Issue number | 9 |
| DOIs | |
| Publication status | Published - 11 Mar 2023 |