Polynomial-time data reduction for dominating set
From MaRDI portal
Abstract: Dealing with the NP-complete Dominating Set problem on undirected graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy to implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization.
Recommendations
Cited in
(94)- A more effective linear kernelization for cluster editing
- The parameterized complexity of the induced matching problem
- On problems without polynomial kernels
- Computational study on planar dominating set problem
- Characterising bounded expansion by neighbourhood complexity
- Computational study on a PTAS for planar dominating set problem
- Explicit linear kernels for packing problems
- Towards optimal kernel for connected vertex cover in planar graphs
- Twin-width and polynomial kernels
- On the parameterized complexity of the expected coverage problem
- On the -interval and the -convexity numbers of graphs and graph products
- Minimum fill-in of sparse graphs: kernelization and approximation
- New kernels for several problems on planar graphs
- On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
- Capacitated domination: problem complexity and approximation algorithms
- On connected dominating sets of restricted diameter
- Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
- Linear kernels for outbranching problems in sparse digraphs
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Kernels in planar digraphs
- A refined search tree technique for dominating set on planar graphs
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Edge-disjoint packing of stars and cycles
- Genus characterizes the complexity of certain graph problems: Some tight results
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Effective and efficient data reduction for the subset interconnection design problem
- Safe approximation and its relation to kernelization
- Simpler linear-time kernelization for planar dominating set
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- Kernelization -- preprocessing with a guarantee
- Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
- An improved kernel for planar connected dominating set
- scientific article; zbMATH DE number 2089218 (Why is no real title available?)
- Fixed-parameter tractability results for full-degree spanning tree and its dual
- On the small cycle transversal of planar graphs
- A 13k-kernel for planar feedback vertex set via region decomposition
- New analysis and computational study for the planar connected dominating set problem
- Lossy kernels for connected dominating set on sparse graphs
- Bidimensionality and kernels
- Kernelization using structural parameters on sparse graph classes
- Polynomial-time data reduction for the subset interconnection design problem
- Capacitated Domination and Covering: A Parameterized Perspective
- A Linear Kernel for Planar Feedback Vertex Set
- Planar graph vertex partition for linear problem kernels
- Kernelization: new upper and lower bound techniques
- Planar capacitated dominating set is \(W[1]\)-hard
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Improved linear problem kernel for planar connected dominating set
- Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
- A strengthened analysis of an algorithm for dominating set in planar graphs
- Conflict-free coloring of graphs
- Lower bounds on kernelization
- Subexponential parameterized algorithms
- Confronting intractability via parameters
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Independent dominating set problem revisited
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- On the Parameterized Complexity of the Expected Coverage Problem
- A Retrospective on (Meta) Kernelization
- The fullerene graphs with a perfect star packing
- Algorithmic properties of sparse digraphs
- Domination above \(r\)-independence: does sparseness help?
- Lossy Kernels for Hitting Subgraphs
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- A linear kernel for planar red-blue dominating set
- Lossy kernels for connected dominating set on sparse graphs
- A linear kernel for a planar connected dominating set
- On the small cycle transversal of planar graphs
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- SOFSEM 2006: Theory and Practice of Computer Science
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- Quadratic kernelization for convex recoloring of trees
- Implicit branching and parameterized partial cover problems
- (Independent) Roman domination parameterized by distance to cluster
- Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
- Kernelization for counting problems on graphs: preserving the number of minimum solutions
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- XNLP-hardness of parameterized problems on planar graphs
- Parameterized complexity of dominating set variants in almost cluster and split graphs
- Parameterized complexity of paired domination
- XALP-completeness of parameterized problems on planar graphs
- Kernelization for counting problems on graphs: preserving the number of minimum solutions
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Packing stars in fullerenes
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Experiments on data reduction for optimal domination in networks
- Improved algorithms and complexity results for power domination in graphs
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- A cubic kernel for feedback vertex set and loop cutset
- Linear kernelizations for restricted 3-Hitting Set problems
This page was built for publication: Polynomial-time data reduction for dominating set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583575)
