Dual domination

Inspired by the feedback scenario, which characterizes online social networks, we introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in the input network are partitioned into two categories: Positive nodes (V+) and negative nodes (V-). We are looking for a set D ⊆ V+ that dominates the largest number of positive nodes while avoiding as many negative nodes as possible. In particular, we study the Maximum Bounded Dual Domination (MBDD) problem, where given a bound k, the problem is to find a set D ⊆ V+, which maximizes the number of nodes dominated in V+ dominating at most k nodes in V- We show that the MBDD problem is hard to approximate to a factor better than (1 − 1/e). We give a polynomial time approximation algorithm with approximation guaranteed (1 − e−1/Δ), where Δ represents the maximum number of neighbors in V+ of any node in V- Furthermore, we give an O(|V|k2) time algorithm to solve the problem on trees.