×

Target set selection with maximum activation time. (English) Zbl 1522.68409

Summary: A target set selection model is a graph \(G\) with a threshold function \(\tau : V (G) \to \mathbb{N}\) upper-bounded by the vertex degree. For a given model, a set \(S_0 \subseteq V (G)\) is a target set if \(V (G)\) can be partitioned into non-empty subsets \(S_0, S_1, \dots, S_t\) such that, for all \(i \in \{1, \dots, t\}\), \(S_i\) contains exactly every vertex \(v\) outside \(S_0 \cup \cdots \cup S_{i - 1}\) having at least \(\tau (v)\) neighbors in \(S_0 \cup \cdots \cup S_{i - 1}\). We say that \(t\) is the activation time \(t_\tau (S_0)\) of the target set \(S_0\). The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set \(S_0\) that maximizes \(t_\tau (S_0)\). That is, given a graph \(G\), a threshold function \(\tau\) in \(G\), and an integer \(k\), the objective of the TSS-time problem is to decide whether \(G\) contains a target set \(S_0\) such that \(t_\tau (S_0) \geq k\). Let \(\tau^\star = \max_{v \in V (G)} \tau (v)\). Our main result is the following dichotomy about the complexity of TSS-time when \(G\) belongs to a minor-closed graph class \(\mathcal{C}\): if \(\mathcal{C}\) has bounded local treewidth, the problem is FPT parameterized by \(k\) and \(\tau^\star \); otherwise, it is NP-complete even for fixed \(k = 4\) and \(\tau^\star = 2\). We also prove that, with \(\tau^\ast = 2\), the problem is NP-hard in bipartite graphs for fixed \(k = 5\), and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set \(S_0\) in a given tree maximizing \(t_\tau (S_0)\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
05C75 Structural characterization of families of graphs
68Q27 Parameterized complexity, tractability and kernelization

References:

[1] Ackerman, Eyal; Ben-Zwi, Oren; Wolfovitz, Guy, Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411, 4017-4022 (2010) · Zbl 1235.90168
[2] Amini, Hamed, Bootstrap percolation in living neural networks, J. Stat. Phys., 141, 3, 459-475 (2010) · Zbl 1207.82037
[3] Balogh, József; Bollobás, Béla, Bootstrap percolation on the hypercube, Probab. Theory Related Fields, 134, 4, 624-648 (2006) · Zbl 1087.60068
[4] Balogh, József; Bollobás, Béla; Duminil-Copin, Hugo; Morris, Robert, The sharp threshold for bootstrap percolation in all dimensions, Trans. Amer. Math. Soc., 364, 5, 2667-2701 (2012), URL: www.jstor.org/stable/41524940 · Zbl 1238.60108
[5] Balogh, József; Bollobás, Béla; Morris, Robert, Bootstrap percolation in three dimensions, Ann. Probab., 37, 4, 1329-1380 (2009) · Zbl 1187.60082
[6] Balogh, József; Bollobás, Béla; Morris, Robert, Bootstrap percolation in high dimensions, Combin. Probab. Comput., 19, 5-6, 643-692 (2010) · Zbl 1263.60082
[7] Banerjee, Suman; Mathew, Rogers; Panolan, Fahad, Target set selection on graphs of bounded vertex cover number, CoRR abs/1812.01482 (2018), URL: http://arxiv.org/abs/1812.01482
[8] Barbosa, Rommel M.; Coelho, Erika M. M.; Dourado, Mitre C.; Rautenbach, Dieter; Szwarcfiter, Jayme L., On the Carathéodory number for the convexity of paths of order three, SIAM J. Discrete Math., 26, 3, 929-939 (2012) · Zbl 1256.05240
[9] Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian, Parameterized inapproximability of target set selection and generalizations, Computability, 3, 135-145 (2014) · Zbl 1320.68088
[10] Ben-Zwi, Oren; Hermelin, Danny; Lokshtanov, Daniel; Newman, Ilan, Treewidth governs the complexity of target set selection, Discrete Optim., 8, 87-96 (2011) · Zbl 1248.90068
[11] Benevides, Fabrício; Campos, Victor; Dourado, Mitre C.; Sampaio, Rudini M.; Silva, Ana, The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects, European J. Combin., 48, 88-99 (2015) · Zbl 1314.05195
[12] Benevides, Fabrício; Campos, Victor; Dourado, Mitre C.; Sampaio, Rudini M.; Silva, Ana, The maximum infection time in the geodesic and monophonic convexities, Theoret. Comput. Sci., 609, 287-295 (2016) · Zbl 1331.05201
[13] Benevides, Fabrício; Przykucki, Michał, On slowly percolating sets of minimal size in bootstrap percolation, Electron. J. Combin., 20, 2, 1-20 (2013) · Zbl 1298.05297
[14] Benevides, Fabrício; Przykucki, Michał, Maximum percolation time in two-dimensional bootstrap percolation, SIAM J. Discrete Math., 29, 1, 224-251 (2015) · Zbl 1371.60169
[15] Bessy, Stéphane; Ehard, Stefan; Penso, Lucia D.; Rautenbach, Dieter, Dynamic monopolies for interval graphs with bounded thresholds, Discrete Appl. Math., 260, 256-261 (2019) · Zbl 1409.05202
[16] Bueno, Letícia R.; Penso, Lucia D.; Protti, Fábio; Ramos, Victor R.; Rautenbach, Dieter; Souza, Uéverton S., On the hardness of finding the geodetic number of a subcubic graph, Inform. Process. Lett., 135, 22-27 (2018) · Zbl 1476.05041
[17] Centeno, Carmen C.; Dourado, Mitre C.; Penso, Lucia D.; Rautenbach, Dieter; Szwarcfiter, Jayme L., Irreversible conversion of graphs, Theoret. Comput. Sci., 412, 29, 3693-3700 (2011) · Zbl 1220.05109
[18] Chalupa, John; Leath, Paul Larry; Reich, Gary Robert, Bootstrap percolation on a bethe lattice, J. Phys. C: Solid State Phys., 12, 1, 31-35 (1979)
[19] Chang, Ching-Lueh; Lyuu, Yuh-Dauh, Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades, Theoret. Comput. Sci., 468, 37-49 (2013) · Zbl 1258.05041
[20] Chen, Ning, On the approximability of influence in social networks, SIAM J. Discrete Math., 23, 3, 1400-1415 (2009) · Zbl 1203.68314
[21] Chiang, Chun-Ying; Huang, Liang-Hao; Li, Bo-Jr; Wu, Jiaojiao; Yeh, Hong-Gwa, Some results on the target set selection problem, J. Comb. Optim., 25, 4, 702-715 (2013) · Zbl 1273.90224
[22] Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias, Constant thresholds can make target set selection tractable, Theory Comput. Syst., 55, 1, 61-83 (2014) · Zbl 1319.68109
[23] Cicalese, Ferdinando; Cordasco, Gennaro; Gargano, Luisa; Milanič, Martin; Peters, Joseph; Vaccaro, Ugo, Spread of influence in weighted networks under time and budget constraints, Theoret. Comput. Sci., 586, 40-58 (2015), Fun with Algorithms · Zbl 1327.68175
[24] Cicalese, Ferdinando; Cordasco, Gennaro; Gargano, Luisa; Milanič, Martin; Vaccaro, Ugo, Latency-bounded target set selection in social networks, Theoret. Comput. Sci., 535, 1-15 (2014) · Zbl 1358.05272
[25] Cordasco, Gennaro; Gargano, Luisa; Mecchia, Marco; Rescigno, Adele A.; Vaccaro, Ugo, Discovering small target sets in social networks: a fast and effective algorithm, Algorithmica, 80, 6, 1804-1833 (2018) · Zbl 1390.05224
[26] Costa, Eurinardo R.; Dourado, Mitre C.; Sampaio, Rudini M., Inapproximability results related to monophonic convexity, Discrete Appl. Math., 197, 70-74 (2015) · Zbl 1321.05128
[27] Courcelle, Bruno, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput., 85, 1, 12-75 (1990) · Zbl 0722.03008
[28] Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket, Parameterized Algorithms (2015), Springer · Zbl 1334.90001
[29] Dahlhaus, Elias; Johnson, David S.; Papadimitriou, Christos H.; Seymour, Paul D.; Yannakakis, Mihalis, The complexity of multiterminal cuts, SIAM J. Comput., 23, 4, 864-894 (1994) · Zbl 0809.68075
[30] Diestel, Reinhard, (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2012), Springer), URL: https://dblp.org/rec/books/daglib/0030488.bib
[31] Dourado, Mitre C.; Penso, Lucia D.; Rautenbach, Dieter, Geodetic convexity parameters for \(( q , q - 4 )\)-graphs, Discrete Appl. Math., 223, 64-71 (2017) · Zbl 1464.05333
[32] Downey, Rodney G.; Fellows, Michael R., (Fundamentals of Parameterized Complexity. Fundamentals of Parameterized Complexity, Texts in Computer Science (2013), Springer) · Zbl 1358.68006
[33] Dreyer, Paul A.; Roberts, Fred S., Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math., 157, 7, 1615-1627 (2009) · Zbl 1163.92035
[34] Duchet, Pierre, Convex sets in graphs, II. Minimal path convexity, J. Combin. Theory Ser. B, 44, 3, 307-316 (1988) · Zbl 0672.52001
[35] Dvorák, Pavel; Knop, Dusan; Toufar, Tomás, Target set selection in dense graph classes, (Hsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-Shou, 29th International Symposium on Algorithms and Computation. 29th International Symposium on Algorithms and Computation, ISAAC 2018. 29th International Symposium on Algorithms and Computation. 29th International Symposium on Algorithms and Computation, ISAAC 2018, Leibniz International Proceedings in Informatics (LIPIcs), vol. 123 (2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 18:1-18:13 · Zbl 1533.68234
[36] Ehard, Stefan; Rautenbach, Dieter, On some tractable and hard instances for partial incentives and target set selection, Discrete Optim., 34, Article 100547 pp. (2019) · Zbl 1506.91132
[37] Eppstein, David, Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 3, 275-291 (2000) · Zbl 0963.05128
[38] Erdős, Paul; Fried, Edrita; Hajnal, András; Milner, Eric C., Some remarks on simple tournaments, Algebra Universalis, 2, 238-245 (1972) · Zbl 0267.05104
[39] Farber, Martin; Jamison, Robert E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Methods, 7, 3, 433-444 (1986) · Zbl 0591.05056
[40] Grohe, Martin, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 23, 4, 613-632 (2003) · Zbl 1089.05503
[41] Harary, Frank; Nieminen, Juhani, Convexity in graphs, J. Differential Geom., 16, 2, 185-190 (1981) · Zbl 0493.05037
[42] Hartmann, Tim A., Target set selection parameterized by clique-width and maximum threshold, (Proc. of the 44th International Conference on Current Trends in Theory and Practice of Computer Science. Proc. of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM. Proc. of the 44th International Conference on Current Trends in Theory and Practice of Computer Science. Proc. of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM, LNCS, vol. 10706 (2018)), 137-149 · Zbl 1444.68144
[43] Holroyd, Alexander E., Sharp metastability threshold for two-dimensional bootstrap percolation, Probab. Theory Related Fields, 125, 2, 195-224 (2003) · Zbl 1042.60065
[44] Kempe, David; Kleinberg, Jon M.; Tardos, Éva, Maximizing the spread of influence through a social network, (Proc. of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2003)), 137-146
[45] Kempe, David; Kleinberg, Jon M.; Tardos, Éva, Maximizing the spread of influence through a social network, Theory Comput., 11, 105-147 (2015) · Zbl 1337.91069
[46] Khoshkhah, Kaveh; Soltani, Hossein; Zaker, Manouchehr, Dynamic monopolies in directed graphs: The spread of unilateral influence in social networks, Discrete Appl. Math., 171, 81-89 (1986) · Zbl 1288.05117
[47] Kynčl, Jan; Lidický, Bernard; Vyskočil, Tomáš, Irreversible 2-conversion set in graphs of bounded degree, Discrete Math. Theoret. Comput. Sci., 19, 3, 81-89 (2017) · Zbl 1401.05283
[48] Marcilon, Thiago Braga; Sampaio, Rudini M., The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree, Discrete Appl. Math., 251, 245-257 (2018) · Zbl 1401.05159
[49] Marcilon, Thiago Braga; Sampaio, Rudini M., The maximum time of 2-neighbor bootstrap percolation: Complexity results, Theoret. Comput. Sci., 708, 1-17 (2018) · Zbl 1383.05299
[50] Marcilon, Thiago Braga; Sampaio, Rudini M., The \(P_3\) infection time is W[1]-hard parameterized by the treewidth, Inform. Process. Lett., 132, 55-61 (2018) · Zbl 1427.68127
[51] Morris, Robert, Minimal percolating sets in bootstrap percolation, Electron. J. Combin., 16, R2, 1-20 (2003) · Zbl 1178.60070
[52] Nichterlein, André; Niedermeier, Rolf; Uhlmann, Johannes; Weller, Mathias, On tractable cases of target set selection, Soc. Netw. Anal. Min., 3, 2, 233-256 (2013) · Zbl 1310.68115
[53] Przykucki, Michał, Maximal percolation time in hypercubes under 2-bootstrap percolation, Electron. J. Combin., 19, 2, 1-13 (2012) · Zbl 1254.82017
[54] Riedl, Eric, Largest minimal percolating sets in hypercubes under 2-bootstrap percolation, Electron. J. Combin., 17, R80, 1-13 (2010) · Zbl 1228.60114
[55] Soltani, Hossein; Moazzez, Babak, A polyhedral study of dynamic monopolies, Ann. Oper. Res., 279, 1-2, 71-87 (2019) · Zbl 1434.90100
[56] Takaoka, Asahi; Ueno, Shuichi, A note on irreversible 2-conversion sets in subcubic graphs, IEICE Trans. Inf. Syst., E98.D, 8, 1589-1591 (2015)
[57] van de Vel, Marcel L. J., Theory of Convex Structures, Vol. 50 (1993), Elsevier · Zbl 0785.52001
[58] Zaker, Manouchehr, On dynamic monopolies of graphs with general thresholds, Discrete Math., 312, 6, 1136-1143 (2012) · Zbl 1238.05262
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.