Approximation and Kernelization for Chordal Vertex Deletion
From MaRDI portal
Publication:4586151
DOI10.1137/17M112035XzbMath1394.05124OpenAlexW2891457632MaRDI QIDQ4586151
Bart M. P. Jansen, Marcin Pilipczuk
Publication date: 12 September 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m112035x
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (17)
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Structural parameterizations with modulator oblivion ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Erdős-Pósa property of chordless cycles and its applications ⋮ Unnamed Item ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ Quadratic vertex kernel for split vertex deletion ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ On the approximate compressibility of connected vertex cover ⋮ Unnamed Item ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Kernelization using structural parameters on sparse graph classes
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Parameterized complexity of vertex deletion into perfect graph classes
- Recognizing tough graphs is NP-hard
- A cubic kernel for feedback vertex set and loop cutset
- Chordal deletion is fixed-parameter tractable
- On diameters and radii of bridged graphs
- The node-deletion problem for hereditary properties is NP-complete
- Unit interval vertex deletion: fewer vertices are relevant
- Parameterized complexity of vertex colouring
- A characterisation of rigid circuit graphs
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Parametrized complexity theory.
- Exploring the Subexponential Complexity of Completion Problems
- Kernelization – Preprocessing with a Guarantee
- (Meta) Kernelization
- A Separator Theorem for Chordal Graphs
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Chordal Deletion Is Fixed-Parameter Tractable
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- On Linear Time Minor Tests with Depth-First Search
- Vertex packings: Structural properties and algorithms
- A New Algorithm for Generating All the Maximal Independent Sets
- Nondeterminism within $P^ * $
- Graph Classes: A Survey
- The Complexity of Multiterminal Cuts
- Linear Recognition of Almost Interval Graphs
- Subexponential parameterized algorithm for Interval Completion
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- Erd\H{o}s-P\'osa property of chordless cycles and its applications
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Multiway cuts in node weighted graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Compression via Matroids
- Interval Deletion Is Fixed-Parameter Tractable
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- On Independent Circuits Contained in a Graph
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The k-Disjoint Paths Problem on Chordal Graphs
- A unified approach to approximating resource allocation and scheduling
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- A polynomial kernel for distance-hereditary vertex deletion
This page was built for publication: Approximation and Kernelization for Chordal Vertex Deletion
