Abstract
The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been thoroughly studied in the past. However, only few results have been published that consider the parameterized complexity of this problem.
We show that Bisection is FPT w.r.t. the minimum cut size if there is an optimum bisection that cuts into a given constant number of connected components. Our algorithm applies to the more general Balanced Biseparator problem where vertices need to be removed instead of edges. We prove that this problem is W[1]-hard w.r.t. the minimum cut size and the number of cut out components.
For Bisection we further show that no polynomial-size kernels exist for the cut size parameter. In fact, we show this for all parameters that are polynomial in the input size and that do not increase when taking disjoint unions of graphs. We prove fixed-parameter tractability for the distance to constant cliquewidth if we are given the deletion set. This implies fixed-parameter algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Andreev, K., Räcke, H.: Balanced graph partitioning. Theory of Computing Systems 39(6), 929–939 (2006)
Arbenz, P.: Personal communication, ETH Zürich (2013)
P. Arbenz, G. van Lenthe, U. Mennel, R. Müller, and M. Sala. Multi-level μ-finite element analysis for human bone structures. In Proc. 8th PARA, volume 4699 of LNCS, pages 240–250. Springer, 2007.
Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28(2), 300–343 (1984)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Science 209(1-2), 1–45 (1998)
Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 17–37. Springer, Heidelberg (2009)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Proc. 28th STACS. LIPIcs, vol. 9, pp. 165–176. Dagstuhl (2011)
Bui, T.N., Peck, A.: Partitioning planar graphs. SIAM J. Comput. 21(2), 203–215 (1992)
Bui, T.N., Chaudhuri, S., Leighton, F.T., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica 7(2), 171–191 (1987)
Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40-42), 3736–3756 (2010)
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1-3), 77–114 (2000)
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376–387. Springer, Heidelberg (2011)
Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics, vol. 173. Springer (2010)
Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117–128. Springer, Heidelberg (2001)
Feldmann, A.E.: Fast balanced partitioning is hard, even on grids and trees. Theor. Comput. Sci. 485, 61–68 (2013)
Feldmann, A.E., Foschini, L.: Balanced partitions of trees and applications. In: Proc. 29th STACS. LIPIcs, vol. 14, pp. 100–111. Dagstuhl (2012)
Feldmann, A.E., Widmayer, P.: An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 143–154. Springer, Heidelberg (2011)
Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \(\mathcal{F}\)-deletion: Approximation, kernelization and optimal fpt algorithms. In: Proc. 53rd FOCS, pp. 470–479. IEEE Computer Society (2012)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. (1979)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Science 1(3), 237–267 (1976)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)
Hliněný, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326–362 (2008)
Khot, S.A., Vishnoi, N.K.: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ1. In: Proc. 46th FOCS, pp. 53–62. IEEE Computer Society (2005)
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: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 282–295. Springer, Heidelberg (2002)
Kwatra, V., Schödl, A., Essa, I., Turk, G., Bobick, A.: Graphcut textures: Image and video synthesis using graph cuts. ACM T. Graphic. 22(3), 277–286 (2003)
Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9, 615–627 (1980)
MacGregor, R.M.: On Partitioning a Graph: a Theoretical and Empirical Study. PhD thesis, University of California, Berkeley (1978)
Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394–406 (2006)
Marx, D., O’Sullivan, B., Razgon, I.: Treewidth reduction for constrained separation and bipartization problems. In: Proc. 27th STACS. LIPIcs, vol. 5, pp. 561–572. Dagstuhl (2010)
Marx, D., O’Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. CoRR, abs/1110.4765 (2011)
Oum, S.: Approximating rank-width and clique-width quickly. ACM T. Algorithms 5 (1) (2008)
Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proc. 40th STOC, pp. 255–264. ACM (2008)
Soumyanath, K., Deogun, J.S.: On the bisection width of partial k-trees. In: Proc. 20th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 74, pp. 25–37 (1990)
Wiegers, M.: The k-section of treewidth restricted graphs. In: Rovan, B. (ed.) MFCS 1990. LNCS, vol. 452, pp. 530–537. Springer, Heidelberg (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Bevern, R., Feldmann, A.E., Sorge, M., Suchý, O. (2013). On the Parameterized Complexity of Computing Graph Bisections. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 2013. Lecture Notes in Computer Science, vol 8165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45043-3_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-45043-3_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45042-6
Online ISBN: 978-3-642-45043-3
eBook Packages: Computer ScienceComputer Science (R0)