Skip to main content
SpringerLink
Log in

A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts

  • Conference paper
Integer Programming and Combinatorial Optimization (IPCO 2004)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 3064))

Abstract

We discuss the Max-flow Quotient-cut Improvement (MQI) algorithm, a flow-based method for improving graph cuts when cut quality is measured by quotient-style metrics such as expansion or conductance. Given a cut \((S,\overline{S})\), this algorithm finds the best improvement among all cuts \((S',\overline{S'})\) such that S′ is a strict subset of S. This idea has already been used by theorists to give improved bounds for graph bisection and for finding hierarchical oblivous routing schemes. Here we investigate the practical utility of the idea and find that MQI can be combined with Metis to obtain a heuristic graph partitioner that does an extremely good job on classic benchmark graphs, VLSI circuits, and four different tasks from the Information Retrieval domain. We also find empirically that Metis+MQI runs in nearly linear time, so it is applicable to very large problems.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • 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

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aggarwal, R., Karypis, G., Kumar, V., Shekhar, S.: Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems 7(1) (1999)

    Google Scholar 

  2. Albert, R., Barabasi, A., Jeong, H.: Diameter of the world wide web. Nature 401, 130–131 (1999)

    Article  Google Scholar 

  3. Alon, N., Milman, V.D.: 1 isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B 38, 73–88 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  4. Alpert, C.J.: The ispd98 circuit benchmark suite. In: Proceedings International Symposium on Physical Design, April 1998, pp. 85–90 (1998)

    Google Scholar 

  5. Alpert, C.J., Kahng, A.B.: Recent developments in netlist partitioning: A survey. VLSI Journal 19(1), 1–81 (1995)

    Article  MATH  Google Scholar 

  6. Arora, S., Rao, S., Vazirani, U.: Expander flows and a O(\(\sqrt{log n}\)) approximation to sparsest cut. In: STOC (2004)

    Google Scholar 

  7. Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences 28(2), 303–343 (1984)

    Article  MathSciNet  Google Scholar 

  8. Boppana, R.B.: Eigenvalues and graph bisection: An average-case analysis. In: Symposium on Foundations of Computer Science(FOCS), pp. 280–285 (1987)

    Google Scholar 

  9. Carrasco, J.J.M., Fain, D., Lang, K., Zhukov, L.: Clustering of bipartite advertiser-keyword graph. Technical report, OR-2003-017, Overture/ Yahoo Labs (2003)

    Google Scholar 

  10. Cheng, D., Kannan, R., Vempala, S., Wang, G.: On a recursive spectral algorithm for clustering from pairwise similarities. Technical report, MITLCS- TR-906, MIT (2003)

    Google Scholar 

  11. Cherkassky, B.V., Goldberg, A.V.: On implementing the push-relabel method for the maximum flow problem. Algorithmica 19(4), 390–410 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  12. Dhillon, I.S.: Co-clustering documents and words using bipartite spectral graph partitioning. In: Knowledge Discovery and Data Mining, pp. 269–274 (2001)

    Google Scholar 

  13. Donath, W.E., Hoffman, A.J.: Lower bounds for partitioning of graphs. IBM J. Res. Develop. 17, 420–425 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  14. Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. In: Symposium on the Foundations of computer science, pp. 105–115 (2000)

    Google Scholar 

  15. Fiduccia, C.M., Mattheyses, R.M.: A linear time heuristic for improving network partitions. In: Design Automation Conference, pp. 175–181 (1982)

    Google Scholar 

  16. Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing 18, 30–55 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  17. Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. In: Theoretical Computer Science, pp. 237–267 (1976)

    Google Scholar 

  18. Goldberg, A.V.: Finding a maximum density subgraph. Technical report, UCB CSD 84/71, University of California, Berkeley (1984)

    Google Scholar 

  19. Hagen, L., Kahng, A.B.: New spectral methods for ratio cut partitioning and clustering. IEEE Trans. on CAD 11(9), 1074–1085 (1992)

    Google Scholar 

  20. Harrelson, C., Hildrum, K., Rao, S.: A polynomial-time tree decomposition to minimize congestion. In: Proceedings of the Fifteenth ACM Symposium on Parallelism Algorithms and Architectures (June 2003)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  22. Johnson, D.S., Aragon, C.R., McGeoch, L.A., Shevon, C.: Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Operations Research 37(6), 865–892 (1989)

    Article  MATH  Google Scholar 

  23. Kannan, R., Vempala, S., Vetta, A.: On clusterings - good, bad and spectral. In: Symposium on Foundations of Computer Science(FOCS) (1999)

    Google Scholar 

  24. Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S.: Multilevel hypergraph partitioning: Applications in VLSI domain. Technical report, UMN (1997)

    Google Scholar 

  25. Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 359–392 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  26. Kernighan, B.W., Lin, S.: An ecient heuristic procedure for partitioning graphs. The Bell System Technical Journal 29(2), 291–307 (1970)

    Google Scholar 

  27. Rao, S., Lang, K.: Improving quotient cuts with max flow. Technical report, OR-2003-014, Overture/Yahoo Labs (2003)

    Google Scholar 

  28. Lang, K., Rao, S.: Finding near-optimal cuts: An empirical evaluation. In: Symposimum on Discrete Algorithms, pp. 212–221 (1993)

    Google Scholar 

  29. Leighton, F.T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: 28th Annual Symposium on Foundations of Computer Science, pp. 256–269. IEEE, Los Alamitos (1988)

    Google Scholar 

  30. Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM) 46(6), 787–832 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  31. Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888–905 (2000)

    Article  Google Scholar 

  32. Sinclair, A.: Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, Probability and Computing 1, 351–370 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  33. Tanner, R.M.: Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods 5, 287–293 (1984)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Yahoo, 210 S. Delacey Ave No.105, Pasadena, CA, 91105, USA

    Kevin Lang

  2. CS Dept, Soda Hall UCB, Berkeley, CA, 94720, USA

    Satish Rao

Authors
  1. Kevin Lang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Satish Rao
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of IEOR, Columbia University, 500 West 120th Street, 10027, New York, NY, USA

    Daniel Bienstock

  2. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA

    George Nemhauser

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lang, K., Rao, S. (2004). A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts. In: Bienstock, D., Nemhauser, G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2004. Lecture Notes in Computer Science, vol 3064. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25960-2_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-25960-2_25

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-22113-5

  • Online ISBN: 978-3-540-25960-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation