Algorithm and Hardness results on Liar's Dominating Set and $k$-tuple Dominating Set

Sandip Banerjee, Sujoy Bhore

Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $D\subseteq V$ such that every vertex $u\in V\setminus D$ is adjacent to at least one vert…