Improved Algorithms for k-Domination and Total k-Domination in Proper Interval Graphs

LEONI, V.; LOPEZ PUJATO MARIA INES; MILANIC, M.; HARTINGER, TATIANA (UNIVERSIDAD OF PRIMORSKA, ESLOVENIA ); CHIARELLI, NINA (UNIVERSIDAD OF PRIMORSKA, ESLOVENIA )

LECTURE NOTES IN COMPUTER SCIENCE

Springer

Año: 2018 p. 1 - 13

0302-9743

Given a positive integer $k$, a $k$-dominating set in a graph $G$ is a set of vertices such that every vertex not in the set has at least $k$ neighbors in the set. A total $k$-dominating set, also known as a $k$-tuple total dominating set, is a set of vertices such that every vertex of the graph has at least $k$ neighbors in the set. The problems of finding the minimum size of a $k$-dominating, resp.~total $k$-dominating set, in a given graph, are referred to as $k$-domination, resp.~total $k$-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 $k$-domination). On the other hand, it follows from recent work by Kang et al.~(2017) that these two families of problems are solvable in time $mathcal{O}(|V(G)|^{6k+4})$ in the class of interval graphs. In this work, we develop faster algorithms for $k$-domination and total $k$-domination in the class of proper interval graphs. The algorithms run in time $mathcal{O}(|V(G)|^{3k})$ for each fixed $kge 1$ and are also applicable to the weighted case.