Linear kernel method improves semitotal domination problem on planar graphs

A Linear Kernel for Planar Semitotal Domination

Data Structures and Algorithms

Summary

The semitotal domination problem involves finding a special group of nodes in a network where each node covers others and is close to another in the group. The authors show a way to simplify this problem for flat networks (planar graphs) by shrinking it to a size proportional to the allowed group size. They also prove that this problem remains very hard for several other types of networks. This work helps better understand which network types allow efficient simplifications and which do not.

What this means in practice

  • For network algorithm designers: Create faster preprocessing steps for semitotal domination problems on planar network topologies using the linear kernel introduced in this work.
  • For graph software developers: Avoid investing in parameterized algorithms for semitotal domination on split, bipartite, or circle graphs by relying on the complexity hardness results proved here.

A theory result. No direct application yet.

Authors

Paloma T. de Lima, Lukas Retschmeier

Abstract

A set of vertices $S$ in a graph $G$ is a semitotal dominating set if $S$ is a dominating set and every vertex in $S$ has a witness, that is, another vertex in $S$ within distance at most two. The Semitotal Domination problem asks whether $G$ admits such a set of size at most $k$. We study this problem parameterized by the solution size. We provide a linear kernel of size $358k$ on planar graphs, a result that adds to several existing linear kernels for other domination variants on planar graphs. Additionally, we show Semitotal Domination is $W[2]$-hard on split graphs, on bipartite graphs and on $t$-claw-free graphs, it is $W[1]$-hard on circle graphs.