Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Parameterized Complexity of Computing Balanced Partitions in Graphs

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition the vertices into two equal-sized parts. We prove that Bisection is FPT for the distance to constant cliquewidth if we are given the deletion set. This implies FPT algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set. However, we show that Bisection does not admit polynomial-size kernels for these parameters. For the Vertex Bisection problem, vertices need to be removed in order to obtain two equal-sized parts. We show that this problem is FPT for the number of removed vertices k if the solution cuts the graph into a constant number c of connected components. The latter condition is unavoidable, since we also prove that Vertex Bisection is W[1]-hard w.r.t. (k,c). Our algorithms for finding bisections can easily be adapted to finding partitions into d equal-sized parts, which entails additional running time factors of n O(d). We show that a substantial speed-up is unlikely since the corresponding task is W[1]-hard w.r.t. d, even on forests of maximum degree two. We can, however, show that it is FPT for the vertex cover number.

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

Similar content being viewed by others

Notes

  1. 1 To be precise, we need the vertex deletion set to be given to obtain an FPT algorithm for this parameter.

  2. 2 This definition of torso is equivalent to the one used by Marx et al. [46].

  3. 3 Here, ⊎ denotes the disjoint union of sets.

  4. 4Parts in a feasible partition for Balanced Partitioning may not be of equal size; we will consider this issue more closely below.

References

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

    Article  MATH  MathSciNet  Google Scholar 

  2. Arbenz, P.: Personal communication. ETH Zürich (2013)

  3. 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 International Workshop on Applied Parallel Computing (PARA 2006), volume 4699 of LNCS, pages 240–250. Springer (2007)

  4. Bhatt, S. N., Leighton, F. T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28 (2), 300–343 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bodlaender, H. L.: Kernelization: New upper and lower bound techniques. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), volume 5917 of LNCS, pages 17–37. Springer (2009)

  6. Bodlaender, H. L., Drange, P. G., Dregi, M. S., Fomin, F. V., Lokshtanov, D., Pilipczuk, M.: An O(c k n) 5-approximation algorithm for treewidth. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 499–508. IEEE Computer Society (2013)

  7. Bodlaender, H. L., Jansen, B. M. P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discret. Math. 28 (1), 277–305 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  8. Brandes, U., Fleischer, D.: Vertex bisection is hard, too. J. Graph Algorithm. Appl. 13 (2), 119–131 (April 2009)

    Article  MATH  MathSciNet  Google Scholar 

  9. Bui, T. N., Peck, A.: Partitioning planar graphs. SIAM J. Comput. 21 (2), 203–215 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  10. Bui, T. N., Chaudhuri, S., Leighton, F. T., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica 7 (2), 171–191 (1987)

    Article  MathSciNet  Google Scholar 

  11. Chandran, L. S., Kavitha, T.: The treewidth and pathwidth of hypercubes. Discret. Math. 306 (3), 359–365 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  12. Chen, J., Kanj, I. A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411 (40-42), 3736–3756 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  13. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101 (1-3), 77–114 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  14. Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In: Proceedings of the 46th Annual Symposium on the Theory of Computing (STOC 2014). To appear (2014)

  15. Delling, D., Goldberg, A. V., Pajor, T., Werneck, R. F. F.: Customizable route planning. In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA 2011), volume 6630 of LNCS, pages 376–387. Springer (2011)

  16. Delling, D., Goldberg, A. V., Razenshteyn, I., Werneck, R. F. F.: Exact combinatorial branch-and-bound for graph bisection. In: Proceedings of the 14th Workshop on Algorithms Engineering and Experiments (ALENEX 2012), pages 30–44 (2012)

  17. Diestel, R., 4th edn: Graph Theory, Volume 173 of graduate texts in mathematics. Springer (2010)

  18. Doucha, M., Kratochvíl, J.: Cluster vertex deletion: A parameterization between vertex cover and clique-width. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), volume 7464 of LNCS, pages 348–359. Springer (2012)

  19. Downey, R. G., Fellows, M. R.: Fundamentals of parameterized complexity. Springer (2013)

  20. Enciso, R., Fellows, M. R., Guo, J., Kanj, I. A., Rosamond, F. A., Suchý, O.: What makes equitable connected partition easy. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), volume 5917 of LNCS, pages 122–133. Springer (2009)

  21. Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), volume 2204 of LNCS, pages 117–128. Springer (2001)

  22. Feldmann, A. E.: Fast balanced partitioning is hard, even on grids and trees. Theor. Comput. Sci. 485, 61–68 (2013)

    Article  MATH  MathSciNet  Google Scholar 

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

  24. Feldmann, A. E., Widmayer, P.: An O(n 4) time algorithm to compute the bisection width of solid grid graphs. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), volume 6942 of LNCS, pages 143–154. Springer (2011)

  25. Fellows, M. R., Hermelin, D., Rosamond, F. A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410 (1), 53–61 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  26. Flum, J., Grohe, M.: Parameterized complexity theory. Springer (2006)

  27. Fomin, F. V., Golovach, P. A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized with clique-width. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 493–502, SIAM (2010)

  28. Fomin, F. V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \(\mathcal {F}\)-deletion: Approximation, kernelization and optimal FPT algorithms. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 470–479. IEEE Computer Society (2012)

  29. Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34 (3), 596–615 (1987)

    Article  MathSciNet  Google Scholar 

  30. Ganian, R., Obdržálek, J.: Expanding the expressive power of monadic second-order logic on restricted graph classes. In: Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2013). Lect. Notes Comput. Sci. 8288, 164–177 (2013)

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

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

    Article  MATH  MathSciNet  Google Scholar 

  33. Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38 (1), 31–45 (2007)

    Article  Google Scholar 

  34. Hliněný, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51 (3), 326–362 (2008)

    Article  Google Scholar 

  35. Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79 (1), 39–49 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  36. Karypis, G., Kumar, V.: A parallel algorithm for multilevel graph partitioning and sparse matrix ordering. J. Parallel Distrib. Comput. 48 (1), 71–95 (1998)

    Article  MathSciNet  Google Scholar 

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

  38. Kloks, T: Treewidth – Computations and Approximations, volume 842 of LNCS. Springer (1994)

  39. Kloks, T., Lee, C. M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002), volume 2573 of LNCS, pages 282–295. Springer (2002)

  40. Kwatra, V., Schödl, A., Essa, I., Turk, G., Bobick, A.: Graphcut textures: Image and video synthesis using graph cuts. ACM Trans. Graph. 22 (3), 277–286 (2003)

    Article  Google Scholar 

  41. Lipton, R. J., Tarjan, R. E.: Applications of a planar separator theorem. SIAM J. Comput. 9, 615–627 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  42. MacGregor, R. M.: On Partitioning a Graph: A theoretical and empirical study. PhD thesis. University of California, Berkeley (1978)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  44. Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51 (1), 60–78 (2008)

    Article  Google Scholar 

  45. Marx, D., O’Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithm. 9 (4), 30 (2013)

    Article  MathSciNet  Google Scholar 

  46. Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford University Press (2006)

  47. Oum, S.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithm. 5 (1) (2008)

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

  49. Soumyanath, K., Deogun, J. S.: On the bisection width of partial k-trees. In: Proceedings of the 20th Southeastern Conference on Combinatorics, Graph Theory, and Computing, volume 74 of Congressus Numerantium, pages 25–37. Utilitas Mathematica Publishing (1990)

  50. van Bevern, R., Feldmann, A. E., Sorge, M., Suchý, O.: On the parameterized complexity of computing graph bisections. In: Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’13), volume 8165 of LNCS, pages 76–88. Springer (2013)

  51. Werneck, R. F. F: Personal communication (2013). Microsoft Research Silicon Valley

  52. Wiegers, M.: The k-section of treewidth restricted graphs. In: Proceedings of the 15th International Symposium on Mathematical Foundations of Computer Science (MFCS 1990), volume 452 of LNCS, pages 530–537. Springer (1990)

Download references

Acknowledgments

René van Bevern and Manuel Sorge gratefully acknowledge support by the DFG, research project DAPA, NI 369/12. Ondřej Suchý is also grateful for support by the DFG, research project AREG, NI 369/9. Part of Ondřej Suchý’s work was done while with TU Berlin.

The authors thank Bart M. P. Jansen, Stefan Kratsch, Rolf Niedermeier and the anonymous referees for helpful suggestions.

Author information

Authors and Affiliations

  1. Institut für Softwaretechnik und Theoretische Informatik, Berlin, TU, Germany

    René van Bevern & Manuel Sorge

  2. Combinatorics, Optimization, University of Waterloo, Waterloo, Ontario, Canada

    Andreas Emil Feldmann

  3. Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic

    Ondřej Suchý

Authors
  1. René van Bevern
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andreas Emil Feldmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manuel Sorge
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ondřej Suchý
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Manuel Sorge.

Additional information

An extended abstract of this article appeared at the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013) [4]. The extended abstract contains results regarding Bisection and Vertex Bisection, while this article additionally provides full proof details as well as parameterized complexity analyses of Balanced Partitioning.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

van Bevern, R., Feldmann, A.E., Sorge, M. et al. On the Parameterized Complexity of Computing Balanced Partitions in Graphs. Theory Comput Syst 57, 1–35 (2015). https://doi.org/10.1007/s00224-014-9557-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-014-9557-5

Keywords

Search

Navigation