Polynomial kernelization for removing induced claws and diamonds

DOI10.1007/s00224-016-9689-xzbMath1368.68222arXiv1503.00704OpenAlexW2115674935WikidataQ59529120 ScholiaQ59529120MaRDI QIDQ2398208

Marcin Pilipczuk, Marek Cygan, Marcin Wrochna, Michał Pilipczuk, Erik Jan van Leeuwen

Publication date: 15 August 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.00704

zbMATH Keywords

parameterized complexitypolynomial kerneledge deletion\{claw, diamond\}-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ A polynomial kernel for trivially perfect editing ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations

Cites Work

• Parameterized complexity of induced graph matching on claw-free graphs
• Cluster editing with locally bounded modifications
• Claw-free graphs. IV: Decomposition theorem
• Claw-free graphs. V. Global structure
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Which problems have strongly exponential complexity?
• A polynomial kernel for trivially perfect editing
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems
• Parametrized complexity theory.
• Exploring the Subexponential Complexity of Completion Problems
• On Generating Triangle-Free Graphs
• Faster Parameterized Algorithms for Deletion to Split Graphs
• Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
• Two Edge Modification Problems without Polynomial Kernels
• Edge-Deletion Problems
• Line Graphs of Helly Hypergraphs
• Subexponential parameterized algorithm for Interval Completion
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Characterizations of derived graphs
• Graph-Theoretic Concepts in Computer Science
• A Subexponential Parameterized Algorithm for Proper Interval Completion

This page was built for publication: Polynomial kernelization for removing induced claws and diamonds