Budgeted Dominating Sets in Uncertain Graphs

We study the {em 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 vertex-weighted uncertain graph $G=(V, E, p, omega)$ and an integer {em budget} (or {em 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 {em Probabilistic Budgeted Dominating Set}~(PBDS) problem and present the following results. begin{enumerate} dnsitem We show that the PBDS problem is NP-complete even when restricted to uncertain {em trees} of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is wone-hard for the budget parameter $k$, and under the {em Exponential time hypothesis} it cannot be solved in $n^{o(k)}$ time. item We show that if one is willing to settle for $(1-epsilon)$ approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. item We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is wone-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. item Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. end{enumerate}