Contracting graphs to paths and trees
From MaRDI portal
Publication:2441588
DOI10.1007/s00453-012-9670-2zbMath1310.68229arXiv1104.3677OpenAlexW2174231092MaRDI QIDQ2441588
Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul, Pinar Heggernes
Publication date: 25 March 2014
Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.3677
kernelizationgraph modification problemsedge contractionsFPT algorithmstree contractionpath contraction
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items
Paths to Trees and Cacti ⋮ Multistage graph problems on a global budget ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Kernelization and randomized parameterized algorithms for co-path set problem ⋮ Graph editing to a fixed target ⋮ The complexity of degree anonymization by graph contractions ⋮ Increasing the minimum degree of a graph by contractions ⋮ Hadwiger Number of Graphs with Small Chordality ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ Obtaining split graphs by edge contraction ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Contracting graphs to paths and trees ⋮ A faster FPT algorithm for bipartite contraction ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ An improved linear kernel for the cycle contraction problem ⋮ Unnamed Item ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Reducing graph transversals via edge contractions ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Edge-contraction problems
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Improved algorithms for feedback vertex set problems
- Chordal deletion is fixed-parameter tractable
- On problems without polynomial kernels
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On the NP-hardness of edge-deletion and -contraction problems
- Proper interval vertex deletion
- Obtaining a planar graph by vertex deletion
- Contracting graphs to paths and trees
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Increasing the Minimum Degree of a Graph by Contractions
- Deterministic Parameterized Connected Vertex Cover
- A Quartic Kernel for Pathwidth-One Vertex Deletion
- Measuring Indifference: Unit Interval Vertex Deletion
- Enumerate and Measure: Improving Parameter Budget Management
- Proper Interval Vertex Deletion
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
- Obtaining a Planar Graph by Vertex Deletion
- On Feedback Vertex Set New Measure and New Structures
- Incompressibility through Colors and IDs
- Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
- Contractibility and NP-completeness
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- Edge-Deletion Problems
- ON DISJOINT CYCLES
- Color-coding
- (Meta) Kernelization
- Computational Complexity
- Node-and edge-deletion NP-complete problems
- Fast FPT-Algorithms for Cleaning Grids
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Contracting chordal graphs and bipartite graphs to paths and trees
- Complexity classification of some edge modification problems
