A Distributed Approximation Algorithm for the Total Dominating Set Problem

Given a network graph \(G=(V,E)\) , a subset \(T\subseteq V\) is said to be a total dominating set (TDS) if every \(v\in V\) is adjacent to at least one node in T. In this paper, we present a distributed algorithm for the TDS problem via the LP relaxation techniques. For a positive integer k and maximum degree \(\Delta \) , the proposed algorithm outputs a fractional total dominating set of expected size \(O(k\Delta ^\frac{2}{k})|TDS_{OPT}|\) . The distributed algorithm runs in \(O(k^2)\) communication rounds, and the algorithm use messages of size \(O(\log \Delta )\) . The fractional solution is then rounded to obtain an integer total dominating set for the original problem.