Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Motivated by applications in network epidemiology, we consider the problem of determining whether it is possible to delete at most k edges from a given input graph (of small treewidth) so that the resulting graph avoids a set \(\mathcal {F}\) of forbidden subgraphs; of particular interest is the problem of determining whether it is possible to delete at most k edges so that the resulting graph has no connected component of more than h vertices, as this bounds the worst-case size of an epidemic. While even this special case of the problem is NP-complete in general (even when \(h=3\)), we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the general problem in time \(2^{O(|\mathcal {F}|w^r)}n\) on an input graph having n vertices and whose treewidth is bounded by a fixed constant w, if each of the subgraphs we wish to avoid has at most r vertices. For the special case in which we wish only to ensure that no component has more than h vertices, we improve on this to give an algorithm running in time \(O((wh)^{2w}n)\), which we have implemented and tested on real datasets based on cattle movements.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. Available at treewidth.com/treewidth/index.html.

References

  1. Anderson, R., Gupta, S., Ng, W.: The significance of sexual partner contact networks for the transmission dynamics of HIV. J. Acquir. Immune Defic. Syndr. Hum. Retrovirol. 3, 417–429 (1990)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  3. Arnborg, S., Lagergren, J., Sesse, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308–340 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, pp. 226–234. ACM, New York (1993). doi:10.1145/167088.167161

  5. Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996). doi:10.1016/0020-0190(96)00050-6

    Article  MathSciNet  MATH  Google Scholar 

  6. Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109(12), 49–82 (1993). doi:10.1016/0304-3975(93)90064-Z

    Article  MathSciNet  MATH  Google Scholar 

  7. Drange, P.G., Dregi, M.S., van ’t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. In: Ahn, H.K., Shin, C.S. (eds.) Algorithms and Computation. Lecture Notes in Computer Science, pp. 285–297. Springer International Publishing, Berlin (2014). doi:10.1007/978-3-319-13075-023

    Google Scholar 

  8. El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst. 3, 354–362 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gao, Y.: Treewidth of Erdős–Renyi random graphs, random intersection graphs, and scale-free random graphs. Discret. Appl. Math. 160(45), 566–578 (2012). doi:10.1016/j.dam.2011.10.013

    Article  MATH  Google Scholar 

  10. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)

    MATH  Google Scholar 

  11. Gecode Team: Gecode: Generic constraint development environment (2016). http://www.gecode.org

  12. Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.: Faster parameterized algorithms for deletion to split graphs. In: Fomin, F., Kaski, P. (eds.) Algorithm Theory SWAT 2012. Lecture Notes in Computer Science, pp. 107–118. Springer, Berlin (2012). doi:10.1007/978-3-642-31155-010

    Chapter  Google Scholar 

  13. Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 139–152 (1993)

    Article  Google Scholar 

  14. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)

    MATH  Google Scholar 

  15. Gross, D., Heinig, M., Iswara, L., Kazmierczak, L.W., Luttrell, K., Saccoman, J.T., Suffel, C.: A survey of component order connectivity models of graph theoretic networks. SWEAS Trans. Math. 12(9), 895–910 (2013)

    Google Scholar 

  16. Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Tokuyama, T. (ed.) Algorithms and Computation. Lecture Notes in Computer Science, vol. 4835, pp. 915–926. Springer, Berlin (2007). doi:10.1007/978-3-540-77120-379

    Chapter  Google Scholar 

  17. Kao, R.R., Green, D.M., Johnson, J., Kiss, I.Z.: Disease dynamics over very different time-scales: foot-and-mouth disease and scrapie on the network of livestock movements in the UK. J. R. Soc. Interface 4(16), 907–916 (2007). doi:10.1098/rsif.2007.1129

    Article  Google Scholar 

  18. Kloks, T., Treewidth, T.: Computations and Approximations. Lecture Notes in Computer Science. Springer, Berlin (1994). doi:10.1007/BFb0045375

    Google Scholar 

  19. Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980). doi:10.1016/0022-0000(80)90060-4

    Article  MathSciNet  MATH  Google Scholar 

  20. Li, A., Tang, L.: The complexity and approximability of minimum contamination problems. In: Ogihara, M., Tarui, J. (eds.) Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 6648, pp. 298–307. Springer, Berlin (2011). doi:10.1007/978-3-642-20877-5_30

    Chapter  Google Scholar 

  21. Margot, F.: Some complexity results about threshold graphs. Discret. Appl. Math. 49(1:3), 299–308 (1994). doi:10.1016/0166-218X(94)90214-3

    Article  MathSciNet  MATH  Google Scholar 

  22. Mitchell, A., Bourn, D., Mawdsley, J., Wint, W., Clifton-Hadley, R., Gilbert, M.: Characteristics of cattle movements in britain: an analysis of records from the cattle tracing system. Anim. Sci. 80, 265–273 (2005). doi:10.1079/ASC50020265

    Article  Google Scholar 

  23. Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discret. Appl. Math. 113(1), 109–128 (2001). doi:10.1016/S0166-218X(00)00391-7

    Article  MathSciNet  MATH  Google Scholar 

  24. Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming. CP’07, pp. 529–543. Springer, Berlin (2007)

  25. Prud’homme, C., Fages, J-G., Lorca, X.: Choco documentation (2016). http://www.choco-solver.org

  26. Robertson, N., Seymour, P.: Graph minors. III. planar tree-width. J. Comb. Theory Ser. B 36(1), 49–64 (1984). doi:10.1016/0095-8956(84)90013-3. http://www.sciencedirect.com/science/article/pii/0095895684900133

  27. Schulte, C., Tack, G., Lagerkvist, M.Z.: Modeling and programming with Gecode (2013). http://www.gecode.org

  28. Stuckey, P.J., Feydy, T., Schutt, A., Tack, G., Fischer, J.: The minizinc challenge 2008–2013. AI Mag. 35(2), 55–60 (2014)

    Article  Google Scholar 

  29. van Dijk, T., van den Heuvel, J.P., Slob, W.: Computing treewidth with LibTW (2006)

  30. Watanabe, T., Ae, T., Nakamura, A.: On the NP-hardness of edge-deletion and -contraction problems. Discret. Appl. Math. 6(1), 63–78 (1983). doi:10.1016/0166-218X(83)90101-4

    Article  MathSciNet  MATH  Google Scholar 

  31. Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, pp. 253–264. ACM, New York (1978). doi:10.1145/800133.804355

Download references

Acknowledgements

The authors would like to thank the following: Ivaylo Valkov for his assistance in developing an initial implementation of this algorithm as part of a summer research project, and the Engineering and Physical Sciences Research Council for providing funding for this summer project; EPIC: Scotland’s Centre of Expertise on Animal Disease Outbreaks, which supported JE for part of her work on this project; the Royal Society of Edinburgh which supported KM for part of her work on this project through a Personal Research Fellowship funded by the Scottish Government; Ciaran McCreesh and Patrick Prosser for their assistance in developing the CP formulation against which we compared the performance of our algorithm.

Author information

Authors and Affiliations

  1. Computing Science and Mathematics, University of Stirling, Stirling, FK9 4LA, UK

    Jessica Enright

  2. School of Computing Science, Sir Alwyn Williams Building, University of Glasgow, Glasgow, G12 8RZ, UK

    Kitty Meeks

Authors
  1. Jessica Enright
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kitty Meeks
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kitty Meeks.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Enright, J., Meeks, K. Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth. Algorithmica 80, 1857–1889 (2018). https://doi.org/10.1007/s00453-017-0311-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-017-0311-7

Keywords

Search

Navigation