×

Solving target set selection with bounded thresholds faster than \(2^n\). (English) Zbl 1507.68223

Summary: 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 \(\operatorname{thr}: V(G) \rightarrow {\mathbb{N}} \cup \{0\}\) and two integers \(k\), \(\ell \). The goal of the problem is to activate at most \(k\) vertices initially so that at the end of the activation process there are at least \(\ell\) activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever; (ii) a vertex \(v\) becomes activated if at least \(\operatorname{thr}(v)\) of its neighbours are activated. The problem and its different special cases were extensively studied from the 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 \({\mathcal{O}}^*\left( (2-\epsilon )^n\right)\) time for some \(\epsilon >0\). We partially answer this question by presenting several faster-than-trivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by one-third of its degree. Also, we show that the problem parameterized by \(\ell\) is \(\mathrm{W}[1]\)-hard even when all thresholds are constant.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68Q27 Parameterized complexity, tractability and kernelization
Full Text: DOI

References:

[1] Abrahamson, KA; Downey, RG; Fellows, MR, Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues, Ann. Pure Appl. Logic, 73, 3, 235-276 (1995) · Zbl 0828.68077 · doi:10.1016/0168-0072(94)00034-z
[2] Ackerman, E.; Ben-Zwi, O.; Wolfovitz, G., Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411, 44-46, 4017-4022 (2010) · Zbl 1235.90168 · doi:10.1016/j.tcs.2010.08.021
[3] Araújo, R.; Sampaio, R.; Szwarcfiter, J., The convexity of induced paths of order three, Electron. Notes Discrete Math., 44, 109-114 (2013) · doi:10.1016/j.endm.2013.10.017
[4] Ash, R., Information Theory. Dover Books on Mathematics (1990), Mineola, NY: Dover Publications, Mineola, NY · Zbl 0768.94005
[5] Balogh, J.; Bollobás, B.; Morris, R., Bootstrap percolation in high dimensions, Comb. Probab. Comput., 19, 5-6, 643-692 (2010) · Zbl 1263.60082 · doi:10.1017/S0963548310000271
[6] Bazgan, C.; Chopin, M.; Nichterlein, A.; Sikora, F., Parameterized approximability of maximizing the spread of influence in networks, J. Discret. Algorithms, 27, 54-65 (2014) · Zbl 1361.68105 · doi:10.1016/j.jda.2014.05.001
[7] Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discret. Optim., 8, 1, 87-96 (2011) · Zbl 1248.90068 · doi:10.1016/j.disopt.2010.09.007
[8] Binkele-Raible, D.; Brankovic, L.; Cygan, M.; Fernau, H.; Kneis, J.; Kratsch, D.; Langer, A.; Liedloff, M.; Pilipczuk, M.; Rossmanith, P.; Wojtaszczyk, JO, Breaking the \(2^n\)-barrier for Irredundance: Two lines of attack, J. Discret. Algorithms, 9, 3, 214-230 (2011) · Zbl 1225.05227 · doi:10.1016/j.jda.2011.03.002
[9] Björklund, A.; Husfeldt, T.; Kaski, P.; Koivisto, M., The traveling salesman problem in bounded degree graphs, ACM Trans. Algorithms, 8, 2, 1-13 (2012) · Zbl 1295.90060 · doi:10.1145/2151171.2151181
[10] Bliznets, I., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Largest Chordal and Interval Subgraphs Faster Than \(2^n\). In: Lecture Notes in Computer Science, pp. 193-204. Springer Berlin Heidelberg (2013). doi:10.1007/978-3-642-40450-4_17 · Zbl 1394.68164
[11] Centeno, CC; Dourado, MC; Penso, LD; Rautenbach, D.; Szwarcfiter, JL, Irreversible conversion of graphs, Theoret. Comput. Sci., 412, 29, 3693-3700 (2011) · Zbl 1220.05109 · doi:10.1016/j.tcs.2011.03.029
[12] Chen, N., On the Approximability of Influence in Social Networks, SIAM J. Discret. Math., 23, 3, 1400-1415 (2009) · Zbl 1203.68314 · doi:10.1137/08073617x
[13] Chopin, M.; Nichterlein, A.; Niedermeier, R.; Weller, M., Constant Thresholds Can Make Target Set Selection Tractable, Theor. Comput. Syst., 55, 1, 61-83 (2013) · Zbl 1319.68109 · doi:10.1007/s00224-013-9499-3
[14] Cygan, M.; Pilipczuk, M.; Pilipczuk, M.; Wojtaszczyk, JO, Scheduling Partially Ordered Jobs Faster than \(2^n\), Algorithmica, 68, 3, 692-714 (2012) · Zbl 1360.90124 · doi:10.1007/s00453-012-9694-7
[15] Cygan, M.; Pilipczuk, M.; Pilipczuk, M.; Wojtaszczyk, JO, Solving the 2-Disjoint Connected Subgraphs Problem Faster than \(2^n\), Algorithmica, 70, 2, 195-207 (2013) · Zbl 1306.05125 · doi:10.1007/s00453-013-9796-x
[16] Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated Domination Faster Than \(O(2^n)\). In: Lecture Notes in Computer Science, pp. 74-80. Springer Berlin Heidelberg (2010). doi:10.1007/978-3-642-13731-0_8 · Zbl 1285.68063
[17] Dreyer, PA Jr; Roberts, FS, Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discret. Appl. Math., 157, 7, 1615-1627 (2009) · Zbl 1163.92035 · doi:10.1016/j.dam.2008.09.012
[18] Dvořák, P., Knop, D., Toufar, T.: Target Set Selection in Dense Graph Classes. arXiv preprint arXiv:1610.07530 (2016) · Zbl 1533.68234
[19] Fomin, FV; Gaspers, S.; Pyatkin, AV; Razgon, I., On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms, Algorithmica, 52, 2, 293-307 (2007) · Zbl 1170.68029 · doi:10.1007/s00453-007-9152-0
[20] Fomin, FV; Grandoni, F.; Kratsch, D., Solving Connected Dominating Set Faster than \(2^n\), Algorithmica, 52, 2, 153-166 (2007) · Zbl 1170.68030 · doi:10.1007/s00453-007-9145-z
[21] Fomin, FV; Heggernes, P.; Kratsch, D.; Papadopoulos, C.; Villanger, Y., Enumerating Minimal Subset Feedback Vertex Sets, Algorithmica, 69, 1, 216-231 (2012) · Zbl 1303.05189 · doi:10.1007/s00453-012-9731-6
[22] Fomin, FV; Kratsch, D., Exact Exponential Algorithms (2010), Berlin, Heidelberg: Springer-Verlag, Berlin, Heidelberg · Zbl 1370.68002 · doi:10.1007/978-3-642-16533-7
[23] Fomin, F.V., Todinca, I., Villanger, Y.: Exact Algorithm for the Maximum Induced Planar Subgraph Problem. In: Algorithms - ESA 2011, pp. 287-298. Springer Berlin Heidelberg (2011). doi:10.1007/978-3-642-23719-5_25 · Zbl 1346.05283
[24] Hartmann, T.A.: Target Set Selection Parameterized by Clique-Width and Maximum Threshold. In: SOFSEM 2018: Theory and Practice of Computer Science, pp. 137-149. Springer International Publishing (2017). 1doi:10.1007/978-3-319-73117-9_10 · Zbl 1444.68144
[25] Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’03. ACM Press (2003). doi:10.1145/956750.956769 · Zbl 1337.91069
[26] Marx, D., Parameterized graph separation problems, Theoret. Comput. Sci., 351, 3, 394-406 (2006) · Zbl 1086.68104 · doi:10.1016/j.tcs.2005.10.007
[27] Nichterlein, A.; Niedermeier, R.; Uhlmann, J.; Weller, M., On tractable cases of Target Set Selection, Soc. Netw. Anal. Min., 3, 2, 233-256 (2012) · doi:10.1007/s13278-012-0067-7
[28] Peleg, D., Size bounds for dynamic monopolies, Discret. Appl. Math., 86, 2-3, 263-273 (1998) · Zbl 0910.90286 · doi:10.1016/s0166-218x(98)00043-2
[29] Pilipczuk, M.: Exact Algorithms for Induced Subgraph Problems. In: Encyclopedia of Algorithms, pp. 1-5. Springer US (2015). doi:10.1007/978-3-642-27848-8_520-1
[30] Pilipczuk, M., Pilipczuk, M.: Finding a Maximum Induced Degenerate Subgraph Faster Than \(2^n\). In: Parameterized and Exact Computation, pp. 3-12. Springer Berlin Heidelberg (2012). doi:10.1007/978-3-642-33293-7_3 · Zbl 1374.68726
[31] Razgon, I.: Computing Minimum Directed Feedback Vertex Set in \(O^*(1.9977^n)\). In: Theoretical Computer Science, pp. 70-81. World Scientific (2007)
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.