Induced disjoint paths in claw-free graphs
From MaRDI portal
Publication:5251566
DOI10.1137/140963200zbMATH Open1311.05090arXiv1202.4419OpenAlexW2571021594MaRDI QIDQ5251566FDOQ5251566
Authors: Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen 
Publication date: 20 May 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1202.4419
Recommendations
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)
Cites Work
- Fundamentals of parameterized complexity
- On a closure concept in claw-free graphs
- Graph minors. XIII: The disjoint paths problem
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Claw-free graphs. V. Global structure
- The structure of claw-free graphs
- On the Computational Complexity of Combinatorial Problems
- Kernel bounds for disjoint cycles and disjoint paths
- Title not available (Why is that?)
- Finding topological subgraphs is fixed-parameter tractable
- The complexity of induced minors and related problems
- Detecting fixed patterns in chordal graphs in polynomial time
- Detecting induced star-like minors in polynomial time
- A linear time algorithm for the induced disjoint paths problem in planar graphs
- Title not available (Why is that?)
- Chordless paths through three vertices
- A note on contracting claw-free graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Induced circuits in planar graphs
- Title not available (Why is that?)
- Containment relations in split graphs
- The three-in-a-tree problem
- Induced disjoint paths in claw-free graphs
- Parameterized complexity of induced graph matching on claw-free graphs
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
- The four-in-a-tree problem in triangle-free graphs
- On the complexity of testing for odd holes and induced odd paths
- Finding induced trees
- Corrigendum to: On the complexity of testing for odd holes and induced odd paths
- Clique or hole in claw-free graphs
- The \(k\)-in-a-path problem for claw-free graphs
- Induced disjoint paths in circular-arc graphs in linear time
Cited In (12)
- 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
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- Parameterized complexity of induced graph matching on claw-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- 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)
