Induced disjoint paths in claw-free graphs
From MaRDI portal
Publication:5251566
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)
Abstract: Paths P1,...,Pk in a graph G=(V,E) are said to be mutually induced if for any 1 <= i < j <= k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that Pi connects si and ti for i=1,...,k. We show that this problem is fixed-parameter tractable for claw-free graphs when parameterized by k. Several related problems, such as the k-in-a-Path problem, are proven to be fixed-parameter tractable for claw-free graphs as well. We show that an improvement of these results in certain directions is unlikely, for example by noting that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless NP subseteq coNP/poly. Moreover, the problem becomes NP-complete, even when k=2, for the more general class of K_1,4-free graphs. Finally, we show that the n^O(k)-time algorithm of Fiala et al. for testing whether a claw-free graph contains some k-vertex graph H as a topological induced minor is essentially optimal by proving that this problem is W[1]-hard even if G and H are line graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 4133491 (Why is no real title available?)
- scientific article; zbMATH DE number 475595 (Why is no real title available?)
- scientific article; zbMATH DE number 7051285 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 3290993 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A linear time algorithm for the induced disjoint paths problem in planar graphs
- A note on contracting claw-free graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Chordless paths through three vertices
- Claw-free graphs. V. Global structure
- Clique or hole in claw-free graphs
- Containment relations in split graphs
- Corrigendum to: On the complexity of testing for odd holes and induced odd paths
- Detecting fixed patterns in chordal graphs in polynomial time
- Detecting induced star-like minors in polynomial time
- Finding induced trees
- Finding topological subgraphs is fixed-parameter tractable
- Fundamentals of parameterized complexity
- Graph minors. XIII: The disjoint paths problem
- Induced circuits in planar graphs
- Induced disjoint paths in circular-arc graphs in linear time
- Induced disjoint paths in claw-free graphs
- Kernel bounds for disjoint cycles and disjoint paths
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- On a closure concept in claw-free graphs
- On the Computational Complexity of Combinatorial Problems
- On the complexity of testing for odd holes and induced odd paths
- Parameterized complexity of induced graph matching on claw-free graphs
- The \(k\)-in-a-path problem for claw-free graphs
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
- The complexity of induced minors and related problems
- The four-in-a-tree problem in triangle-free graphs
- The structure of claw-free graphs
- The three-in-a-tree problem
Cited in
(13)- The \(k\)-in-a-path problem for claw-free graphs
- Few induced disjoint paths for \(H\)-free graphs
- Few induced disjoint paths for \(H\)-free graphs
- MIP formulations for induced graph optimization problems: a tutorial
- Clique or hole in claw-free graphs
- Parameterized complexity of induced graph matching on claw-free graphs
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- Induced disjoint paths and connected subgraphs for H-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- A polynomial kernel for deletion to the scattered class of cliques and trees
- The \(k\)-in-a-path problem for claw-free graphs
- Induced disjoint paths in claw-free graphs
- Parameterized complexity of induced H-matching on claw-free graphs
This page was built for publication: Induced disjoint paths in claw-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5251566)
