Approximation and kernelization for chordal vertex deletion

DOI10.1137/17M112035XzbMATH Open1394.05124OpenAlexW2891457632MaRDI QIDQ4586151FDOQ4586151

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

Recommendations

• Approximation and kernelization for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Chordal deletion is fixed-parameter tractable
• Chordal Deletion Is Fixed-Parameter Tractable

zbMATH Keywords

approximation algorithmkernelization algorithmchordal vertex deletion

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cites Work

• Graph Classes: A Survey
• The node-deletion problem for hereditary properties is NP-complete
• Parametrized complexity theory.
• Kernelization – Preprocessing with a Guarantee
• A 4 k ² kernel for feedback vertex set
• A New Algorithm for Generating All the Maximal Independent Sets
• The Complexity of Multiterminal Cuts
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Multiway cuts in node weighted graphs
• Title not available (Why is that?)
• Parameterized Algorithms
• The k-Disjoint Paths Problem on Chordal Graphs
• Vertex packings: Structural properties and algorithms
• On Independent Circuits Contained in a Graph
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• On Linear Time Minor Tests with Depth-First Search
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• On diameters and radii of bridged graphs
• Parameterized complexity of vertex colouring
• Chordal editing is fixed-parameter tractable
• Kernelization using structural parameters on sparse graph classes
• Nondeterminism within $P^ * $
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Title not available (Why is that?)
• A unified approach to approximating resource allocation and scheduling
• Chordal deletion is fixed-parameter tractable
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• A cubic kernel for feedback vertex set and loop cutset
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• A Separator Theorem for Chordal Graphs
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Interval Deletion Is Fixed-Parameter Tractable
• A characterisation of rigid circuit graphs
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Parameterized complexity of vertex deletion into perfect graph classes
• Subexponential parameterized algorithm for Interval Completion
• Title not available (Why is that?)
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• Recognizing tough graphs is NP-hard
• Uniform Kernelization Complexity of Hitting Forbidden Minors
• Unit interval vertex deletion: fewer vertices are relevant
• Linear Recognition of Almost Interval Graphs
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Compression via Matroids
• Exploring the subexponential complexity of completion problems
• (Meta) Kernelization
• Chordal Deletion Is Fixed-Parameter Tractable
• Erd\H{o}s-P\'osa property of chordless cycles and its applications
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• A polynomial kernel for distance-hereditary vertex deletion

Cited In (24)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Deletion in Abstract Voronoi Diagrams in Expected Linear Time.
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• A polynomial kernel for 3-leaf power deletion
• A vertex incremental approach for maintaining chordality
• Chordal Deletion Is Fixed-Parameter Tractable
• On the approximate compressibility of connected vertex cover
• Erdős-Pósa property of chordless cycles and its applications
• Chordless Cycle Packing Is Fixed-Parameter Tractable
• On the Parameterized Complexity of Clique Elimination Distance
• Search-space reduction via essential vertices
• A survey of parameterized algorithms and the complexity of edge modification
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Quadratic vertex kernel for split vertex deletion
• Structural parameterizations with modulator oblivion
• A polynomial kernel for distance-hereditary vertex deletion
• Kernelization through Tidying
• Polynomial Kernel for Interval Vertex Deletion
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• A constant-factor approximation for weighted bond cover
• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size

This page was built for publication: Approximation and kernelization for chordal vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4586151)