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.

Dual domination

Abstract

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.
Scheda breve Scheda completa Scheda completa (DC)
2019
978-3-030-25004-1
978-3-030-25005-8
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11386/4728848`
Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 2
• 0