Polynomial-time data reduction for dominating set

Dealing with the NP-complete Dominating Set problem on 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.

• Publication year

  2002

• Venue

  JACM

• Publication date

  2002-07-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/990308.990309arXiv cs/0207066
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Parameterized Complexity: The Main Ideas and Some Research Frontiers

  2009cited by this paper
• Experiments on data reduction for optimal domination in networks

  2006cited by this paper
• Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs

  2005cited by this paper
• On Domination in Graphs

  2005cited by this paper
• Dominating Sets and Local Treewidth

  2003influential reference
• Blow-Ups, Win/Win's, and Crown Rules: Some New Directions in FPT

  2003cited by this paper
• Dominating sets in planar graphs: branch-width and exponential speed-up

  2003influential reference
• Parameterized complexity for the skeptic

  2003cited by this paper
• A Simple Heuristic for Minimum Connected Dominating Set in Graphs

  2003cited by this paper
• Genus Characterizes the Complexity of Graph Problems: Some Tight Results

  2003cited by this paper
• On efficient fixed-parameter algorithms for weighted vertex cover

  2003cited by this paper
• Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs

  2003cited by this paper
• Improved Tree Decomposition Based Algorithms for Domination-like Problems

  2002cited by this paper
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

  2002cited by this paper
• Exponential Speedup of Fixed-Parameter Algorithms on K3, 3-Minor-Free or K5-Minor-Free Graphs

  2002cited by this paper
• Improved Parameterized Algorithms for Planar Dominating Set

  2002cited by this paper
• Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem

  2002cited by this paper
• The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus

  2002cited by this paper
• Algorithms column: the vertex cover problem

  2002cited by this paper
• Exact algorithms for NP hard problems on networks: design, analysis and implementation

  2002cited by this paper
• Domination in Graphs Applied to Electric Power Networks

  2002cited by this paper
• Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

  2002cited by this paper
• Faster exact algorithms for hard problems: A parameterized point of view

  2001cited by this paper
• Parameterized complexity: exponential speed-up for planar graph problems

  2001cited by this paper
• Graph Separators: A Parameterized View

  2001cited by this paper
• Refined Search Tree Technique for Dominating Set on Planar Graphs 1

  2001cited by this paper
• Parameterized Complexity: The Main Ideas and Connections to Practical Computing

  2000cited by this paper
• On the Differences between "Practical" and "Applied"

  2000cited by this paper
• Vertex Cover: Further Observations and Further Improvements

  1999cited by this paper
• Complexity and Approximation

  1999cited by this paper
• Covering Trains by Stations or the Power of Data Reduction

  1998cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Fundamentals of domination in graphs

  1998cited by this paper
• LEDA: a platform for combinatorial and geometric computing

  1997influential reference
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• Complexity of Domination-Type Problems in Graphs

  1994cited by this paper
• Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy

  1992cited by this paper
• Graph Theory and Its Applications to Problems of Society

  1987cited by this paper
• Approximation algorithms for NP-complete problems on planar graphs

  1983cited by this paper
• A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982influential reference
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Vertex packings: Structural properties and algorithms

  1975cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper
• Differences Between

  year unknowncited by this paper

• XALP-completeness of parameterized problems on planar graphs

  2026cites this paper
• NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem

  2025cites this paper
• A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

  2025cites this paper
• PACE Solver Description: UzL Solver for Dominating Set and Hitting Set

  2025cites this paper
• Revisiting a Successful Reduction Rule for Dominating Set

  2025influential citation
• Budgeted spatial data acquisition: when coverage and connectivity matter

  2024cites this paper
• TSAcc: An Efficient Tempo-Spatial Similarity Aware Accelerator for Attention Acceleration

  2024cites this paper
• Exactly Solving Minimum Dominating Set and Its Generalization

  2024cites this paper
• XNLP-hardness of Parameterized Problems on Planar Graphs

  2024influential citation
• Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs

  2024cites this paper
• Optimized Edge Node Allocation Considering User Delay Tolerance for Cost Reduction

  2024cites this paper
• Parameterized Complexity of Paired Domination

  2024cites this paper
• Two-Point Concentration of the Domination Number of Random Graphs

  2024cites this paper
• (Independent) Roman Domination Parameterized by Distance to Cluster

  2024cites this paper
• Dynamic treewidth

  2023cites this paper
• Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs

  2023cites this paper
• Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions

  2023cites this paper
• Kernelizing Problems on Planar Graphs in Sublinear Space and Polynomial Time

  2023cites this paper
• A Linear Kernel for Planar Vector Domination

  2023cites this paper
• Methodology for Reducing the Connection Possibilities in Transmission Network Expansion Planning

  2023cites this paper
• An Exact Algorithm for the Minimum Dominating Set Problem

  2023cites this paper
• Relaxed Connected Dominating Set Problem for Power System Cyber–Physical Security

  2022influential citation
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

  2022cites this paper
• The fullerene graphs with a perfect star packing

  2022cites this paper
• The fullerenes with a perfect star packing

  2021cites this paper
• Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable

  2021cites this paper
• On the Δ-interval and the Δ-convexity numbers of graphs and graph products

  2021cites this paper
• Twin-width and Polynomial Kernels

  2021cites this paper
• Budgeted Dominating Sets in Uncertain Graphs

  2021cites this paper
• Packing stars in fullerenes

  2020cites this paper
• Effective Approaches to Solve P-Center Problem via Set Covering and SAT

  2020cites this paper
• LP WAN Gateway Location Selection Using Modified K-Dominating Set Algorithm

  2020cites this paper
• A Retrospective on (Meta) Kernelization

  2020cites this paper
• New kernels for several problems on planar graphs

  2020cites this paper
• Heuristic Algorithm for Gateway Location Selection in Large Scale LoRa Networks

  2020cites this paper
• Parameterized algorithms of fundamental NP-hard problems: a survey

  2020cites this paper
• A general kernelization technique for domination and independence problems in sparse classes

  2020cites this paper
• Computer Science – Theory and Applications: 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings

  2020cites this paper
• On the Parameterized Complexity of the Expected Coverage Problem

  2020cites this paper
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets

  2019cites this paper
• Domination above r-independence: does sparseness help?

  2019cites this paper
• Parameterized Computational Geometry via Decomposition Theorems

  2019cites this paper
• Preface

  2018cites this paper
• Experimental evaluation of kernelization algorithms to Dominating Set

  2018influential citation
• Framework

  2018cites this paper
• Some Contributions to Parameterized Complexity

  2018influential citation
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs

  2018cites this paper
• Hypertrees

  2018cites this paper
• Open problems

  2018cites this paper
• Graphs and SAT Notation

  2018cites this paper
• Polynomial Parameter Transformation

  2018cites this paper
• Turing Kernelization

  2018cites this paper
• Kernelization

  2018cites this paper
• CONFLICT-FREE COLORING OF GRAPHS\ast

  2018cites this paper
• Inductive Priorities

  2018cites this paper
• Extending Distillation

  2018cites this paper
• Linear Programming

  2018cites this paper
• Acknowledgements

  2018cites this paper
• Index

  2018cites this paper
• Improved Kernels for Several Problems on Planar Graphs

  2018cites this paper
• Problem Definitions

  2018cites this paper
• Representative Families

  2018cites this paper
• What Is a Kernel?

  2018cites this paper
• Modules

  2018cites this paper
• Surgery on Graphs

  2018cites this paper
• Improved solution strategies for dominating trees

  2018cites this paper
• Polynomial Lower Bounds

  2018cites this paper
• Greedy Packing

  2018cites this paper
• Instance Selectors

  2018cites this paper
• Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes

  2018cites this paper
• Crown Decomposition

  2018cites this paper
• Matroids

  2018cites this paper
• Bidimensionality and Protrusions

  2018cites this paper
• Expansion Lemma

  2018cites this paper
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness

  2018cites this paper
• Excluded Grid Minors and EPTAS

  2018cites this paper
• Conflict-Free Coloring of Graphs | SIAM Journal on Discrete Mathematics | Vol. 32, No. 4 | Society for Industrial and Applied Mathematics

  2018cites this paper
• Introduction to Treewidth

  2018cites this paper
• Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors

  2018influential citation
• Closed quasigeodesics, escaping from polygons, and conflict-free graph coloring

  2018cites this paper
• WALCOM: Algorithms and Computation: 12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings

  2018cites this paper
• Sunflower Lemma

  2018cites this paper
• Lossy Kernels for Connected Dominating Set on Sparse Graphs

  2017cites this paper
• Lossy Kernels for Hitting Subgraphs

  2017cites this paper
• Algorithmic Properties of Sparse Digraphs

  2017influential citation
• Three Colors Suffice: Conflict-Free Coloring of Planar Graphs

  2017cites this paper
• Formulating graph covering problems for adiabatic quantum computers

  2017cites this paper
• Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis

  2017cites this paper
• Software Diversity for Improved Network Security: Optimal Distribution of Software-Based Shared Vulnerabilities

  2017cites this paper
• Lossy kernels for connected distance-$r$ domination on nowhere dense graph classes

  2017cites this paper
• Adiabatic Quantum Computing with QUBO Formulations

  2016cites this paper
• Lower bounds for preprocessing algorithms based on protrusion replacement

  2016cites this paper
• Structural sparsity

  2016cites this paper
• A 43k Kernel for Planar Dominating Set using Computer-Aided Reduction Rule Discovery

  2016influential citation
• Structural sparseness and complex networks

  2016cites this paper
• Kernelization, Bidimensionality and Kernels

  2016cites this paper
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes

  2016cites this paper
• Lossy kernelization

  2016cites this paper
• Explicit Linear Kernels for Packing Problems

  2016cites this paper
• Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices

  2016cites this paper