Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound

Jonas Lill, Kalina Petrova, Simon Weber

This paper, recently published by researchers from ETH Zürich and IST Austria, presents a significant leap in our ability to solve the MaxCut problem efficiently when we are looking for solutions that are "just a bit better" than what theory guarantees must exist.

TL;DR

The authors provide the first parameterized linear-time algorithm for the MaxCut problem in multigraphs (graphs with weighted edges) that finds cuts exceeding the Poljak-Turzík bound. By using a tighter theoretical lower bound as a baseline, they make the algorithm applicable to a wider range of graphs while maintaining a lightning-fast $O(m+n)$ running time.

What Problem Does This Paper Address?

MaxCut is a fundamental problem in computer science: given a graph, partition its vertices into two sets to maximize the total weight of edges crossing between them. It’s famously NP-complete, meaning we don't expect to find an algorithm that is always fast for every possible graph.

However, mathematicians have long known "guaranteed" lower bounds. For example, the Edwards-Erdős bound states that any connected simple graph with $m$ edges and $n$ vertices has a cut of at least $m/2 + (n-1)/4$.

The "Above Guarantee" paradigm asks: if we know a cut of size $L$ exists, can we efficiently find one of size $L+k$? Previous work achieved linear-time algorithms for simple graphs using the Edwards-Erdős bound. This paper tackles two major gaps:

  1. Multigraphs: Real-world networks often have multiple edges or weights between nodes.
  2. Tighter Bounds: For multigraphs, the Edwards-Erdős bound is "loose." The Poljak-Turzík bound ($w(G)/2 + w_{MSF}(G)/4$, where $w_{MSF}$ is the weight of the minimum spanning forest) is much more accurate but significantly harder to work with algorithmically.

Methods

The authors employ a strategy common in parameterized complexity: Reduction Rules.

  1. Preprocessing via Reductions: They introduce eight specific reduction rules that simplify the graph. These rules either prove that a cut of the desired size exists or reduce the graph's complexity while keeping track of the parameter $k$ (the "excess" cut size needed).
  2. Tracking the MSF: The core technical challenge was ensuring these rules correctly account for changes in the Minimum Spanning Forest (MSF) weight. Unlike simply counting vertices ($n-1$), tracking $w_{MSF}$ through graph deletions and contractions is mathematically delicate.
  3. Uniform-Clique-Forests: After applying the rules exhaustively, the graph is either empty or reduced to a "uniform-clique-forest"—a specific structure where every biconnected component is a clique with uniform edge weights.
  4. Exact Solving: They prove that MaxCut can be solved in linear time on these uniform-clique-forests, even when vertices have weights. By iterating over the possible partitions of a small set of "marked" vertices ($S$, where $|S| \le 12k$), they find the optimal cut.

Datasets

Not discussed in the paper. This is a theoretical contribution focused on algorithmic proofs and complexity analysis rather than empirical benchmarking.

Key Insights and Ideas

  • The Power of Poljak-Turzík: In simple graphs, the Poljak-Turzík and Edwards-Erdős bounds are identical. However, in multigraphs, Poljak-Turzík is often larger. This means the "distance" to the target cut ($k$) is smaller, making the problem easier to solve for the algorithm.
  • Discretizing Progress: The authors show that their reduction rules make "progress" in increments of $1/4$ relative to the Poljak-Turzík bound, allowing them to bound the number of steps needed.
  • Structural Characterization: The realization that any graph not containing a cut of the guaranteed size must be "close" to a uniform-clique-forest is a powerful structural insight that enables the final linear-time step.

Key Results

  • Theorem 4 (Decision): An algorithm that decides if a cut of size $PoljakTurzik + k$ exists in $2^{O(k)} \cdot O(|E| + |V|)$ time. This is parameterized linear time, meaning for a fixed $k$, the algorithm scales perfectly with the size of the graph.
  • Theorem 5 (Search): A quadratic-time algorithm $2^{O(k)} \cdot O(|E| \cdot |V|)$ to actually construct the cut.
  • Strict Improvement: The authors demonstrate cases (Observation 6) where their algorithm provides a polynomial-time solution while previous methods based on the Edwards-Erdős bound would have remained exponential.

Limitations and Future Work

  • Integer Weights Only: The current approach relies on edge weights being positive integers. Extending this to positive real weights is an open challenge because the parameter $k$ might not decrease in discrete, predictable steps.
  • Kernelization: While the algorithm is efficient, the authors note that providing a "linear kernel" (a way to shrink the graph to a size purely dependent on $k$) for multigraphs is a potential area for further refinement.
  • Generalizing to other properties: The authors suggest their techniques might be adaptable to other "$\lambda$-extendible" graph properties beyond MaxCut.

Summary updated

Abstract

MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least $m/2 + (n-1)/4$. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., $f(k)\cdot O(m)$. We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least $w(G)/2 + w_{MSF}(G)/4$, where w(G) denotes the total weight of G, and $w_{MSF}(G)$ denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., $f(k)\cdot O(m+n)$.
BibTeX
@inproceedings{lill2025linear,
  author = {Jonas Lill and Kalina Petrova and Simon Weber},
  title = {{Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound}},
  booktitle = {Algorithmica},
  year = {2025},
  doi = {10.1007/s00453-025-01306-y},
}
Figure