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

Jonas Lill, Kalina Petrova, Simon Weber

TL;DR

This paper presents a new algorithm for the MAXCUT problem on multigraphs (or weighted graphs) that runs in parameterized linear time. It improves upon existing algorithms by extending them to handle multigraphs and by using a tighter lower bound (the Poljak-Turzík bound) for the parameter, leading to a more efficient algorithm for certain instances.

What Problem Does This Paper Address?

The MAXCUT problem asks for a partition of a graph's vertices into two sets such that the sum of weights of edges connecting vertices in different sets is maximized. This is a fundamental NP-complete problem with applications in various fields. While exact solutions are generally intractable for large graphs, research has focused on "parameterized complexity," where the goal is to find algorithms that are efficient when a specific parameter is small.

Previous work established that MAXCUT is solvable in fixed-parameter tractable (FPT) time when the desired cut size is "close" to a known lower bound. Specifically, algorithms exist for simple graphs where the parameter k is the difference between the desired cut size and the Edwards-Erdös bound. These algorithms were later improved to run in parameterized linear time, meaning their runtime is roughly f(k) * O(m), where m is the number of edges.

This paper addresses two main limitations:

  1. Multigraphs: Existing parameterized linear-time algorithms were primarily designed for simple graphs. The authors extend these algorithms to work for multigraphs (or equivalently, graphs with positive integer edge weights).
  2. Tighter Lower Bound: The Edwards-Erdös bound is a general lower bound. The Poljak-Turzík bound is a tighter lower bound for weighted graphs, which can be strictly larger than the Edwards-Erdös bound for multigraphs. By using the Poljak-Turzík bound as the basis for the parameter k, the authors can achieve a smaller parameter value for the same problem instance, leading to potentially faster algorithms.

Methods

The core of the paper's approach is a reduction technique that transforms the input graph into a simpler structure called a "uniform-clique-forest" while preserving the MAXCUT solution. This reduction process involves a series of "reduction rules" that iteratively simplify the graph by removing vertices and adjusting the parameter k.

Key methodological aspects include:

  • Reduction Rules: The paper introduces eight specific reduction rules. These rules are designed to systematically simplify the graph. Crucially, each rule is carefully crafted to ensure that the MAXCUT problem on the reduced graph is equivalent to the original problem, up to the parameter k and the Poljak-Turzík bound. The rules are more complex than those used for the Edwards-Erdös bound because tracking changes to the minimum spanning forest weight is more intricate than tracking vertex counts.
  • Uniform-Clique-Forest: The reduction process aims to transform the graph into a uniform-clique-forest. This is a graph where each biconnected component (a "block") is a clique where all edges have the same weight. Solving MAXCUT on such a structure is significantly easier.
  • MAXCUT with Vertex Weights: Once the graph is reduced to a uniform-clique-forest, the problem is further transformed into a "MAXCUT with Vertex Weights" problem. This is a standard problem that can be solved efficiently on uniform-clique-forests.
  • Parameterized Linear Time: The overall algorithm achieves parameterized linear time complexity, f(k) * O(m + n), by carefully analyzing the number of reduction steps (bounded by k) and the time complexity of each step.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • Poljak-Turzík Bound Advantage: The paper highlights that the Poljak-Turzík bound can be strictly larger than the Edwards-Erdös bound for multigraphs. This means that using the Poljak-Turzík bound as the parameter k can lead to a smaller k for the same problem instance, resulting in a more efficient parameterized algorithm.
  • Sophisticated Reduction Rules: The development of eight specific reduction rules that carefully manage the changes to the minimum spanning forest weight is a significant technical contribution. These rules are more complex than those used in prior work on simple graphs.
  • Bridging Theory and Practice: By extending existing FPT algorithms to multigraphs and utilizing a tighter bound, the paper makes MAXCUT algorithms more applicable to a broader range of real-world graph problems where edge weights or multiple edges are common.

Key Results

  • Theorem 4: An algorithm that decides, for any weighted graph G and integer k, whether a cut of weight at least $\frac{w(G)}{2} + \frac{w_{MSF}(G)}{4} + k$ exists, runs in parameterized linear time $O(2^{O(k)} \cdot (|E| + |V|))$.
  • Theorem 5: An algorithm that computes such a cut (if one exists) runs in parameterized quadratic time $O(2^{O(k)} \cdot (|E| \cdot |V|))$.
  • Generalization: The algorithms are extended to work for multigraphs and positive integer-weighted graphs, a significant improvement over previous work limited to simple graphs.
  • Improved Parameterization: By using the Poljak-Turzík bound, the parameter k can be smaller than when using the Edwards-Erdös bound, leading to better performance for certain instances.

Limitations and Future Work

  • Open Problems: The authors identify several open problems:
  • Extending their results to other "λ-extendible properties" beyond MAXCUT, particularly for multigraphs.
  • Developing kernelization results for MAXCUT on multigraphs or positive integer-weighted graphs.
  • Generalizing the algorithms to handle positive real-weighted graphs, which presents challenges due to the inability to discretize the decrease of k.
  • Runtime for Computing Cuts: While the decision problem (Theorem 4) achieves parameterized linear time, the problem of computing the cut (Theorem 5) has a slightly higher complexity of $O(2^{O(k)} \cdot (|E| \cdot |V|))$. Further improvements in this area might be possible.
  • Practical Performance: The paper focuses on theoretical complexity. The practical performance of the algorithm on large-scale instances is not discussed.

Summary updated

Abstract

MaxCut is a classical <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>NP</mml:mi></mml:math> -complete problem and a crucial building block in many combinatorial algorithms. The famous <i>Edwards-Erdös bound</i> states that any connected graph on <i>n</i> vertices with <i>m</i> edges contains a cut of size at least <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:mfrac><mml:mi>m</mml:mi> <mml:mn>2</mml:mn></mml:mfrac> <mml:mo>+</mml:mo> <mml:mfrac><mml:mrow><mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn></mml:mrow> <mml:mn>4</mml:mn></mml:mfrac> </mml:mrow> </mml:math> . Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter <i>k</i> is the difference between the desired cut size <i>c</i> 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., <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> <mml:mo>·</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> . We improve upon this result in two ways: Firstly, we extend the algorithm to work also for <i>multigraphs</i> (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 <i>Poljak-Turzík bound</i>. The Poljak-Turzík bound states that any weighted graph <i>G</i> has a cut of weight at least <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac><mml:mrow><mml:mi>w</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo></mml:mrow> <mml:mn>2</mml:mn></mml:mfrac> <mml:mo>+</mml:mo> <mml:mfrac> <mml:mrow><mml:msub><mml:mi>w</mml:mi> <mml:mrow><mml:mi>MSF</mml:mi></mml:mrow> </mml:msub> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:mrow> <mml:mn>4</mml:mn></mml:mfrac> </mml:mrow> </mml:math> , where <i>w</i>(<i>G</i>) denotes the total weight of <i>G</i>, and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>w</mml:mi> <mml:mrow><mml:mi>MSF</mml:mi></mml:mrow> </mml:msub> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:mrow> </mml:math> 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 <i>k</i>. Our algorithm also runs in parameterized linear time, i.e., <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> <mml:mo>·</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> .
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