Exploiting c-closure in kernelization algorithms for graph problems
From MaRDI portal
Exploiting \(c\)-closure in kernelization algorithms for graph problems
\(c\)-closuredominating setfixed-parameter tractabilityinduced matchingirredundant setkernelizationRamsey numbers
Generalized Ramsey theory (05C55) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)
Abstract: A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number such that G is c-closed. Fox et al. [ICALP '18] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size k^O(c), that Induced Matching admits a kernel with O(c^7*k^8) vertices, and that Irredundant Set admits a kernel with O(c^(5/2)*k^3) vertices. Our kernelization exploits the fact that c-closed graphs have polynomially-bounded Ramsey numbers, as we show.
Recommendations
Cites work
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Boundary classes of graphs for the dominating set problem
- Crown reductions for the minimum weighted vertex cover problem
- Crown structures for vertex cover kernelization
- Detecting and enumerating small induced subgraphs in c-closed graphs
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Extremal combinatorics. With applications in computer science
- Finding cliques in social networks: a new distribution-free model
- FPT algorithms for domination in biclique-free graphs
- Fundamentals of parameterized complexity
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 3869067 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- scientific article; zbMATH DE number 7765378 (Why is no real title available?)
- Improved induced matchings in sparse graphs
- Kernelization of packing problems
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- New results on maximum induced matchings in bipartite graphs and beyond
- On the induced matching problem
- Parameterized algorithms
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Parameterized complexity of finding regular induced subgraphs
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Slightly superexponential parameterized problems
- Some remarks on the theory of graphs
- The complexity of irredundant sets parameterized by size
- The parameterized complexity of the induced matching problem
- Tight kernel bounds for problems on graphs with small degeneracy
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Which problems have strongly exponential complexity?
Cited in
(10)- Kernels in graphs with a clique-cutset
- Detecting and enumerating small induced subgraphs in c-closed graphs
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Exploiting c-Closure in Kernelization Algorithms for Graph Problems
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Essentially tight kernels for (weakly) closed graphs
- Computing dense and sparse subgraphs of weakly closed graphs
- Essentially tight kernels for (weakly) closed graphs
- A complexity-theoretic analysis of majority illusion in social networks
- Solving partial dominating set and related problems using twin-width
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 Q5048305)
