Polynomial-time data reduction for dominating set
From MaRDI portal
Publication:3583575
DOI10.1145/990308.990309zbMATH Open1192.68337DBLPjournals/jacm/AlberFN04arXivcs/0207066OpenAlexW2093762675WikidataQ57360014 ScholiaQ57360014MaRDI QIDQ3583575FDOQ3583575
Authors: Jochen Alber, Michael R. Fellows, Rolf Niedermeier 
Publication date: 17 August 2010
Published in: Journal of the ACM (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/cs/0207066
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (84)
- Conflict-free coloring of graphs
- A linear kernel for a planar connected dominating set
- Kernelization: new upper and lower bound techniques
- A Retrospective on (Meta) Kernelization
- An improved kernel for planar connected dominating set
- A Linear Kernel for Planar Feedback Vertex Set
- Packing stars in fullerenes
- A more effective linear kernelization for cluster editing
- Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
- Quadratic kernelization for convex recoloring of trees
- Computational study on a PTAS for planar dominating set problem
- Polynomial-time data reduction for the subset interconnection design problem
- A strengthened analysis of an algorithm for dominating set in planar graphs
- SOFSEM 2006: Theory and Practice of Computer Science
- On the parameterized complexity of the expected coverage problem
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Characterising bounded expansion by neighbourhood complexity
- 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
- Lossy kernels for connected dominating set on sparse graphs
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- Capacitated domination: problem complexity and approximation algorithms
- Kernelization using structural parameters on sparse graph classes
- The fullerene graphs with a perfect star packing
- Title not available (Why is that?)
- Fixed-parameter tractability results for full-degree spanning tree and its dual
- Implicit branching and parameterized partial cover problems
- A \(13k\)-kernel for planar feedback vertex set via region decomposition
- Planar graph vertex partition for linear problem kernels
- Kernelization -- preprocessing with a guarantee
- Improved linear problem kernel for planar connected dominating set
- Lower bounds on kernelization
- On connected dominating sets of restricted diameter
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- New analysis and computational study for the planar connected dominating set problem
- Safe approximation and its relation to kernelization
- Algorithmic properties of sparse digraphs
- A cubic kernel for feedback vertex set and loop cutset
- Subexponential parameterized algorithms
- Confronting intractability via parameters
- Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Improved algorithms and complexity results for power domination in graphs
- 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
- Capacitated Domination and Covering: A Parameterized Perspective
- Experiments on data reduction for optimal domination in networks
- Kernels in planar digraphs
- Computational study on planar dominating set problem
- A refined search tree technique for dominating set 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
- Title not available (Why is that?)
- Effective and efficient data reduction for the subset interconnection design problem
- The complexity ecology of parameters: An illustration using bounded max leaf number
- A linear kernel for planar red-blue dominating set
- Genus characterizes the complexity of certain graph problems: Some tight results
- Simpler linear-time kernelization for planar dominating set
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Lossy kernels for connected dominating set on sparse graphs
- On the Parameterized Complexity of the Expected Coverage Problem
- Title not available (Why is that?)
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Domination above \(r\)-independence: does sparseness help?
- On the small cycle transversal of planar graphs
- On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products
- Minimum fill-in of sparse graphs: kernelization and approximation
- New kernels for several problems on planar graphs
- 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
- Bidimensionality and kernels
- Lossy Kernels for Hitting Subgraphs
- On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
- Twin-width and polynomial kernels
Uses Software
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)
