New algorithms for weigthed k-domiantion and total k-domination in proper interval graphs

CHIARELLI, NINA (UNIVERSIDAD OF PRIMORSKA, ESLOVENIA ); LEONI, V.; LOPEZ PUJANTO , MARÍA INÉS; MILANIC MARTIN (UNIVERSIDAD OF PRIMORSKA, ESLOVENIA ); HARTINGER, TATIANA (UNIVERSIDAD OF PRIMORSKA, ESLOVENIA )

THEORETICAL COMPUTER SCIENCE

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2019 vol. 795 p. 128 - 141

0304-3975

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, 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, respectively total $k$-dominating set, in a given graph, are referred to as $k$-domination, respectively 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 previous works by Bui-Xuan et al.~(2013) and by Belmonte et al.~(2013) that these two families of problems are solvable in time $mathcal{O}(|V(G)|^{3k+4})$ in the class of interval graphs. We develop faster algorithms for $k$-domination and total $k$-domination in the class of proper interval graphs, by means of reduction to a single shortest path computation in a derived directed acyclic graph with $mathcal{O}(|V(G)|^{2k})$ nodes and$mathcal{O}(|V(G)|^{4k})$ arcs. We show that a suitable implementation, which avoids constructing all arcs of the digraph, leads toa running time of$ {O}(|V(G)|^{3k})$. The algorithms are also applicable to the weighted case.