betaFeedback

WorksComputer Science

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition

Abstract

Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts. Cygan, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saurabh (SICOMP 2019) gave the first fixed-parameter algorithm, which runs in O*(2^(O(k^3))) time, by introducing an unbreakable decomposition. Cygan, Komosa, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saurabh, and Wahlström (TALG 2021) strengthened the decomposition and improved the running time to O*(2^(O(k log k))). However, whether the running time could be improved to single-exponential remained open. In this paper, we give a deterministic O*(2^(O(k)))-time algorithm for Minimum Bisection. Our algorithm also counts all feasible bisections. To obtain an O*(2^(O(k)))-time algorithm, we introduce two new techniques. First, we give a new algorithm that computes a (2k,k)-edge-unbreakable decomposition with adhesion at most 2k in O*(2^(O(k))) time by relaxing the unbreakability and adhesion guarantees of the decomposition in (TALG 2021). Second, we improve the running time of the dynamic program over the decomposition from O*(2^(O(k log k))) to O*(2^(O(k))) using important cuts, inclusion-exclusion, and formal logarithms and exponentials. Together with color coding, the same techniques give a deterministic O*(2^(O(k)))-time algorithm for Matching Cut, which asks for a cut whose crossing edges form a matching. This improves the O*(2^(O(k log k)))-time algorithm of Aravind and Saxena (IWOCA 2021).

Introduction

Minimum Bisection asks whether the vertices of a graph can be divided into two parts of equal size, up to one vertex, with at most kk edges between the two parts. Throughout the paper, GG is a simple undirected graph and n=∣V(G)∣n = |V(G)|. For A⊆V(G)A \subseteq V(G), let δG(A):={uv∈E(G):∣{u,v}∩A∣=1}\delta_G(A) := \{uv \in E(G) : |\{u,v\} \cap A| = 1\}.

Minimum Bisection

Input: A simple undirected graph GG and an integer k≥0k \ge0.

Question: Is there a set A⊆V(G)A \subseteq V(G) with ∣A∣=⌊n/2⌋|A| = \lfloor n/2 \rfloor and ∣δG(A)∣≤k|\delta_G(A)| \le k?

Parameter: kk.

Kernighan and Lin [26] formulated the problem of partitioning the vertices of an edge-weighted graph into parts of prescribed sizes so as to minimize the weight of the crossing edges. The unweighted two-part case with equal part sizes is Minimum Bisection. Garey, Johnson, and Stockmeyer [16] proved that Minimum Bisection is NP-complete.

Cygan, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saurabh [13] gave the first fixed-parameter algorithm for Minimum Bisection, with running time O∗(2O(k3))O^*(2^{O(k^3)}), and asked whether Minimum Bisection admits a single-exponential fixed-parameter algorithm.2 Cygan, Komosa, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saurabh, and Wahlström [11] improved the running time to O∗(2O(klog⁡k))O^*(2^{O(k \log k)}), making substantial progress toward this goal while leaving the question open.

In this paper, we answer the question posed in [13] affirmatively by giving a deterministic O∗(2O(k))O^*(2^{O(k)})-time algorithm for Minimum Bisection.

Existing framework for Minimum Bisection by [13] and [11]. Before describing our algorithm, we review the framework common to the two previous algorithms. Both algorithms first compute a tree decomposition with a certain property, called an unbreakable decomposition, and then perform bottom-up dynamic programming over the decomposition. Unbreakable decomposition itself was introduced in [13] as an algorithmically tractable relaxation of lean tree decompositions [42, 6].

For a graph HH, a set X⊆V(H)X \subseteq V(H) is (q,k)(q,k)-vertex-unbreakable if every separation (L,R)(L,R)3 of HH with ∣L∩R∣≤k|L \cap R| \le k satisfies min⁡{∣L∩X∣,∣R∩X∣}≤q\min\{|L \cap X|, |R \cap X|\} \le q. A tree decomposition is (q,k)(q,k)-vertex-unbreakable if every bag is (q,k)(q,k)-vertex-unbreakable. [13] constructs in O∗(2O(k2))O^*(2^{O(k^2)}) time a (2O(k),k)(2^{O(k)}, k)-vertex-unbreakable decomposition with adhesion at most 2O(k)2^{O(k)}, where the adhesion of a tree decomposition is the maximum size of the intersection of two adjacent bags. [11] substantially strengthens the decomposition guarantee and constructs in O∗(2O(klog⁡k))O^*(2^{O(k \log k)}) time a tree decomposition with adhesion at most kk that is (i,i)(i,i)-vertex-unbreakable for every 1≤i≤k1 \le i \le k.

Both algorithms then perform bottom-up dynamic programming over their tree decompositions. At a node tt with parent t′t', a state records which vertices of the adhesion Bt∩Bt′B_t \cap B_{t'} lie on one side of the cut, the number of vertices on that side in the subgraph below tt, and the number of cut edges in that subgraph.

The difficult step is the transition at a large bag BtB_t. The unbreakability guarantee in [11] ensures that every set A⊆V(G)A \subseteq V(G) with ∣δG(A)∣≤k|\delta_G(A)| \le k satisfies ∣A∩Bt∣≤k|A \cap B_t| \le k or ∣Bt∖A∣≤k|B_t \setminus A| \le k, but enumerating all such intersections takes nO(k)n^{O(k)} time. Their algorithm avoids this enumeration by color coding. In particular, at most kk child adhesions are split by the cut, and each has size at most kk. Hence, the coloring must separate the smaller of A∩BtA \cap B_t and Bt∖AB_t \setminus A from O(k2)O(k^2) vertices on the other side of these adhesions. If each vertex is colored red with probability Θ(1/k)\Theta(1/k), the probability that every vertex of the smaller set is red and all O(k2)O(k^2) opposite-side vertices are blue is 2−O(klog⁡k)2^{-O(k \log k)}. The color-coding step therefore contributes a factor of 2O(klog⁡k)2^{O(k \log k)} to the transition time.

Our techniques. In [11], both the construction of the unbreakable decomposition and the transition at a large bag take O∗(2O(klog⁡k))O^*(2^{O(k \log k)}) time. We perform both steps in O∗(2O(k))O^*(2^{O(k)}) time and thereby obtain a single-exponential algorithm.

We first consider the construction of the unbreakable decomposition. We do not know whether a vertex-unbreakable decomposition with the bounds of [11], that is, adhesions of size at most kk and (i,i)(i,i)-vertex-unbreakable bags for every 1≤i≤k1 \le i \le k, can be constructed in O∗(2O(k))O^*(2^{O(k)}) time. However, as observed in [11], all applications considered there, including Minimum Bisection, require only the weaker notion of edge-unbreakability. For a graph HH, a set X⊆V(H)X \subseteq V(H) is (q,k)(q,k)-edge-unbreakable if min⁡{∣A∩X∣,∣X∖A∣}≤q\min\{|A \cap X|, |X \setminus A|\} \le q for every A⊆V(H)A \subseteq V(H) with ∣δH(A)∣≤k|\delta_H(A)| \le k. A tree decomposition of HH is (q,k)(q,k)-edge-unbreakable if every bag is (q,k)(q,k)-edge-unbreakable. We construct an edge-unbreakable decomposition in single-exponential time.

Theorem 1.1. Given a graph GG and kk, one can construct in O∗(2O(k))O^*(2^{O(k)}) time a (2k,k)(2k,k)-edge-unbreakable decomposition with adhesion at most 2k2k.

We next consider the transition at a large bag. Unlike the previous algorithms, we do not use color coding. We instead apply algebraic operations to formal power series that represent the dynamic-programming tables, including inclusion–exclusion and formal logarithms and exponentials, all of which can be performed in O∗(2O(k))O^*(2^{O(k)}) time. These operations cannot be performed on Boolean existence values alone, so each state stores the number of partial solutions that it represents. Consequently, our algorithm counts all feasible solutions to Minimum Bisection rather than merely deciding feasibility.

Theorem 1.2. The feasible solutions to Minimum Bisection can be counted deterministically in O∗(2O(k))O^*(2^{O(k)}) time. If a feasible solution exists, one can recover one within the same running time.

Application. Our approach also applies to Matching Cut, parameterized by the number of crossing edges.

Matching Cut

Input: A simple undirected graph GG and an integer k≥0k \ge0.

Question: Is there a set ∅≠A⊂V(G)\varnothing\ne A \subset V(G) such that ∣δG(A)∣≤k|\delta_G(A)| \le k, and ∣δG(A)∩δG({v})∣≤1|\delta_G(A) \cap\delta_G(\{v\})| \le1 for every v∈V(G)v \in V(G)?

Parameter: kk.

Gomes and Sau [18] observed that Matching Cut parameterized by kk reduces to Stable Cutset, for which Marx, O’Sullivan, and Razgon [35] gave a fixed-parameter algorithm using Courcelle’s theorem. Aravind and Saxena [4] later made the dependence on kk explicit with an O∗(2O(klog⁡k))O^*(2^{O(k \log k)})-time algorithm by applying the framework of [11].

Our algorithm for Matching Cut combines the Minimum Bisection algorithm with color coding that assigns distinct colors to the endpoints of the cut. In particular, we obtain the following result.

Theorem 1.3. Matching Cut can be solved deterministically, and a witness can be recovered, in O∗(2O(k))O^*(2^{O(k)}) time.

Unlike our algorithm for Minimum Bisection, our algorithm for Matching Cut does not count feasible solutions, because the initial color-coding step preserves only the existence of a solution.

Remark. It is natural to ask whether our techniques also yield single-exponential algorithms for other applications of unbreakable decompositions. [11] applied the unbreakable-decomposition framework to Steiner Cut, a generalization of pp-Way Cut, and to Steiner Multicut. As noted above, these applications use only edge-unbreakability, so our decomposition is sufficient for the same framework, up to constant changes in the parameters. This replacement alone, however, does not yield single-exponential algorithms, because the bottleneck is already present in the number of dynamic-programming states. For pp-Way Cut, a solution may have up to p≤k+1p \le k+1 parts, and the direct dynamic program assigns each adhesion vertex to one of these parts, already resulting in pO(k)=2O(klog⁡k)p^{O(k)} = 2^{O(k\log k)} dynamic-programming states, whereas the corresponding number for Minimum Bisection is only 2O(k)2^{O(k)}. We do not know whether these states can be compressed. Nevertheless, we believe that our construction provides a useful first step toward speeding up other applications of unbreakable decompositions, such as pp-Way Cut, Steiner Cut, and Steiner Multicut.

Lower bound. Aravind and Saxena [4] gave a lower-bound result for Matching Cut parameterized by the number kk of crossing edges. More quantitatively, let g:N→R≥0g:\mathbb{N}\to\mathbb{R}_{\ge0} be unbounded and nondecreasing, satisfy g(x)=O(x)g(x)=O(x), and satisfy g(λx)=O(g(x))g(\lambda x)=O(g(x)) for every fixed constant λ>0\lambda>0. Then Matching Cut cannot be solved in O∗(2o(g(k)))O^*(2^{o(g(k))}) time unless 3-SAT can be solved in O∗(2o(g(s)))O^*(2^{o(g(s))}) time on instances of size ss, where ss is the total number of variables and clauses in the input 3-CNF formula.4

For Minimum Bisection, we prove Theorem 1.4.

Theorem 1.4. Let g:N→R≥0g:\mathbb{N}\to\mathbb{R}_{\ge0} be unbounded and nondecreasing, satisfy g(x)=O(x)g(x)=O(x), and satisfy g(λx)=O(g(x))g(\lambda x)=O(g(x)) for every fixed constant λ>0\lambda>0. Suppose that Minimum Bisection can be solved in O∗(2o(g(k)))O^*(2^{o(g(k))}) time. Then 3-SAT can be solved in 2o(g(qs))+O(slog⁡q/q+log⁡s)2^{o(g(qs))+O(s\log q/q+\log s)} time for every integer qq with 2≤q≤s2\le q\le s, where ss is the total number of variables and clauses in the input 3-CNF formula.5

In particular, the theorem yields three consequences.

  • For every fixed 0<α<10<\alpha<1, if 3-SAT has no O∗(2o(sα))O^*(2^{o(s^\alpha)})-time algorithm, then Minimum Bisection has no O∗(2o(k/(log⁡k)α/(2−α)))O^*(2^{o(k/(\log k)^{\alpha/(2-\alpha)})})-time algorithm.

  • For every fixed c>0c>0, if 3-SAT has no O∗(2o(s/(log⁡s)c))O^*(2^{o(s/(\log s)^c)})-time algorithm, then Minimum Bisection has no O∗(2o(k/((log⁡k)2clog⁡log⁡k)))O^*(2^{o(k/((\log k)^{2c}\log\log k))})-time algorithm.

  • If 3-SAT has no O∗(2o(s))O^*(2^{o(s)})-time algorithm, equivalently, if ETH holds, then Minimum Bisection has no O∗(2o(k))O^*(2^{o(k)})-time algorithm.

We remark that [11] asked whether an O∗(2o(k))O^*(2^{o(k)})-time algorithm for Minimum Bisection could be ruled out under ETH. The ETH consequence in Theorem 1.4 answers this question affirmatively. However, OpenAI and Anthropic recently released independent manuscripts claiming that ETH is false [38, 12]. If either claim is correct, ETH no longer provides an algorithmic barrier. We nevertheless believe that Theorem 1.4 retains the spirit of the question in [11], because the first and second items transfer near-exponential lower bounds for 3-SAT to near-single-exponential lower bounds for Minimum Bisection, with the exponent remaining arbitrarily close to linear.

Related work

References

  1. [1]Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences, 58(1):193–210, 1999. doi:10.1006/jcss.1998.1605.DOI
  2. [2]Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, and Thatchaphol Saranurak. Unbreakable decomposition in close-to-linear time. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1464–1493, 2025. doi:10.1137/1.9781611978322.46.DOI
  3. [3]Aditya Anand, Euiwoong Lee, Yaowei Long, and Thatchaphol Saranurak. Local important separators with applications to unbreakable decomposition and multicut. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027. To appear. arXiv:2610.39030.arxiv.org/abs/2610.39030
  4. [4]N. R. Aravind and Roopam Saxena. An FPT algorithm for matching cut and d-cut. In International Workshop on Combinatorial Algorithms (IWOCA), pages 531–543, 2021. doi:10.1007/978-3-030-79987-8_37.DOI
  5. [5]Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, and Michael Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171–191, 1987. doi:10.1007/BF02579448.
  6. [6]Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree-decompositions. Combinatorics, Probability and Computing, 11(6):541–547, 2002. doi:10.1017/S0963548302005369.DOI
  7. [7]Paul S. Bonsma. The complexity of the matching-cut problem for planar graphs and other graph classes. Journal of Graph Theory, 62(2):109–126, 2009. doi:10.1002/jgt.20390.DOI
  8. [8]Johannes Carmesin, Reinhard Diestel, Matthias Hamann, and Fabian Hundertmark. k-blocks: A connectivity invariant for graphs. SIAM Journal on Discrete Mathematics, 28(4):1876–1891, 2014. doi:10.1137/130923646.
  9. [9]Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Loksh­tanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, Cham, 2015. doi:10.1007/978-3-319-21275-3.DOI
  10. [10]Václav Chvátal. Recognizing decomposable graphs. Journal of Graph Theory, 8(1):51–53, 1984. doi:10.1002/jgt.3190080106.DOI
  11. [11]Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, and Magnus Wahlström. Randomized contractions meet lean decompositions. ACM Transactions on Algorithms, 17(1):6:1–6:30, 2021. doi:10.1145/3426738.DOI
  12. [12]Claude (Anthropic). A 2^{o(n)} time algorithm for 3-SAT, October 2026. Draft manuscript with an accompanying Lean 4 formalization. URL: https://github.com/anthropics/formal-math/blob/main/eth/paper.pdf.
  13. [13]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Minimum bisection is fixed-parameter tractable. SIAM Journal on Computing, 48(2):417–450, 2019. doi:10.1137/140988553.DOI
  14. [14]Joshua Erde. A unified treatment of linked and lean tree-decompositions. Journal of Combinatorial Theory, Series B, 130:114–143, 2018. doi:10.1016/j.jctb.2017.12.001.DOI
  15. [15]Kyle Fox, Philip N. Klein, and Shay Mozes. A polynomial-time bicriteria approximation scheme for planar bisection. In ACM Symposium on Theory of Computing (STOC), pages 841–850, 2015. doi:10.1145/2746539.2746564.DOI
  16. [16]Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237–267, 1976. doi:10.1016/0304-3975(76)90059-1.DOI
  17. [17]Ronald L. Graham. On primitive graphs and optimal vertex assignments. Annals of the New York Academy of Sciences, 175(1):170–186, 1970. doi:10.1111/j.1749-6632.1970.tb56468.x.DOI
  18. [18]Guilherme C. M. Gomes and Ignasi Sau. Finding cuts of bounded degree: Complexity, FPT and exact algorithms, and kernelization. In International Symposium on Parameterized and Exact Computation (IPEC), pages 19:1–19:15, 2019. doi:10.4230/LIPIcs.IPEC.2019.19.DOI
  19. [19][HKS21] Tesshu Hanaka, Yasuaki Kobayashi, and Taiga Sone. A (probably) optimal algorithm for bisection on bounded-treewidth graphs. Theoretical Computer Science, 873:38–46, 2021. doi:10.1016/j.tcs.2021.04.023.DOI
  20. [20][ILSS23] Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. Parameterized complexity of fair bisection: (FPT-approximation meets unbreakability). In European Symposium on Algorithms (ESA), pages 63:1–63:17, 2023. doi:10.4230/LIPIcs.ESA.2023.63.DOI
  21. [21][IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.
  22. [22][KF06] Robert Krauthgamer and Uriel Feige. A polylogarithmic approximation of the minimum bisection. SIAM Review, 48(1):99–130, 2006. doi:10.1137/050649094.
  23. [23][Kho06] Subhash Khot. Ruling out PTAS for graph Min-Bisection, dense k-subgraph, and bipartite clique. SIAM Journal on Computing, 36(4):1025–1071, 2006. doi:10.1137/S0097539705447037.DOI
  24. [24][KK98] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359–392, 1998. doi:10.1137/S1064827595287997.DOI
  25. [25][KKL20] Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms. Discrete Applied Mathematics, 283:44–58, 2020. doi:10.1016/j.dam.2019.12.010.DOI
  26. [26][KL70] Brian W. Kernighan and Shen Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2):291–307, 1970. doi:10.1002/j.1538-7305.1970.tb01770.x.DOI
  27. [27][KL16] Dieter Kratsch and Van Bang Le. Algorithms solving the matching cut problem. Theoretical Computer Science, 609(2):328–335, 2016. doi:10.1016/j.tcs.2015.10.016.DOI
  28. [28][Kor25] Tuukka Korhonen. Linear-time algorithms for k-edge-connected components, k-lean tree decompositions, and more. In ACM Symposium on Theory of Computing (STOC), pages 111–119, 2025. doi:10.1145/3717823.3718123.DOI
  29. [29][LL19] Hoàng-Oanh Le and Van Bang Le. A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter. Theoretical Computer Science, 770:69–78, 2019. doi:10.1016/j.tcs.2018.10.029.DOI
  30. [30][LPR22] Felicia Lucke, Daniël Paulusma, and Bernard Ries. On the complexity of matching cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science, 936:33–42, 2022. doi:10.1016/j.tcs.2022.09.014.DOI
  31. [31][LPR23] Felicia Lucke, Daniël Paulusma, and Bernard Ries. Finding matching cuts in H-free graphs. Algorithmica, 85(10):3290–3322, 2023. doi:10.1007/s00453-023-01137-9.DOI
  32. [33]Jason Li and Trevor Vaughn. Faster minimum k-cut I: Simple and sparse weighted graphs, 2026. arXiv:2609.27781. URL: https://arxiv.org/abs/2609.27781.
  33. [34]Dániel Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394–406, 2006. doi:10.1016/j.tcs.2005.10.007.DOI
  34. [35]Dániel Marx, Barry O’Sullivan, and Igor Razgon. Treewidth reduction for constrained separation and bipartization problems. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 561–572, 2010. doi:10.4230/LIPIcs.STACS.2010.2485.DOI
  35. [36]Augustine M. Moshi. Matching cutsets in graphs. Journal of Graph Theory, 13(5):527–536, 1989. doi:10.1002/jgt.3190130502.DOI
  36. [37]Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 182–191, 1995. doi:10.1109/SFCS.1995.492475.
  37. [38]OpenAI. The exponential time hypothesis is false, October 2026. Draft manuscript with an accompanying Lean formalization. URL: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.
  38. [39]Maurizio Patrignani and Maurizio Pizzonia. The complexity of the matching-cut problem. In Graph-Theoretic Concepts in Computer Science (WG), pages 284–295, 2001. doi:10.1007/3-540-45477-2_26.DOI
  39. [40]Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In ACM Symposium on Theory of Computing (STOC), pages 255–264, 2008. doi:10.1145/1374376.1374415.DOI
  40. [41]Alexander D. Scott and Gregory B. Sorkin. Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Transactions on Algorithms, 5(4):45:1–45:27, 2009. doi:10.1145/1597036.1597049.DOI
  41. [42]Robin Thomas. A Menger-like property of tree-width: The finite case. Journal of Combinatorial Theory, Series B, 48(1):67–76, 1990. doi:10.1016/0095-8956(90)90130-R.DOI

Paper details

vlnc:W_76t3n688
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 6 Pro, GPT-6 Astra, GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents