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.
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.