Papers › Solving Cut-Problems in Quadratic Time for Graphs With Bounded Treewidth
Solving Cut-Problems in Quadratic Time for Graphs With Bounded Treewidth
Hauke Brinkop, Klaus Jansen
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
In the problem (Unweighted) Max-Cut we are given a graph G = (V,E) and asked for a set S ⊆V such that the number of edges from S to V ∖S is maximal. In this paper we consider an even harder problem: (Weighted) Max-Bisection. Here we are given an undirected graph G = (V,E) and a weight function w E →ℚ_(>0) and the task is to find a set S ⊆V such that (i) the sum of the weights of edges from S is maximal; and (ii) S contains ⌈n/2⌉ vertices (where n = |V|). We design a framework that allows to solve this problem in time 𝒪(2ᵗ n²) if a tree decomposition of width t is given as part of the input. This improves the previously best running time for Max-Bisection of [DBLP:journals/tcs/HanakaKS21] by a factor t². Under common hardness assumptions, neither the dependence on t in the exponent nor the dependence on n can be reduced [DBLP:journals/tcs/HanakaKS21,DBLP:journals/jcss/EibenLM21,DBLP:journals/talg/LokshtanovMS18]. Our framework can be applied to other cut problems like Min-Edge-Expansion, Sparsest-Cut, Densest-Cut, β-Balanced-Min-Cut, and Min-Bisection. It also works in the setting with arbitrary weights and directed edges.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections