Contracting to a longest path in H-free graphs
From MaRDI portal
Publication:6065420
Abstract: We prove two dichotomy results for detecting long paths as patterns in a given graph. The NP-hard problem Longest Induced Path is to determine the longest induced path in a graph. The NP-hard problem Longest Path Contractibility is to determine the longest path to which a graph can be contracted to. By combining known results with new results we completely classify the computational complexity of both problems for -free graphs. Our main focus is on the second problem, for which we design a general contractibility technique that enables us to reduce the problem to a matching problem.
Cites work
- A note on contracting claw-free graphs
- A simple polynomial algorithm for the longest path problem on cocomparability graphs
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Algorithms for maximum weight induced paths
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- An improved linear kernel for the cycle contraction problem
- Clique-width for hereditary graph classes
- Computing and counting longest paths on circular-arc graphs in polynomial time
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- Contractibility and NP-completeness
- Contracting bipartite graphs to paths and cycles
- Contracting chordal graphs and bipartite graphs to paths and trees
- Contracting few edges to remove forbidden induced subgraphs
- Contraction theorems in Hamiltonian graph theory
- Cyclicity of graphs
- Finding Large Clique Minors is Hard
- Finding small separators in linear time via treewidth reduction
- Graph minors. XIII: The disjoint paths problem
- Graph-Theoretic Concepts in Computer Science
- HAMILTONian circuits in chordal bipartite graphs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2188410 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- Mim-width. I. Induced path problems
- Obtaining a bipartite graph by contracting few edges
- Obtaining planarity by contracting few edges
- On characterization of Hamiltonian graphs
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- On the parameterized complexity of contraction to generalization of trees
- Parameterized complexity of three edge contraction problems with degree constraints
- Path contraction faster than 2ⁿ
- Paths to trees and cacti
- Split contraction: the untold story
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
- The computational complexity of graph contractions II: Two tough polynomially solvable cases
- The edge Hamiltonian path problem is NP-complete
- The longest path problem has a polynomial solution on interval graphs
- The longest path problem is polynomial on cocomparability graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Rectilinear Steiner Tree Problem is NP-Complete
- The structure of bull-free graphs II and III -- a summary
- The structure of claw-free graphs
- Vertex colouring and forbidden subgraphs -- a survey
Cited in
(9)- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- The complexity of contracting bipartite graphs into small cycles
- Induced disjoint paths and connected subgraphs for H-free graphs
- Finding matching cuts in \(H\)-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Revisiting path contraction and cycle contraction
- Complexity framework for forbidden subgraphs. I: The framework
- The complexity of contracting bipartite graphs into small cycles
This page was built for publication: Contracting to a longest path in H-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065420)
