Valentin Garnero ; Ignasi Sau - A Linear Kernel for Planar Total Dominating Set

dmtcs:3295 - Discrete Mathematics & Theoretical Computer Science, May 16, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-14
A Linear Kernel for Planar Total Dominating SetArticle

Authors: Valentin Garnero ; Ignasi Sau ORCID

    A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on general graphs when parameterized by the solution size. By the meta-theorem of Bodlaender et al. [J. ACM, 2016], there exists a linear kernel for Total Dominating Set on graphs of bounded genus. Nevertheless, it is not clear how such a kernel can be effectively constructed, and how to obtain explicit reduction rules with reasonably small constants. Following the approach of Alber et al. [J. ACM, 2004], we provide an explicit kernel for Total Dominating Set on planar graphs with at most $410k$ vertices, where $k$ is the size of the solution. This result complements several known constructive linear kernels on planar graphs for other domination problems such as Dominating Set, Edge Dominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-Blue Dominating Set.


    Volume: Vol. 20 no. 1
    Section: Discrete Algorithms
    Published on: May 16, 2018
    Accepted on: April 19, 2018
    Submitted on: May 2, 2017
    Keywords: Computer Science - Data Structures and Algorithms,05C85, 05C10,G.2.2
    Funding:
      Source : OpenAIRE Graph
    • Algorithmes de graphes parametres et exacts; Funder: French National Research Agency (ANR); Code: ANR-09-BLAN-0159
    • Decomposition of Graphical Models; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0028
    • IDEAL-BASED ALGORITHMS FOR VASSES AND WELL-STRUCTURED SYSTEMS; Funder: French National Research Agency (ANR); Code: ANR-17-CE40-0028

    Consultation statistics

    This page has been seen 624 times.
    This article's PDF has been downloaded 471 times.