Improved budgeted connected domination and budgeted edge-vertex domination (Q2222087): Difference between revisions

Given a graph \(G\) and a budget \(k\), the Budgeted Connected Dominating Set problem (BCDS) asks to find a connected subset of at most \(k\) vertices maximizing the number of dominated vertices in \(G\). The BCDS problem is NP-hard and so far the best result, \((1-e^{-1})/13\)-approximation, was given in [\textit{S. Khuller} et al., in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1702--1713 (2014; Zbl 1423.68598)]. The present paper introduces a new tree decomposition technique to prove an improved \((1-e^{-1})/12\approx0.05267\) approximation. This ratio is then further improved to \((1-e{-7/8})/11\approx 0.05301\) by generalizing the first part of the analysis in [loc. cit.] and then modifying the proposed algorithm accordingly. This result is complemented with a \((1-e^{-1}+\epsilon)\) inapproximability bound for any \(\epsilon>0\), holding also for the case of star topology. The authors also present an algorithm for BSDS achieving an optimal \((1-e^{-1})\) approximation. Budgeted Edge-Vertex Domination (BEVD) is the edge-vertex domination variant of BCDS, where an edge dominates its endpoints and all vertices neighboring them and we seek a (not necessarily connected) subset of \(k\) edges maximizing the number of dominated vertices in \(G\). The authors prove that there is a \((1-e^{-1})\)- approximation algorithm for BEVD and that this is the best possible due to a \((1-e^{-1}+\epsilon)\) inapproximability lower bound for any \(\epsilon > 0\). Finally, the Partial Edge-Vertex Domination problem is considered where a quota of vertices needs to be dominated by utilizing the minimum number of edges possible. The authors employ a reduction to a partial version of the classical Set Cover problem to prove that there exists an \(H(n^\prime)\)-approximation, where \(H(\cdot)\) is the harmonic number and \(n^\prime\) is the number of vertices requested to be dominated.