Fast Balanced Partitioning Is Hard Even on Grids and Trees

1. Andreev, K., Räcke, H.: Balanced graph partitioning. Theory of Computing Systems 39(6), 929–939 (2006)

   Article  MathSciNet  MATH  Google Scholar 

2. Arbenz, P., van Lenthe, G., Mennel, U., Müller, R., Sala, M.: Multi-level μ-finite element analysis for human bone structures. In: Proceedings of the 8th Workshop on State-of-the-art in Scientific and Parallel Computing (PARA), pp. 240–250 (2007)

   Google Scholar 

3. Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pp. 222–231 (2004)

   Google Scholar 

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

   Article  MathSciNet  MATH  Google Scholar 

5. Chevalier, C., Pellegrini, F.: PT-Scotch: A tool for efficient parallel graph ordering. Parallel Computing 34(68), 318–331 (2008)

   Article  MathSciNet  Google Scholar 

6. Delling, D., Goldberg, A., Pajor, T., Werneck, R.: Customizable route planning. Experimental Algorithms, 376–387 (2011)

   Google Scholar 

7. Díaz, J., Serna, M.J., Torán, J.: Parallel approximation schemes for problems on planar graphs. Acta Informatica 33(4), 387–408 (1996)

   Article  MathSciNet  MATH  Google Scholar 

8. Diestel, R., Jensen, T.R., Gorbunov, K.Y., Thomassen, C.: Highly connected sets and the excluded grid theorem. Journal of Combinatorial Theory, Series B 75(1), 61–73 (1999)

   Article  MathSciNet  MATH  Google Scholar 

9. Diks, K., Djidjev, H.N., Sykora, O., Vrto, I.: Edge separators of planar and outerplanar graphs with applications. Journal of Algorithms 14(2), 258–279 (1993)

   Article  MathSciNet  MATH  Google Scholar 

10. Elman, H., Silvester, D., Wathen, A.: Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics. Oxford University Press, USA (2005)

    MATH  Google Scholar 

11. Even, G., Naor, J., Rao, S., Schieber, B.: Fast approximate graph partitioning algorithms. SIAM Journal on Computing 28(6), 2187–2214 (1999)

    Article  MathSciNet  MATH  Google Scholar 

12. Feldmann, A.E.: Balanced Partitioning of Grids and Related Graphs: A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations. PhD thesis, ETH Zurich, Diss.-Nr. ETH: 20371 (April 2012)

    Google Scholar 

13. Feldmann, A.E., Das, S., Widmayer, P.: Restricted cuts for bisections in solid grids: A proof via polygons. In: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 143–154 (2011)

    Google Scholar 

14. Feldmann, A.E., Foschini, L.: Balanced partitions of trees and applications. In: 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 100–111 (2012)

    Google Scholar 

15. Feldmann, A.E., Widmayer, P.: An O(n ⁴) time algorithm to compute the bisection width of solid grid graphs. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 143–154 (2011)

    Google Scholar 

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

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

18. Karypis, G., Kumar, V.: METIS-unstructured graph partitioning and sparse matrix ordering system, version 2.0. Technical report, University of Minnesota (1995)

    Google Scholar 

19. Khot, S.A., Vishnoi, N.K.: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ₁. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 53–62 (2005)

    Google Scholar 

20. Klein, P., Plotkin, S., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 682–690 (1993)

    Google Scholar 

21. Krauthgamer, R., Naor, J., Schwartz, R.: Partitioning graphs into balanced components. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 942–949 (2009)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

23. Lipton, R., Tarjan, R.: Applications of a planar separator theorem. SIAM Journal on Computing 9, 615–627 (1980)

    Article  MathSciNet  MATH  Google Scholar 

24. MacGregor, R.M.: On Partitioning a Graph: a Theoretical and Empirical Study. PhD thesis, University of California, Berkeley (1978)

    Google Scholar 

25. Papadimitriou, C., Sideri, M.: The bisection width of grid graphs. Theory of Computing Systems 29, 97–110 (1996)

    MathSciNet  MATH  Google Scholar 

26. Park, J.K., Phillips, C.A.: Finding minimum-quotient cuts in planar graphs. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 766–775 (1993)

    Google Scholar 

27. Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC) (2008)

    Google Scholar 

28. Simon, H.D., Teng, S.H.: How good is recursive bisection? SIAM Journal on Scientific Computing 18(5), 1436–1445 (1997)

    Article  MathSciNet  MATH  Google Scholar 

29. Wu, Z., Leahy, R.: An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 15(11), 1101–1113 (1993)

    Article  Google Scholar 

Download references