Exploiting c-Closure in Kernelization Algorithms for Graph Problems

DOI10.4230/LIPICS.ESA.2020.65OpenAlexW3082339973MaRDI QIDQ5874537FDOQ5874537

Authors: Tomohiro Koana, Christian Komusiewicz, 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/

Recommendations

• Exploiting \(c\)-closure in kernelization algorithms for graph problems
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• Kernels in graphs with a clique-cutset
• On graph kernels: hardness results and efficient alternatives.
• Essentially tight kernels for (weakly) closed graphs
• On computing graph closures
• On the computational complexity of graph closures
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• On the kernelization of split graph problems
• A note on computing graph closures

zbMATH Keywords

dominating setfixed-parameter tractabilityinduced matchingRamsey numberskernelizationirredundant set\(c\)-closure

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Fundamentals of parameterized complexity
• Parameterized complexity of finding regular induced subgraphs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Boundary classes of graphs for the dominating set problem
• Parameterized algorithms
• Some remarks on the theory of graphs
• Vertex packings: Structural properties and algorithms
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Kernelization of packing problems
• Title not available (Why is that?)
• The parameterized complexity of the induced matching problem
• Perfect Code is \(W[1]\)-complete
• Extremal combinatorics. With applications in computer science
• New results on maximum induced matchings in bipartite graphs and beyond
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Vertex cover: Further observations and further improvements
• Graph-Theoretic Concepts in Computer Science
• Improved induced matchings in sparse graphs
• On the induced matching problem
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• The complexity of irredundant sets parameterized by size
• Title not available (Why is that?)
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• FPT algorithms for domination in biclique-free graphs
• Finding cliques in social networks: a new distribution-free model
• Tight kernel bounds for problems on graphs with small degeneracy

Cited In (6)

• Title not available (Why is that?)
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Kernels in graphs with a clique-cutset
• Exploiting \(c\)-closure in kernelization algorithms for graph problems
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• Twin-width and polynomial kernels

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

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