Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Distance Vector Domination

  • Conference paper
  • First Online:

Abstract

Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detect a set of individuals who, once immunized, can prevent the spreading of fake narratives. The considered problem, namedDistance Vector Domination generalizes both distance and multiple domination, at individual (i.e., vertex) level. We study the parameterized complexity of the problem according to several standard and structural parameters. We prove the W[1]-hardness of the problem with respect to neighborhood diversity, even when all the distances are 1. We also give fixed-parameter algorithms for some variants of the problem and parameter combinations.

Work partially supported by project SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7550
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9437
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Notes

  1. 1.

    For a positive integera, we use [a] to denote the set of integers\([a] = \{1, 2, \ldots , a\}\).

References

  1. Albert, R., Jeong, H., Barabási, A.-L.: Error and attack tolerance of complex networks. Nature404, 378–382 (2000)

    Article MATH  Google Scholar 

  2. Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth.8, 277–284 (1987)

    Article MathSciNet MATH  Google Scholar 

  3. Banerjee, S., Jenamani, M., Pratihar, D.K.: A survey on influence maximization in a social network. Knowl. Inf. Syst.62, 3417–3455 (2020).https://doi.org/10.1007/s10115-020-01461-4

    Article MATH  Google Scholar 

  4. Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discret. Optim.8(1), 87–96 (2011)

    Article MathSciNet MATH  Google Scholar 

  5. Bermond, J.-C., Gargano, L., Rescigno, A.A.: Gathering with minimum delay in tree sensor networks. In: Proceedings of SIROCCO’08, LNCS 5058, pp. 262–276 (2008)

    Google Scholar 

  6. Bodlaender, H.L., Kloks, T.: Better algorithms for the pathwidth and treewidth of graphs. In: Proceedings of ICALP’91, LNCS 510, pp. 544–555 (1991)

    Google Scholar 

  7. Betzler, N., Bredereck, R., Niedermeier, R., Uhlmann, J.: On Bounded-Degree Vertex Deletion parameterized by treewidth. Discret. Appl. Math.160(1–2), 53–60 (2012)

    Article MathSciNet MATH  Google Scholar 

  8. Borradaile, G., Le, H.: Optimal dynamic program for R-domination problems over tree decompositions. In: Proceedings of 11th International Symposium on Parameterized and Exact Computation, IPEC, LIPIcs, vol. 63, pp. 8:1–8:23 (2016)

    Google Scholar 

  9. Chong, C.-Y., Kumar, S.P.: Sensor networks: Evolution, opportunities, and challenges. Proc. IEEE91(8), 1247–1256 (2003)

    Article MATH  Google Scholar 

  10. Cicalese, F., Milanic, M., Vaccaro, U.: On the approximability and exact algorithms for vector domination and related problems in graphs. Discrete Appl. Math.161, 750–767 (2013)

    Article MathSciNet MATH  Google Scholar 

  11. Cicalese, F., Cordasco, G., Gargano, L., Milanic, M., Vaccaro, U.: Latency-bounded target set selection in social networks. Theoret. Comput. Sci.535, 1–15 (2014)

    Article MathSciNet MATH  Google Scholar 

  12. Cordasco, G., Gargano, L., Mecchia, M., Rescigno, A.A., Vaccaro, U.: A fast and effective heuristic for discovering small target sets in social networks. In: Proceedings of the 9th International Conference on Combinatorial Optimization and Applications (COCOA) (2015)

    Google Scholar 

  13. Cordasco, G., Gargano, L., Rescigno, A.A.: Influence propagation over large scale social networks. In: Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’15), pp. 1531–1538 (2015)

    Google Scholar 

  14. Cordasco, G., Gargano, L., Rescigno, A.A.: On finding small sets that influence large networks. Soc. Netw. Anal. Min.6(11) (2016)

    Google Scholar 

  15. Cordasco, G., Gargano, L., Mecchia, M., Rescigno, A.A., Vaccaro, U.: Discovering small target sets in social networks: a fast and effective algorithm. Algorithmica80(6), 1804–1833 (2018)

    Article MathSciNet MATH  Google Scholar 

  16. Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Evangelism in social networks: algorithms and complexity. Networks71(4), 346–357 (2018)

    Article MathSciNet MATH  Google Scholar 

  17. Cordasco, G., Gargano, L., Rescigno, A.A.: Active influence spreading in social networks. Theoret. Comput. Sci.764, 15–29 (2019)

    Article MathSciNet MATH  Google Scholar 

  18. Cordasco, G., et al.: Whom to befriend to influence people. Theoret. Comput. Sci.810, 26–42 (2020)

    Article MathSciNet MATH  Google Scholar 

  19. Cordasco, G., Gargano, L., Rescigno, A.A.: Parameterized complexity for iterated type partitions and modular-width. Discrete Appl. Math., 350 (2024)

    Google Scholar 

  20. Corneil, D., Habib, M., Paul, C., Tedder, M.: A recursive linear time modular decomposition algorithm via LexBFS.arXiv:0710.3901 [cs.DM] (2024)

  21. Courcelle, B.: The monadic second-order logic of graphs recognizable sets of finite graphs. Inform. Comput.85(1), 12–75 (1990)

    Article MathSciNet MATH  Google Scholar 

  22. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math.101(1), 77–114 (2000)

    Article MathSciNet MATH  Google Scholar 

  23. Cygan, M., et al.: Parameterized Algorithms. Springer International Publishing, Cham (2015).https://doi.org/10.1007/978-3-319-21275-3

    Book MATH  Google Scholar 

  24. Dasgupta, K., Kukreja, M., Kalpakis, K.: Topology-aware placement and role assignment for energy-efficient information gathering in sensor networks. In Proceedings of IEEE Symposium on Computers and Communications, pp. 341–348 (2003)

    Google Scholar 

  25. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999).https://doi.org/10.1007/978-1-4612-0515-9

    Book MATH  Google Scholar 

  26. Dvorák, P., Knop, D., Toufar, T.: Target set selection in dense graph classes. In: Proceedings of 29th International Symposium on Algorithms and Computation (ISAAC’18) (2018).https://doi.org/10.4230/LIPIcs.ISAAC.2018.18

  27. Fink, J.F., Jacobson, M.S.: n-Domination in Graphs. Graph Theory with Applications to Algorithms and Computer Science. John Wiley & Sons, pp. 283–300 (1985)

    Google Scholar 

  28. Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), LNCS 8246, pp. 163–176 (2013)

    Google Scholar 

  29. Gallai, T.: Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungarica18, 26–66 (1967)

    Article MathSciNet MATH  Google Scholar 

  30. Ganian, R.: Using Neighborhood Diversity to Solve Hard Problems. arXiv 2012 (2012).arXiv:1201.3091

  31. Granovetter, M.: Threshold models of collective behaviors. Am. J. Sociol.83(6), 1420–1443 (1978)

    Article MATH  Google Scholar 

  32. Goddard, W., Henning, M.A.: Restricted domination parameters in graphs. J. Comb. Optim.13, 353–363 (2007)

    Article MathSciNet MATH  Google Scholar 

  33. Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs, Marcel Dekker (1998)

    Google Scholar 

  34. Haynes, T.W., Hedetniemi, S., Slater, P. (Eds.). Domination in Graphs: Advanced Topics, Marcel Dekker (1998)

    Google Scholar 

  35. Harant, J., Prochnewski, A., Voigt, M.: On dominating sets and independent sets of graphs. Comb. Probab. Comput.8, 547–553 (1999)

    Article MathSciNet MATH  Google Scholar 

  36. Henning, M.A.: Distance domination in graphs. In: Topics in Domination in Graphs. Developments in Mathematics, vol. 64 (2020).https://doi.org/10.1007/978-3-030-51117-3_7

  37. Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci.62(2), 367–375 (2001).https://doi.org/10.1006/jcss.2000.1727

    Article MathSciNet MATH  Google Scholar 

  38. Ishii, T., Ono, H., Uno, Y.: (Total) Vector domination for graphs with bounded branchwidth. Discret. Appl. Math.207, 80–89 (2016)

    Article MathSciNet MATH  Google Scholar 

  39. Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for (k, r)-center. Discr. App. Math.264, 90–117 (2019)

    Article MathSciNet MATH  Google Scholar 

  40. Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of KDD’03, pp. 137–146 (2003)

    Google Scholar 

  41. Kimura, M., Saito, K., Motoda, H.: Blocking links to minimize contamination spread in a social network. ACM Trans. Knowl. Discov. Data3(2) (2009)

    Google Scholar 

  42. Kloks, T.: Treewidth Computations and Approximations. LNCS 842, Springer-Verlag Berlin, Heidelberg (1994). ISSN 0302-9743,https://doi.org/10.1007/BFb0045375

  43. Lafond, M., Luo, W.: Parameterized complexity of domination problems using restricted modular partitions. In: MFCS 2023, pp. 61:1–61:14 (2023)

    Google Scholar 

  44. Lamblet Mafort, R., Protti, F.: Vector Domination in split-indifference graphs. Inf. Process. Lett., 155 (2020). ISSN 0020-0190

    Google Scholar 

  45. Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica64, 19–37 (2012)

    Article MathSciNet MATH  Google Scholar 

  46. Newman, M.E.J., Forrest, S., Balthrop, J.: Email networks and the spread of computer viruses. Phys. Rev. E66 (2002)

    Google Scholar 

  47. Raman, V., Saurabh, S., Srihari, S.: Parameterized algorithms for generalized domination. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 116–126. Springer, Heidelberg (2008).https://doi.org/10.1007/978-3-540-85097-7_11

    Chapter MATH  Google Scholar 

  48. Romanek, M.: Parameterized algorithms for modular-width. Bachelor’s Thesis (2016)

    Google Scholar 

  49. Slater, P.J.: R-domination in graphs. J. Assoc. Comp. Mach.23(3), 446–450 (1976)

    Article MATH  Google Scholar 

  50. Li, P., Wang, A., Shang, J.: A simple optimal algorithm for k-tuple dominating problem in interval graphs. J. Comb. Optim.45(14) (2023)

    Google Scholar 

  51. Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica2, 385–393 (1982)

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Psychology, University of Campania “L.Vanvitelli”, Caserta, Italy

    Gennaro Cordasco

  2. Department of Computer Science, University of Salerno, Fisciano, Italy

    Luisa Gargano & Adele A. Rescigno

Authors
  1. Gennaro Cordasco

    You can also search for this author inPubMed Google Scholar

  2. Luisa Gargano

    You can also search for this author inPubMed Google Scholar

  3. Adele A. Rescigno

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toGennaro Cordasco.

Editor information

Editors and Affiliations

  1. Comenius University in Bratislava, Bratislava, Slovakia

    Rastislav Královič

  2. Czech Academy of Sciences, Prague, Czech Republic

    Věra Kůrková

Rights and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cordasco, G., Gargano, L., Rescigno, A.A. (2025). Distance Vector Domination. In: Královič, R., Kůrková, V. (eds) SOFSEM 2025: Theory and Practice of Computer Science. SOFSEM 2025. Lecture Notes in Computer Science, vol 15538. Springer, Cham. https://doi.org/10.1007/978-3-031-82670-2_14

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7550
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9437
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp