Abstract | ||
---|---|---|
Let G = (V, E) be a graph on n vertices, where d(nu) denotes the degree of vertex nu, and t(nu) is a threshold associated with nu. We consider a process in which initially a set S of vertices becomes active, and thereafter, in discrete time steps, every vertex nu that has at least t(nu) active neighbors becomes active as well. The set S is contagious if eventually all V becomes active. The target set selection problem TSS asks for the smallest contagious set. TSS is NP-hard and moreover, notoriously difficult to approximate.In the conservative special case of TSS, t(nu) > 1/2d(nu) for every nu is an element of V. In this special case, TSS can be approximated within a ratio of O(Delta), where Delta = max(v is an element of V)[d(nu)]. In this work we introduce a more general class of TSS instances that we refer to as conservative on average (CoA), that satisfy the condition Sigma(nu is an element of V)t(v) > 1/2 Sigma(nu is an element of V) d(v). We design approximation algorithms for some subclasses of CoA. For example, if t(v) >= 1/2d(nu) for every nu is an element of V, we can find in polynomial time a contagious set of size (O) over tilde (Delta.OPT2), where OPT is the size of a smallest contagious set in G. We also provide several hardness of approximation results. For example, assuming the unique games conjecture, we prove that TSS on CoA instances with Delta <= 3 cannot be approximated within any constant factor.We also present results concerning the fixed parameter tractability of CoA TSS instances. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.dam.2021.09.003 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Target set selection | Journal | 305 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Uriel Feige | 1 | 5647 | 560.87 |
Shimon Kogan | 2 | 67 | 6.60 |