[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

On integer and bilevel formulations for the k-vertex cut problem

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

The family of critical node detection problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problem asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. A hereditary property is a property of a graph which also holds for its induced subgraphs.

References

  1. Balas, E., de Souza, C.C.: The vertex separator problem: a polyhedral investigation. Math. Program. 103(3), 583–608 (2005)

    MathSciNet  MATH  Google Scholar 

  2. Barahona, F.: On the k-cut problem. Oper. Res. Lett. 26(3), 99–105 (2000)

    MathSciNet  MATH  Google Scholar 

  3. Bastubbe, M., Lübbecke, M.: A branch-and-price algorithm for capacitated hypergraph vertex separation. Technical Report, Optimization (2017)

  4. Ben-Ameur, W., Biha, M.D.: On the minimum cut separator problem. Networks 59(1), 30–36 (2012)

    MathSciNet  MATH  Google Scholar 

  5. Ben-Ameur, W., Mohamed-Sidi, M.A., Neto, J.: The k-separator problem. In: Computing and Combinatorics, pp. 337–348 (2013)

    Google Scholar 

  6. Berger, A., Grigoriev, A., v. d. Zwaan, R.: Complexity and approximability of the k-way vertex cut. Networks 63(2), 170–178 (2014)

    MathSciNet  MATH  Google Scholar 

  7. Borndörfer, R., Ferreira, C., Martin, A.: Decomposing matrices into blocks. SIAM J. Optim. 9(1), 236–269 (1998)

    MathSciNet  MATH  Google Scholar 

  8. Brown, G., Carlyle, M., Salmerón, J., Wood, K.: Defending critical infrastructure. INFORMS J. Appl. Anal. 36(6), 530–544 (2006)

    Google Scholar 

  9. Bui, T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inf. Process. Lett. 42(3), 153–159 (1992)

    MathSciNet  MATH  Google Scholar 

  10. Chopra, S., Rao, M.R.: On the multiway cut polyhedron. Networks 21(1), 51–89 (1991)

    MathSciNet  MATH  Google Scholar 

  11. Color02/03/04: graph coloring and its generalizations. http://mat.gsia.cmu.edu/COLOR03/. Accessed 20 July 2018

  12. Cornaz, D., Furini, F., Lacroix, M., Malaguti, E., Mahjoub, A.R., Martin, S.: The vertex \(k\)-cut problem. Discrete Optim. 31, 8–28 (2019)

    MathSciNet  MATH  Google Scholar 

  13. Cornaz, D., Magnouche, Y., Mahjoub, A.R., Martin, S.: The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut. In: Conference on Computers and Industrial Engineering (CIE45), pp. 857–864 (2015)

  14. Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakiss, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994)

    MathSciNet  MATH  Google Scholar 

  15. Dimacs implementation challenges. http://dimacs.rutgers.edu/archive/Challenges/. Accessed 20 July 2018

  16. de Souza, C., Balas, E.: The vertex separator problem: algorithms and computations. Math. Program. 103(3), 609–631 (2005)

    MathSciNet  MATH  Google Scholar 

  17. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)

    MathSciNet  MATH  Google Scholar 

  18. Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: Interdiction games under monotonicity. INFORMS J. Comput. 31(2), 390–410 (2019)

    MathSciNet  Google Scholar 

  19. Fukuyama, J.: NP-completeness of the planar separator problems. J. Gr. Algorithms Appl. 10(2), 317–328 (2006)

    MathSciNet  MATH  Google Scholar 

  20. Furini, F., Ljubić, I., San Segundo, P., Martin, S.: The maximum clique interdiction problem. Eur. J. Oper. Res. 277(1), 112–127 (2019)

    MathSciNet  MATH  Google Scholar 

  21. Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Automata, Languages and Programming, pp. 487–498 (1994)

    MATH  Google Scholar 

  22. Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49–61 (2004)

    MathSciNet  MATH  Google Scholar 

  23. Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24–37 (1994)

    MathSciNet  MATH  Google Scholar 

  24. Gupta, A., Lee, E., Li, J.: An FPT algorithm beating 2-approximation for \(k\)-cut. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp. 2821–2837 (2018)

  25. Karger, D.R., Motwani, R.: An NC algorithm for minimum cuts. SIAM J. Comput. 26(1), 255–272 (1997)

    MathSciNet  MATH  Google Scholar 

  26. Kempe, D., Kleinberg, J., Tardos, É.: Influential nodes in a diffusion model for social networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) Automata, Languages and Programming, pp. 1127–1138. Springer, Berlin (2005)

    Google Scholar 

  27. Lalou, M., Tahraoui, M.A., Kheddouci, H.: The critical node detection problem in networks: a survey. Comput. Sci. Rev. 28, 92–117 (2018)

    MathSciNet  MATH  Google Scholar 

  28. Magnouche, J.: The Multi-terminal Vertex Separator Problem: Complexity, Polyhedra and Algorithms (2017)

  29. Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394–406 (2006)

    MathSciNet  MATH  Google Scholar 

  30. Saran, H., Vazirani, V.: Finding \(k\) cuts within twice the optimal. SIAM J. Comput. 24(1), 101–108 (1995)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are indebted to two anonymous referees and one technical editor for their constructive and useful comments. Enrico Malaguti is supported by the Air Force Office of Scientific Research under Award Number FA9550-17-1-0025

Author information

Authors and Affiliations

  1. LAMSADE, Université Paris-Dauphine, Paris, France

    Fabio Furini

  2. ESSEC Business School of Paris, Cergy, France

    Ivana Ljubić

  3. DEI, University of Bologna, Bologna, Italy

    Enrico Malaguti & Paolo Paronuzzi

Authors
  1. Fabio Furini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ivana Ljubić
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Enrico Malaguti
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Paolo Paronuzzi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ivana Ljubić.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 194 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Furini, F., Ljubić, I., Malaguti, E. et al. On integer and bilevel formulations for the k-vertex cut problem. Math. Prog. Comp. 12, 133–164 (2020). https://doi.org/10.1007/s12532-019-00167-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-019-00167-1

Keywords

Mathematics Subject Classification

Search

Navigation