Document Open Access Logo

Target Set Selection in Dense Graph Classes

Authors Pavel Dvorák, Dusan Knop, Tomás Toufar

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.18.pdf
  • Filesize: 491 kB
  • 13 pages

Document Identifiers

Author Details

Pavel Dvorák
  • Computer Science Institute, Charles University, Prague, Czech Republic
Dusan Knop
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Berlin, Germany and Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Tomás Toufar
  • Computer Science Institute, Charles University, Prague, Czech Republic

Funding

  • Dvorák, Pavel: The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 616787.
  • Knop, Dusan: Part of this work has been done while affiliated with Department of Informatics, University of Bergen, Norway and supported by the project NFR MULTIVAL.

Cite As Get BibTex

Pavel Dvorák, Dusan Knop, and Tomás Toufar. Target Set Selection in Dense Graph Classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.18

Abstract

In this paper we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex the task is to find a set of vertices (called a target set) to activate at the beginning which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold.
We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph.
We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We show that the Target Set Selection problem parameterized by the neighborhood diversity when there is no restriction on the thresholds is W[1]-hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • parameterized complexity
  • target set selection
  • dense graphs

Metrics

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

Related Versions

References

  1. Eyal Ackerman, Oren Ben-Zwi, and Guy Wolfovitz. Combinatorial model and bounds for target set selection. Theoretical Computer Science, 411(44):4017-4022, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.08.021.
  2. József Balogh, Béla Bollobás, and Robert Morris. Bootstrap Percolation in High Dimensions. Combinatorics, Probability & Computing, 19(5-6):643-692, 2010. URL: http://dx.doi.org/10.1017/S0963548310000271.
  3. Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman. Treewidth governs the complexity of target set selection. Discrete Optimization, 8(1):87-96, 2011. Parameterized Complexity of Discrete Optimization. Google Scholar
  4. Ning Chen. On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, 23(3):1400-1415, 2009. Google Scholar
  5. Chun-Ying Chiang, Liang-Hao Huang, Bo-Jr Li, Jiaojiao Wu, and Hong-Gwa Yeh. Some results on the target set selection problem. Journal of Combinatorial Optimization, 25(4):702-715, 2013. URL: http://dx.doi.org/10.1007/s10878-012-9518-3.
  6. Morgan Chopin, André Nichterlein, Rolf Niedermeier, and Mathias Weller. Constant Thresholds Can Make Target Set Selection Tractable. Theory Comput. Syst., 55(1):61-83, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9499-3.
  7. Ferdinando Cicalese, Gennaro Cordasco, Luisa Gargano, Martin Milanič, Joseph Peters, and Ugo Vaccaro. Spread of influence in weighted networks under time and budget constraints. Theoretical Computer Science, 586:40-58, 2015. Google Scholar
  8. Ferdinando Cicalese, Gennaro Cordasco, Luisa Gargano, Martin Milanič, and Ugo Vaccaro. Latency-bounded target set selection in social networks. Theoretical Computer Science, 535:1-15, 2014. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  10. Pedro Domingos and Matt Richardson. Mining the network value of customers. In ACM SIGKDD, pages 57-66. ACM, 2001. Google Scholar
  11. 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. URL: http://dx.doi.org/10.1016/j.dam.2008.09.012.
  12. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. URL: http://dx.doi.org/10.1007/BF02579200.
  13. Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized Algorithms for Modular-Width. In IPEC 2013, pages 163-176, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_15.
  14. Robert Ganian. Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics. In IPEC 2011, pages 259-271, 2011. URL: http://dx.doi.org/10.1007/978-3-642-28050-4_21.
  15. Tim A. Hartmann. Target Set Selection Parameterized by Clique-Width and Maximum Threshold. In SOFSEM 2018, pages 137-149. Springer International Publishing, 2018. Google Scholar
  16. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In ACM SIGKDD, pages 137-146. ACM, 2003. Google Scholar
  17. Michael Lampis. Algorithmic Meta-theorems for Restrictions of Treewidth. Algorithmica, 64(1):19-37, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9554-x.
  18. Hendrik W. Lenstra, Jr. Integer Programming with a Fixed Number of Variables. Mathematics of Operations Research, 8(4):538-548, 1983. URL: http://dx.doi.org/10.1287/moor.8.4.538.
  19. André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, and Mathias Weller. On tractable cases of Target Set Selection. Social Netw. Analys. Mining, 3(2):233-256, 2013. URL: http://dx.doi.org/10.1007/s13278-012-0067-7.
  20. David Peleg. Local Majorities, Coalitions and Monopolies in Graphs: A Review. Theor. Comput. Sci., 282(2):231-257, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00055-X.
  21. Matthew Richardson and Pedro Domingos. Mining Knowledge-sharing Sites for Viral Marketing. In ACM SIGKDD, KDD '02, pages 61-70, New York, NY, USA, 2002. ACM. URL: http://dx.doi.org/10.1145/775047.775057.
  22. Marc Tedder, Dereck G. Corneil, Michel Habib, and Christophe Paul. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. In ICALP 2008, pages 634-645, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_52.
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