Abstract
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertexweighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem.
1) We show that the PBDS problem is NPcomplete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the wellknown fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time.
2) We show that if one is willing to settle for (1ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edgeprobabilities, the problem can be solved optimally in polynomial time.
3) We consider the parameterized complexity of the PBDS problem, and show that UniPBDS (where all edge probabilities are identical) is 𝖶[1]hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth.
4) Finally, we extend some of our parameterized results to planar and apexminorfree graphs.
Our first hardness proof (Thm. 1) makes use of the new problem of kSubset ΣΠ Maximization (kSPM), which we believe is of independent interest. We prove its NPhardness by a reduction from the wellknown kSUM problem, presenting a close relationship between the two problems.
BibTeX  Entry
@InProceedings{choudhary_et_al:LIPIcs.MFCS.2021.32,
author = {Choudhary, Keerti and Cohen, Avi and Narayanaswamy, N. S. and Peleg, David and Vijayaragunathan, R.},
title = {{Budgeted Dominating Sets in Uncertain Graphs}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {32:132:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14472},
URN = {urn:nbn:de:0030drops144723},
doi = {10.4230/LIPIcs.MFCS.2021.32},
annote = {Keywords: Uncertain graphs, Dominating set, NPhard, PTAS, treewidth, planar graph}
}
Keywords: 

Uncertain graphs, Dominating set, NPhard, PTAS, treewidth, planar graph 
Collection: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) 
Issue Date: 

2021 
Date of publication: 

18.08.2021 