Polynomial-time data reduction for dominating set
From MaRDI portal
Publication:3583575
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
(84)- A linear kernel for a planar connected dominating set
- Conflict-free coloring of graphs
- Kernelization: new upper and lower bound techniques
- Packing stars in fullerenes
- A Retrospective on (Meta) Kernelization
- An improved kernel for planar connected dominating set
- A Linear Kernel for Planar Feedback Vertex Set
- A more effective linear kernelization for cluster editing
- Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
- Lossy kernels for connected dominating set on sparse graphs
- Quadratic kernelization for convex recoloring of trees
- On the Parameterized Complexity of the Expected Coverage Problem
- Computational study on a PTAS for planar dominating set problem
- A strengthened analysis of an algorithm for dominating set in planar graphs
- Polynomial-time data reduction for the subset interconnection design problem
- On the parameterized complexity of the expected coverage problem
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Characterising bounded expansion by neighbourhood complexity
- SOFSEM 2006: Theory and Practice of Computer Science
- On problems without polynomial kernels
- Planar capacitated dominating set is \(W[1]\)-hard
- On the small cycle transversal of planar graphs
- Linear kernelizations for restricted 3-Hitting Set problems
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Lossy kernels for connected dominating set on sparse graphs
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Kernelization using structural parameters on sparse graph classes
- Capacitated domination: problem complexity and approximation algorithms
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- Implicit branching and parameterized partial cover problems
- A 13k-kernel for planar feedback vertex set via region decomposition
- Fixed-parameter tractability results for full-degree spanning tree and its dual
- The fullerene graphs with a perfect star packing
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Planar graph vertex partition for linear problem kernels
- Improved linear problem kernel for planar connected dominating set
- Kernelization -- preprocessing with a guarantee
- Lower bounds on kernelization
- Domination above \(r\)-independence: does sparseness help?
- On connected dominating sets of restricted diameter
- New analysis and computational study for the planar connected dominating set problem
- On the small cycle transversal of planar graphs
- Safe approximation and its relation to kernelization
- A cubic kernel for feedback vertex set and loop cutset
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Subexponential parameterized algorithms
- Algorithmic properties of sparse digraphs
- Confronting intractability via parameters
- On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products
- Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
- Improved algorithms and complexity results for power domination in graphs
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- The parameterized complexity of the induced matching problem
- Independent dominating set problem revisited
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Experiments on data reduction for optimal domination in networks
- Capacitated Domination and Covering: A Parameterized Perspective
- Minimum fill-in of sparse graphs: kernelization and approximation
- Kernels in planar digraphs
- Computational study on planar dominating set problem
- A refined search tree technique for dominating set on planar graphs
- New kernels for several problems on planar graphs
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Towards optimal kernel for connected vertex cover in planar graphs
- Explicit linear kernels for packing problems
- Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
- Edge-disjoint packing of stars and cycles
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Linear kernels for outbranching problems in sparse digraphs
- scientific article; zbMATH DE number 2089218 (Why is no real title available?)
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Effective and efficient data reduction for the subset interconnection design problem
- Bidimensionality and kernels
- A linear kernel for planar red-blue dominating set
- Lossy Kernels for Hitting Subgraphs
- Genus characterizes the complexity of certain graph problems: Some tight results
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Simpler linear-time kernelization for planar dominating set
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
- Twin-width and polynomial kernels
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)
