2023/02/14 by Tesshu Hanaka, Hirotaka Ono, Hanaka, Tesshu +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2302.06983
A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S1,S2,…,Sk such that the size of each unit Si is r and the subgraph of G induced by Si is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets (r=1), paired dominating sets (r=2), and connected dominating sets (r is arbitrary and k=1). In this paper, we investigate the computational complexity of r-Grouped Dominating Set, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, the problem is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that the problem for every fixed r>0 is still hard to solve. From the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that it is fixed-parameter tractable for r and treewidth, because the condition of r-grouped domination for a constant r can be represented as monadic second-order logic (mso2). This is good news, but the running time is not practical. We then design an O^*(min\(2τ(r+1))τ,(2τ)2τ\)-time algorithm for general r≥ 2, where τ is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i.e., r ∈ \2,3\, we can speed up the algorithm, whose running time becomes O^*((r+1)τ). We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r-Grouped Dominating Set.