Bliznets, Ivan ;
Sagunov, Danil
Solving Target Set Selection with Bounded Thresholds Faster than 2^n
Abstract
In this paper we consider the Target Set Selection problem. The problem naturally arises in many fields like economy, sociology, medicine. In the Target Set Selection problem one is given a graph G with a function thr: V(G) > N cup {0} and integers k, l. The goal of the problem is to activate at most k vertices initially so that at the end of the activation process there is at least l activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever; (ii) vertex v becomes activated if at least thr(v) of its neighbours are activated. The problem and its different special cases were extensively studied from approximation and parameterized points of view. For example, parameterizations by the following parameters were studied: treewidth, feedback vertex set, diameter, size of target set, vertex cover, cluster editing number and others.
Despite the extensive study of the problem it is still unknown whether the problem can be solved in O^*((2epsilon)^n) time for some epsilon >0. We partially answer this question by presenting several fasterthantrivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by onethird of its degree. Also, we show that the problem parameterized by l is W[1]hard even when all thresholds are constant.
BibTeX  Entry
@InProceedings{bliznets_et_al:LIPIcs:2019:10223,
author = {Ivan Bliznets and Danil Sagunov},
title = {{Solving Target Set Selection with Bounded Thresholds Faster than 2^n}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {22:122:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10223},
URN = {urn:nbn:de:0030drops102235},
doi = {10.4230/LIPIcs.IPEC.2018.22},
annote = {Keywords: exact exponential algorithms, target set, vertex thresholds, social influence, irreversible conversions of graphs, bootstrap percolation}
}
05.02.2019
Keywords: 

exact exponential algorithms, target set, vertex thresholds, social influence, irreversible conversions of graphs, bootstrap percolation 
Seminar: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Issue date: 

2019 
Date of publication: 

05.02.2019 