Exploiting c-Closure in Kernelization Algorithms for Graph Problems

DOI10.4230/LIPIcs.ESA.2020.65OpenAlexW3082339973MaRDI QIDQ5874537

Christian Komusiewicz, Tomohiro Koana, Frank Sommer

Publication date: 7 February 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12931/pdf/LIPIcs-ESA-2020-65.pdf/

zbMATH Keywords

Ramsey numbersdominating setinduced matchingfixed-parameter tractabilitykernelizationirredundant set\(c\)-closure

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (4)

Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Unnamed Item ⋮ Twin-width and polynomial kernels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved induced matchings in sparse graphs
• On the induced matching problem
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Perfect Code is \(W[1\)-complete]
• Boundary classes of graphs for the dominating set problem
• New results on maximum induced matchings in bipartite graphs and beyond
• The complexity of irredundant sets parameterized by size
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Vertex Cover: Further Observations and Further Improvements
• FPT Algorithms for Domination in Biclique-Free Graphs
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• Extremal Combinatorics
• Vertex packings: Structural properties and algorithms
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
• Finding Cliques in Social Networks: A New Distribution-Free Model
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• Some remarks on the theory of graphs

This page was built for publication: Exploiting c-Closure in Kernelization Algorithms for Graph Problems