Solving Cut-Problems in Quadratic Time for Graphs with Bounded Treewidth

In the problem (Unweighted) Max-Cut we are given a graph \(G = (V,E)\) and asked for a set \(S \subseteq V\) such that the number of edges from S to \(V \setminus 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 \rightarrow \mathbb {Q}_{>0}\) and the task is to find a set \(S \subseteq V\) such that (i) the sum of the weights of edges from S is maximal; and (ii) S contains \(\lceil * \rceil {\frac{n}{2}}\) vertices (where \(n = | V |\)). We design a framework that allows to solve this problem in time \(\mathcal {O}(2^t n^2)\) 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 Hanaka, Kobayashi, and Sone [9] by a factor \(t^2\). Under common hardness assumptions, neither the dependence on t in the exponent nor the dependence on n can be reduced [7, 9, 16]. Our framework can be applied to other cut problems like Min-Edge-Expansion, Sparsest-Cut, Densest-Cut, \(\beta \)-Balanced-Min-Cut, and Min-Bisection. It also works in the setting with arbitrary weights and directed edges.

1. 1.

   The undirected and unweighted versions can easily be modelled as directed and weighted by setting each edge weight to 1 and by replacing each undirected edge between vertices \(v_1\) and \(v_2\) by two directed edges, \(v_1v_2\) and \(v_2v_1\).

2. 2.

   The upper bound on the number of nodes occurs only implicitly in their work within the analysis of their algorithm’s running time.

3. 3.

   To be precise, they consider Min-Bisection; however, in their paper as well as in [11], all arguments work for both problems.

4. 4.

   It might disappear on multiple leaf-root-paths; however, the node at which a vertex disappears, is the same on each of those leaf-root-paths.

5. 5.

   Since we only did an index shift, we can reuse the recurrence from [11] by applying the same shift to it.

6. 6.

   Note that \(\partial S\) can only take on \(\mathcal {O}(2^t)\) different values at some fixed node i. We use a simple DP to precompute the \(w(\cdot )\) terms efficiently (for a fixed node in time \(\mathcal {O}(2^tn)\)).

7. 7.

   \(x \le y \implies f(a,x) \ge f(a,y)\).

8. 8.

   For the reader not familiar with order theory: The binary supremum is an associative and commutative map. If for every pair of elements there is a supremum, that is, a smallest element that is larger than both elements of the pair, then so it does for any finite set M. This can be shown by a simple inductive argument using the aforementioned associativity/commutativity.

Authors and Affiliations

1. Kiel University, Kiel, Germany

   Hauke Brinkop & Klaus Jansen

Corresponding author

Correspondence to Hauke Brinkop .

Editors and Affiliations

1. University of Liverpool, Liverpool, UK

   Leszek Gąsieniec

Reprints and permissions

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics