Given a positive integer @math , a @math -dominating set in a graph @math is a set of vertices such that every vertex not in the set has at least @math neighbors in the set. A total @math -dominating set, also known as a @math -tuple total dominating set, is a set of vertices such that every vertex of the graph has at least @math neighbors in the set. The problems of finding the minimum size of a @math -dominating, resp. total @math -dominating set, in a given graph, are referred to as @math -domination, resp. total @math -domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total @math -domination). On the other hand, it follows from recent work by (2017) that these two families of problems are solvable in time @math in the class of interval graphs. In this work, we develop faster algorithms for @math -domination and total @math -domination in the class of proper interval graphs. The algorithms run in time @math for each fixed @math and are also applicable to the weighted case.
We now give an overview of related work and compare our results with the most related other results, in addition to those due to @cite_60 , which motivated this work.
@cite_60
2963271448
In 2013 Belmonte and Vatshelle used mim-width, a graph parameter bounded on interval graphs and permutation graphs that strictly generalizes clique-width, to explain existing algorithms for many domination-type problems, known as LC-VSVP problems. We focus on chordal graphs and co-comparability graphs, that strictly contain interval graphs and permutation graphs respectively. First, we show that mim-width is unbounded on these classes, thereby settling an open problem from 2012. Then, we introduce two graphs (K_t K_t ) and (K_t S_t ) to restrict these graph classes, obtained from the disjoint union of two cliques of size t, and one clique of size t and one independent set of size t respectively, by adding a perfect matching. We prove that ((K_t S_t) )-free chordal graphs have mim-width at most (t-1 ), and ((K_t K_t) )-free co-comparability graphs have mim-width at most (t-1 ). From this, we obtain several algorithmic consequences, for instance, while Dominating Set is NP-complete on chordal graphs, it can be solved in time ( O (n^ t ) ) on chordal graphs where t is the maximum among induced subgraphs (K_t S_t ) in the given graph. We also show that classes restricted in this way have unbounded rank-width which validates our approach.