Algorithmic results on locating-total domination in graphs (Q6157416)

A dominating set (DS) of \(G\) is a set \(D\subseteq V\) such that each vertex in \(V\setminus D\) is adjacent to at least one vertex in \(D\). A total dominating set (TDS) of \(G\) is a set \(D\subseteq V\) with the property that each vertex in \(V\) is adjacent to at least one vertex in \(D\). A locating-dominating set (LDS) of \(G\) is a subset \(D\subseteq V\) such that \(D\) is a DS of \(G\) and \(N(u) \cap D\neq N(v)\cap D\) for each pair of distinct vertices \(u\) and \(v\) in \(V\setminus D\). A locating-total dominating set (LTDS) of \(G\) is a subset \(D\subseteq V\) such that \(D\) is both TDS and LDS of \(G\). The smallest size of an LTDS of \(G\) between all LTDSs of \(G\) is called the locating-total domination number of \(G\), denoted by \(\gamma_L^t(G)\). The Locating-Total Dominating Set problem is the problem of computing an LTDS \(D\) of a given graph \(G\) with \(|D|=\gamma_L^t(G)\). The authors prove that the decision version of the Locating-Total Dominating Set problem is NP-complete for circle graphs, undirected path graphs, and graphs of separability at most 2. Also, they give a \((2 \ln|V|+1.7)\)-approximation algorithm for computing a minimum LTDS of a given graph \(G\) and prove that the problem of computing a minimum locating-total dominating set is APX-complete for graphs of degree at most 4. Finally, they propose a linear algorithm for computing the locating-total domination number of trees.