Skip to main content
SpringerLink
Log in

An exact algorithm for graph partitioning

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Armbruster, M.: Branch-and-Cut for a Semidefinite Relaxation of Large-Scale Minimum Bisection Problems. PhD thesis, Chemnitz University of Technology, Chemnitz (2007)

  2. Armbruster M., Fügenschuh M., Helmberg C., Martin A.: A comparative study of linear and semidefinite branch-and-cut methods for solving the minimum graph bisection problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds) Proceedings of the 13th International Integer Programming and Combinatorial Optimization Conference, vol. 5035 of Lecture Notes in Computer Science, pp. 112–124. Springer, (2008)

  3. Barzilai J., Borwein J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  4. Borchers B.: CSDP, A C library for semidefinite programming. Optim. Methods Softw. 11(1), 613–623 (1999)

    Article  MathSciNet  Google Scholar 

  5. Brunetta L., Conforti M., Rinaldi G.: A branch-and-cut algorithm for the equicut problem. Math. Program. 78, 243–263 (1997)

    MathSciNet  MATH  Google Scholar 

  6. Catalyürek U.V., Aykanat C.: Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel Distrib. Syst. 10, 673–693 (1999)

    Article  Google Scholar 

  7. Collins O., Dolinar S., McEliece R., Pollara F.: A VLSI decomposition of the de Bruijn graph. J. ACM 39, 931–948 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  8. de Souza, C.C.: The Graph Equipartition Problem: Optimal Solutions, Extensions and Applications. PhD thesis, Université Catholique de Louvain, Louvain-la-Neuve (1993)

  9. Devine, K., Boman, E., Heaphy, R., Bisseling, R., Catalyurek, U.: Parallel hypergraph partitioning for scientific computing. In: Proceedings of 20th International Parallel and Distributed Processing Symposium (IPDPS’06), IEEE (2006)

  10. Dongarra, J.J.: Performance of various computers using standard linear equations software. Technical Report cs-89-85, University of Tennessee, Knoxville (2008)

  11. Falkner J., Rendl F., Wolkowicz H.: A computational study of graph partitioning. Math. Program. 66, 211–240 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  12. Feldmann, R., Monien, B., Mysliwietz, P., Tschöke, S.: A better upper bound on the bisection width of de Bruijn networks. In: STACS 97, Lecture Notes in Computer Science, vol. 1200, pp. 511–522. Springer, Berlin (1997)

  13. 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, 229–256 (1998)

    MATH  Google Scholar 

  14. Garey M.R., Johnson D.S., Stockmeyer L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237–267 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gilbert J.R., Miller G.L., Teng S.H.: Geometric mesh partitioning: implementation and experiments. SIAM J. Sci. Comput. 19, 2091–2110 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  16. Grigori, L., Boman, E., Donfack, S., Davis, T.A.: Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization. SIAM J. Sci. Comput. (2008). under submission

  17. Hager W.W., Krylyuk Y.: Graph partitioning and continuous quadratic programming. SIAM J. Discret. Math. 12, 500–523 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  18. Hager W.W., Krylyuk Y.: Multiset graph partitioning. Math. Meth. Oper. Res. 55, 1–10 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  19. Hager W.W., Phan D.T.: An ellipsoidal branch and bound algorithm for global optimization. SIAM J. Optim. 20, 740–758 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Helmberg C.: A cutting plane algorithm for large scale semidefinite relaxations. In: Grötschel, M. (eds) The Sharpest Cut, MPS-SIAM Series Optimization, pp. 233–256. SIAM, Philadelphia (2004)

    Google Scholar 

  21. Hendrickson, B., Leland, R.: The Chaco user’s guide—Version 2.0, Sandia National Laboratories. Technical Report SAND94-2692 (1994)

  22. Hendrickson B., Leland R.: An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16, 452–469 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  23. Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proceedings of Supercomputing ’95, ACM, November (1995)

  24. Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Dordrecht (1995)

    MATH  Google Scholar 

  25. Johnson D.S., Aragon C.R., McGeoch L.A., Schevon C.: Optimization by simulated annealing: an experimental evaluation. Part I, graph partitioning. Oper. Res. 37, 865–892 (1989)

    Article  MATH  Google Scholar 

  26. Johnson E.L., Mehrotra A., Nemhauser G.L.: Min-cut clustering. Math. Program. 62, 133–151 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  27. Johnson, T.: A concurrent dynamic task graph. In: Proceedings of 1993 International Conference on Parallel Processing, (TR-93-011, CISE Department, University of Florida) (1993)

  28. Karisch S.E., Rendl F., Clausen J.: Solving graph bisection problems with semidefinite programming. INFORMS J. Comput. 12, 177–191 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  29. Karypis G., Kumar V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359–392 (1998)

    Article  MathSciNet  Google Scholar 

  30. Karypis G., Kumar V.: Parallel multilevel k-way partitioning scheme for irregular graphs. SIAM Rev. 41, 278–300 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  31. Karypis G., Kumar V.: Multilevel k-way hypergraph partitioning. VLSI Des. 11, 285–300 (2000)

    Article  Google Scholar 

  32. Lengauer T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester (1990)

    MATH  Google Scholar 

  33. Mitchell, J.: Branch-and-cut for the k-way equipartition problem. Technical report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute (2001)

  34. Murty K.G., Kabadi S.N.: Some NP-complete problems in quadratic and linear programming. Math. Program. 39, 117–129 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  35. Pardalos P.M., Vavasis S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15–22 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  36. Pellegrini F., Roman J., Amestoy P.R.: Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering. Concurr. Pract. Exp. 12, 68–84 (2000)

    Google Scholar 

  37. Preis, R., Diekmann, R.: The PARTY partitioning library user guide—version 1.1 (1996)

  38. Rendl F., Rinaldi G., Wiegele A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121, 307–335 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  39. Sensen, N.: Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows. In: Lecture Notes in Computer Science, vol. 2161, pp. 391–403. Springer, London (2001)

  40. Sinclair M.: An exact penalty function approach for nonlinear integer programming problems. Eur. J. Oper. Res. 27, 50–56 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  41. Soper A.J., Walshaw C., Cross M.: A combined multilevel search and multilevel optimization approach to graph-partition. J. Glob. Optim. 29, 225–241 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  42. Souza C., Keunings R., Wolsey L., Zone O.: A new approach to minimizing the frontwidth in finite element calculations. Comput. Methods Appl. Mech. Eng. 111, 323–334 (1994)

    Article  MATH  Google Scholar 

  43. Teng S.-H.: Provably good partitioning and load balancing algorithms for parallel adaptive N-body simulation. SIAM J. Sci. Comput. 19, 635–656 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  44. Walshaw C., Cross M., Everett M.: Parallel dynamic graph partitioning for adaptive unstructured meshs. J. Parallel Distrib. Comput. 47, 102–108 (1997)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Florida, PO Box 118105, Gainesville, FL, 32611-8105, USA

    William W. Hager

  2. Department of Business Analytics and Mathematical Sciences, IBM T.J. Watson Research Center, PO Box 218, Yorktown Heights, NY, 10598, USA

    Dzung T. Phan

  3. Department of Mathematics, Center for Computation and Technology, Louisiana State University, 140 Lockett Hall, Baton Rouge, LA, 70803-4918, USA

    Hongchao Zhang

Authors
  1. William W. Hager
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dzung T. Phan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hongchao Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to William W. Hager.

Additional information

November 23, 2009. Revised October 13, 2011. This research was partly supported by National Science Foundation Grant 0620286 and by Office of Naval Research Grant N00014-11-1-0068.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hager, W.W., Phan, D.T. & Zhang, H. An exact algorithm for graph partitioning. Math. Program. 137, 531–556 (2013). https://doi.org/10.1007/s10107-011-0503-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-011-0503-x

Keywords

Mathematics Subject Classification (2000)

Search

Navigation