[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations

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

Abstract

This paper explores integer programming formulations for solving graph partitioning problems that impose an upper limit on the weight of the partition clusters. Traditional efforts have concentrated on studying a model commonly known as the triangular formulation, which has some undesirable properties, like requiring a cubic number of constraints with respect to the number of vertices. We study some alternative formulations arising from different perspectives. In particular, we consider the idea of modeling the problem from the standpoint of an attacker who wants to deteriorate the graph’s integrity by removing edges and show that some of the structural properties of the proposed formulations can be exploited to speed up the solution times. To compare the strength of the formulations’ LP bounds, we study their projection into the space of the edges and show that all of them concentrate on partitioning subtrees of the input graph. Inspired by this observation, we develop a formulation based on a dynamic program for the problem on trees and show how to use it to derive strong valid inequalities for the problem on general graphs. As part of the technical developments of the paper, we also expand the polyhedral characterization of the problem’s solution space, introducing new families of inequalities and provide empirical evidence of their efficacy to improve the quality of the proposed formulations. Finally, we conduct an extensive computational study to compare the strength of our developments.

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
Fig. 3
Fig. 4

Similar content being viewed by others

Data availability statement

This manuscript has associated data in a data repository. See the reference [61] in the paper.

Code availability

This manuscript has associated code in a repository. See the reference [61].

Notes

  1. Throughout the paper, we denote \(\left( {\begin{array}{c}V\\ k\end{array}}\right) \) the set of all k-element subsets of V.

References

  1. Abusorrah, A., Alabdulwahab, A., Li, Z., Shahidehpour, M.: Minimax-regret robust defensive strategy against false data injection attacks. IEEE Trans. Smart Grid 10(2), 2068–2079 (2017)

    Article  Google Scholar 

  2. Achterberg, T.: Constraint integer programming. PhD thesis, Technische Universität Berlin (2007)

  3. Agasi, E., Becker, R.I., Perl, Y.: A shifting algorithm for constrained min–max partition on trees. Discrete Appl. Math. 45(1), 1–28 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Englewood Cliffs (1988)

    Book  MATH  Google Scholar 

  5. Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  6. Ales, Z., Knippel, A.: The \(k\)-partitioning problem: formulations and branch-and-cut. Networks 76(3), 323–349 (2020)

    Article  MathSciNet  Google Scholar 

  7. Andreev, K., Racke, H.: Balanced graph partitioning. Theory Comput. Syst. 39(6), 929–939 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Aringhieri, R., Grosso, A., Hosteins, P., Scatamacchia, R.: Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem. Discrete Appl. Math. 253, 103–121 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  9. Arulselvan, A., Commander, C.W., Elefteriadou, L., Pardalos, P.M.: Detecting critical nodes in sparse graphs. Comput. Oper. Res. 36(7), 2193–2200 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Balas, E., Fischetti, M.: On the monotonization of polyhedra. Math. Program. 78(1), 59–84 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  11. Balas, E., Ng, S.M.: On the set covering polytope: I. All the facets with coefficients in 0, 1, 2. Math. Program. 43(3), 57–69 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Wiley, Hoboken (2008)

    MATH  Google Scholar 

  13. Bertolazzi, P., Lucertini, M., Spaccamela, A.M.: Analysis of a class of graph partitioning problems. RAIRO. Informatique théorique 16(3), 255–261 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  14. Buchin, M., Selbach, L.: A polynomial-time partitioning algorithm for weighted cactus graphs (2020). arXiv:2001.00204

  15. Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering: Selected Results and Surveys, pp. 117–158. Springer, Berlin (2016)

    Chapter  Google Scholar 

  16. Carr, R.D., Lancia, G.: Compact vs. exponential-size lp relaxations. Oper. Res. Lett. 30(1), 57–65 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  17. Chen, J., Yuan, B.: Detecting functional modules in the yeast protein–protein interaction network. Bioinformatics 22(18), 2283–2290 (2006)

    Article  Google Scholar 

  18. Chopra, S.: The graph partitioning polytope on series-parallel and 4-wheel free graphs. SIAM J. Discrete Math. 7(1), 16–31 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  19. Chopra, S., Rao, M.R.: The partition problem. Math. Program. 59(1–3), 87–115 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  20. Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4), 305–337 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  21. Chvátal, V., Cook, W.: The discipline number of a graph. Discrete Math. 86(1–3), 191–198 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  22. Conforti, M., Rao, M.R., Sassano, A.: The equipartition polytope. I: formulations, dimension and basic facets. Math. Program. 49(1–3), 49–70 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  23. Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR Q. J. Oper. Res. 8(1), 1–48 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  24. Cunningham, W.H., Green-Krotki, J.: Dominants and submissives of matching polyhedra. Math. Program. 36(2), 228–237 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  25. D’Amico, S.J., Wang, S.-J., Batta, R., Rump, C.M.: A simulated annealing approach to police district design. Comput. Oper. Res. 29(6), 667–684 (2002)

    Article  MATH  Google Scholar 

  26. Deo, N.: Graph Theory with Applications to Engineering and Computer Science. Courier Dover Publications, Mineola (2017)

    MATH  Google Scholar 

  27. Di Summa, M., Grosso, A., Locatelli, M.: Branch and cut algorithms for detecting critical nodes in undirected graphs. Comput. Optim. Appl. 53(3), 649–680 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  28. Erdös, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5(1), 17–60 (1960)

    MathSciNet  MATH  Google Scholar 

  29. Faigle, U., Schrader, R., Suletzki, R.: A cutting plane algorithm for optimal graph partitioning. Methods Oper. Res. 57, 109–116 (1987)

    MathSciNet  MATH  Google Scholar 

  30. Ferreira, C.E., Martin, A., de Souza, C.C., Weismantel, R., Wolsey, L.A.: Formulations and valid inequalities for the node capacitated graph partitioning problem. Math. Program. 74(3), 247–266 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  31. Ferreira, C.E., Martin, A., de Souza, C.C., Weismantel, R., Wolsey, L.A.: The node capacitated graph partitioning problem: a computational study. Math. Program. 81(2), 229–256 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  32. Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)

    Article  MathSciNet  Google Scholar 

  33. Frangioni, A., Lodi, A., Rinaldi, G.: Optimizing over semimetric polytopes. In: Bienstock, D., Nemhauser, G. (eds.) Integer Programming and Combinatorial Optimization, pp. 431–443. Springer, Berlin (2004)

    Chapter  Google Scholar 

  34. Frangioni, A., Lodi, A., Rinaldi, G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2–3), 375–388 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  35. Gomory, R.E.: An algorithm for integer solutions to linear programs. Recent Adv. Math. Program. 64(260–302), 14 (1963)

    MATH  Google Scholar 

  36. Grötschel, M., Wakabayashi, Y.: A cutting plane algorithm for a clustering problem. Math. Program. 45(1–3), 59–96 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  37. Grötschel, M., Wakabayashi, Y.: Facets of the clique partitioning polytope. Math. Program. 47(1–3), 367–387 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  38. Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  39. Hojny, C., Joormann, I., Lüthen, H., Schmidt, M.: Mixed-integer programming techniques for the connected max-\(k\)-cut problem. Math. Program. Comput. 13(1), 75–132 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  40. Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16, 372–378 (1973)

    Article  Google Scholar 

  41. Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks 40(2), 97–111 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  42. Ito, T., Nishizeki, T., Schröder, M., Uno, T., Zhou, X.: Partitioning a weighted tree into subtrees with weights in a given range. Algorithmica 62(3), 823–841 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  43. Johnson, E.L., Mehrotra, A., Nemhauser, G.L.: Min-cut clustering. Math. Programm. 62(1–3), 133–151 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  44. Kahng, A.B., Lienig, J., Markov, I.L., Hu, J.: VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, Berlin (2011)

    Book  MATH  Google Scholar 

  45. Kundu, S., Misra, J.: A linear tree partitioning algorithm. SIAM J. Comput. 6(1), 151–154 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  46. Labbé, M., Özsoy, F.A.: Size-constrained graph partitioning polytopes. Discrete Math. 310(24), 3473–3493 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  47. Laurent, M., Deza, M., Grötschel, M.: Complete descriptions of small multicut polytopes. In: Gritzmann, P., Sturmfels, B., Klee, V. (eds.) Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, vol. 4, pp. 221–252. American Mathematical Soc., Providence (1991)

    Google Scholar 

  48. Liu, X., Li, Z., Li, Z.: Optimal protection strategy against false data injection attacks in power systems. IEEE Trans. Smart Grid 8(4), 1802–1810 (2016)

    Article  Google Scholar 

  49. Lozovanu, D., Zelikovsky, A.: Minimal and bounded tree problems. Tezele Congresului XVIII al Academiei Romano-Americane, Kishniev, p. 25 (1993)

  50. Lukes, J.A.: Efficient algorithm for the partitioning of trees. IBM J. Res. Dev. 18(3), 217–224 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  51. Mahdavi Pajouh, F., Boginski, V., Pasiliao, E.L.: Minimum vertex blocker clique problem. Networks 64(1), 48–64 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  52. Mahdavi Pajouh, F., Walteros, J.L., Boginski, V., Pasiliao, E.L.: Minimum edge blocker dominating set problem. Eur. J. Oper. Res. 247(1), 16–26 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  53. Mehrotra, A., Trick, M.A.: Cliques and clustering: A combinatorial approach. Oper. Res. Lett. 22(1), 1–12 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  54. Mittelmann, H.: Benchmarks for optimization software (2018). http://plato.asu.edu/bench.html. Last accessed May 2021

  55. Myung, Y.-S., Kim, H.-J.: A cutting plane algorithm for computing k-edge survivability of a network. Eur. J. Oper. Res. 156(3), 579–589 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  56. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)

    Book  MATH  Google Scholar 

  57. Newman, M.E.J.: Community detection and graph partitioning. Europhys. Lett. 103(2), 28003 (2013)

    Article  Google Scholar 

  58. Nguyen, D.P., Minoux, M., Nguyen, V.H., Nguyen, T.H., Sirdey, R.: Improved compact formulations for a wide class of graph partitioning problems in sparse graphs. Discrete Optim. 25, 175–188 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  59. Oosten, M., Rutten, J.H.G.C., Spieksma, F.C.R.: The clique partitioning problem: facets and patching facets. Netw. Int. J. 38(4), 209–226 (2001)

    MathSciNet  MATH  Google Scholar 

  60. Oosten, M., Rutten, J.H.G.C., Spieksma, F.C.R.: Disconnecting graphs by removing vertices: a polyhedral approach. Stat. Neerl. 61(1), 35–60 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  61. Papazaharias, D.V., Walteros, J.L.: Solving graph partitioning problems on sparse graphs. Implementation (2022). https://doi.org/10.5281/zenodo.7114648

    Article  Google Scholar 

  62. Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). http://networkrepository.com

  63. Salemi, H., Buchanan, A.: Solving the distance-based critical node problem. INFORMS J. Comput. 34(3), 1309–1326 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  64. Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007)

    Article  MATH  Google Scholar 

  65. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)

    MATH  Google Scholar 

  66. Shen, S., Smith, J.C.: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks 60(2), 103–119 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  67. Shen, S., Smith, J.C., Goli, R.: Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optim. 9(3), 172–188 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  68. Sherali, H.D., Lunday, B.J.: On generating maximal nondominated benders cuts. Ann. Oper. Res. 210(1), 57–72 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  69. Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888–905 (2000)

    Article  Google Scholar 

  70. Smith, J.C., Song, Y.: A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3), 797–811 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  71. Sørensen, M.M.: A polyhedral approach to graph partitioning. PhD thesis, Aarhus School of Business (1995)

  72. Sørensen, M.M.: \(b\)-tree facets for the simple graph partitioning polytope. J. Comb. Optim. 8(2), 151–170 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  73. Sørensen, M.M.: Polyhedral computations for the simple graph partitioning problem. Technical report, Aarhus School of Business, Department of Accounting, Finance and Logistics (2005)

  74. Sørensen, M.M.: Facet-defining inequalities for the simple graph partitioning polytope. Discrete Optim. 4(2), 221–231 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  75. Sørensen, M.M.: Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes. Discrete Optim. 25, 120–140 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  76. Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM 44(4), 585–591 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  77. STOM-Group: Hazmat network data (2021). https://github.com/STOM-Group/Hazmat-Network-Data. Last accessed June 2021

  78. Validi, H., Buchanan, A.: Political districting to minimize cut edges. Math. Program. Comput. 1, 1 (2022). https://doi.org/10.1007/s12532-022-00221-5

    Article  MathSciNet  MATH  Google Scholar 

  79. Validi, H., Buchanan, A., Lykhovyd, E.: Imposing contiguity constraints in political districting models. Oper. Res. 70(2), 867–892 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  80. Vogiatzis, C., Walteros, J.L.: Integer programming models for detecting graph bipartitions with structural requirements. Networks 71(4), 432–450 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  81. Walteros, J.L., Buchanan, A.: Why is maximum clique often easy in practice? Oper. Res. 68(6), 1866–1895 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  82. Walteros, J.L., Veremyev, A., Pardalos, P.M., Pasiliao, E.L.: Detecting critical node structures on graphs: a mathematical programming approach. Networks 73(1), 48–88 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  83. Watts, D.J., Strogatz, S.H.: Collective dynamics of “small-world’’ networks. Nature 393(6684), 440–442 (1998)

    Article  MATH  Google Scholar 

  84. Wei, N., Walteros, J.L.: Integer programming methods for solving binary interdiction games. Eur. J. Oper. Res. 302(2), 456–469 (2022)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Funding

This material is based upon work supported by the Office of Naval Research under contract No. N00014-20-1-2242.

Author information

Authors and Affiliations

  1. University at Buffalo, The State University of New York, Buffalo, NY, USA

    Demetrios V. Papazaharias & Jose L. Walteros

Authors
  1. Demetrios V. Papazaharias
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jose L. Walteros
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Both authors contributed to the study’s conception, design, and execution. D. V. Papazaharias implemented the proposed algorithms, collected the data, and analyzed the computational results. The writing process was a collaborative effort between both authors, who read and approved the final manuscript.

Corresponding author

Correspondence to Jose L. Walteros.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Papazaharias, D.V., Walteros, J.L. Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations. Math. Prog. Comp. 15, 103–151 (2023). https://doi.org/10.1007/s12532-022-00228-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-022-00228-y

Keywords

Mathematics Subject Classification