Document Open Access Logo

Solving Target Set Selection with Bounded Thresholds Faster than 2^n

Authors Ivan Bliznets , Danil Sagunov

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.22.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Ivan Bliznets
  • St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia
Danil Sagunov
  • St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia

Funding

This research was supported by the Russian Science Foundation (project 16-11-10123)

Cite As Get BibTex

Ivan Bliznets and Danil Sagunov. Solving Target Set Selection with Bounded Thresholds Faster than 2^n. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.22

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^*((2-epsilon)^n) 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 l is W[1]-hard even when all thresholds are constant.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Branch-and-bound
Keywords
  • exact exponential algorithms
  • target set
  • vertex thresholds
  • social influence
  • irreversible conversions of graphs
  • bootstrap percolation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic, 73(3):235-276, June 1995. URL: http://dx.doi.org/10.1016/0168-0072(94)00034-z.
  2. Eyal Ackerman, Oren Ben-Zwi, and Guy Wolfovitz. Combinatorial model and bounds for target set selection. Theoretical Computer Science, 411(44-46):4017-4022, October 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.08.021.
  3. R.T. Araújo, R.M. Sampaio, and J.L. Szwarcfiter. The convexity of induced paths of order three. Electronic Notes in Discrete Mathematics, 44:109-114, November 2013. URL: http://dx.doi.org/10.1016/j.endm.2013.10.017.
  4. József Balogh, Béla Bollobás, and Robert Morris. Bootstrap percolation in high dimensions. Combinatorics, Probability and Computing, 19(5-6):643-692, 2010. Google Scholar
  5. Cristina Bazgan, Morgan Chopin, André Nichterlein, and Florian Sikora. Parameterized approximability of maximizing the spread of influence in networks. Journal of Discrete Algorithms, 27:54-65, July 2014. URL: http://dx.doi.org/10.1016/j.jda.2014.05.001.
  6. Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman. Treewidth governs the complexity of target set selection. Discrete Optimization, 8(1):87-96, February 2011. URL: http://dx.doi.org/10.1016/j.disopt.2010.09.007.
  7. Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, and Jakub Onufry Wojtaszczyk. Breaking the 2ⁿ-barrier for Irredundance: Two lines of attack. Journal of Discrete Algorithms, 9(3):214-230, September 2011. URL: http://dx.doi.org/10.1016/j.jda.2011.03.002.
  8. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling salesman problem in bounded degree graphs. ACM Transactions on Algorithms, 8(2):1-13, April 2012. URL: http://dx.doi.org/10.1145/2151171.2151181.
  9. Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. Largest Chordal and Interval Subgraphs Faster Than 2ⁿ. In Lecture Notes in Computer Science, pages 193-204. Springer Berlin Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_17.
  10. Carmen C. Centeno, Mitre C. Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L. Szwarcfiter. Irreversible conversion of graphs. Theoretical Computer Science, 412(29):3693-3700, July 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.03.029.
  11. Ning Chen. On the Approximability of Influence in Social Networks. SIAM Journal on Discrete Mathematics, 23(3):1400-1415, January 2009. URL: http://dx.doi.org/10.1137/08073617x.
  12. Morgan Chopin, André Nichterlein, Rolf Niedermeier, and Mathias Weller. Constant Thresholds Can Make Target Set Selection Tractable. Theory of Computing Systems, 55(1):61-83, September 2013. URL: http://dx.doi.org/10.1007/s00224-013-9499-3.
  13. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Scheduling Partially Ordered Jobs Faster than 2ⁿ. Algorithmica, 68(3):692-714, October 2012. URL: http://dx.doi.org/10.1007/s00453-012-9694-7.
  14. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2ⁿ. Algorithmica, 70(2):195-207, May 2013. URL: http://dx.doi.org/10.1007/s00453-013-9796-x.
  15. Marek Cygan, Marcin Pilipczuk, and Jakub Onufry Wojtaszczyk. Capacitated Domination Faster Than O(2ⁿ). In Lecture Notes in Computer Science, pages 74-80. Springer Berlin Heidelberg, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13731-0_8.
  16. Paul A. Dreyer Jr. and Fred S. Roberts. Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Applied Mathematics, 157(7):1615-1627, 2009. Google Scholar
  17. Pavel Dvořák, Dušan Knop, and Tomáš Toufar. Target Set Selection in Dense Graph Classes. arXiv preprint arXiv:1610.07530, 2016. Google Scholar
  18. Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon. On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica, 52(2):293-307, December 2007. URL: http://dx.doi.org/10.1007/s00453-007-9152-0.
  19. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. Solving Connected Dominating Set Faster than 2ⁿ. Algorithmica, 52(2):153-166, December 2007. URL: http://dx.doi.org/10.1007/s00453-007-9145-z.
  20. Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger. Enumerating Minimal Subset Feedback Vertex Sets. Algorithmica, 69(1):216-231, December 2012. URL: http://dx.doi.org/10.1007/s00453-012-9731-6.
  21. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer-Verlag, Berlin, Heidelberg, 1st edition, 2010. Google Scholar
  22. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Exact Algorithm for the Maximum Induced Planar Subgraph Problem. In Algorithms endash ESA 2011, pages 287-298. Springer Berlin Heidelberg, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_25.
  23. Tim A. Hartmann. Target Set Selection Parameterized by Clique-Width and Maximum Threshold. In SOFSEM 2018: Theory and Practice of Computer Science, pages 137-149. Springer International Publishing, December 2017. URL: http://dx.doi.org/10.1007/978-3-319-73117-9_10.
  24. David Kempe, Jon Kleinberg, and Éva 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 quotesingle03. ACM Press, 2003. URL: http://dx.doi.org/10.1145/956750.956769.
  25. Dániel Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394-406, February 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.10.007.
  26. André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, and Mathias Weller. On tractable cases of Target Set Selection. Social Network Analysis and Mining, 3(2):233-256, May 2012. URL: http://dx.doi.org/10.1007/s13278-012-0067-7.
  27. D. Peleg. Size bounds for dynamic monopolies. Discrete Applied Mathematics, 86(2-3):263-273, September 1998. URL: http://dx.doi.org/10.1016/s0166-218x(98)00043-2.
  28. Marcin Pilipczuk and Michał Pilipczuk. Finding a Maximum Induced Degenerate Subgraph Faster Than 2ⁿ. In Parameterized and Exact Computation, pages 3-12. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33293-7_3.
  29. Michał Pilipczuk. Exact Algorithms for Induced Subgraph Problems. In Encyclopedia of Algorithms, pages 1-5. Springer US, 2015. URL: http://dx.doi.org/10.1007/978-3-642-27848-8_520-1.
  30. Igor Razgon. Computing Minimum Directed Feedback Vertex Set in O^*(1.9977ⁿ). In Theoretical Computer Science, pages 70-81. World Scientific, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact