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

Area of Science:

• Computer Science
• Discrete Mathematics
• Graph Theory
• Algorithm Analysis

Background:

• The MaxCut problem is a classical NP-complete problem with significant applications in combinatorial optimization.
• Existing algorithms for MaxCut on simple graphs have parameterized linear time complexity based on the Edwards-Erdös bound.
• The Poljak-Turzík bound offers a potentially tighter lower bound for MaxCut, especially in weighted graphs.

Purpose of the Study:

• To extend existing parameterized algorithms for the MaxCut problem to handle multigraphs and weighted graphs.
• To improve the parameterization of MaxCut algorithms by utilizing the Poljak-Turzík bound instead of the Edwards-Erdös bound.
• To achieve a parameterized linear time complexity for MaxCut on multigraphs and weighted graphs.

Main Methods:

• Adaptation of existing fixed-parameter tractable (FPT) algorithms for MaxCut.
• Extension of the algorithm's applicability to graphs with parallel edges (multigraphs) or positive integer weights.
• Re-parameterization of the algorithm using the difference between the desired cut size and the Poljak-Turzík bound.

Main Results:

• The developed algorithm successfully extends the parameterized MaxCut solution to multigraphs and weighted graphs.
• The new parameterization based on the Poljak-Turzík bound can lead to smaller parameter values (k) for multigraphs.
• The algorithm achieves a parameterized linear time complexity of f(k)·O(m+n), an improvement over previous O(m) bounds.

Conclusions:

• This work provides a more versatile and efficient parameterized algorithm for the MaxCut problem applicable to a broader class of graphs.
• The use of the Poljak-Turzík bound offers a refined approach to parameterizing MaxCut, enhancing algorithmic performance.
• The achieved parameterized linear time complexity represents a significant theoretical advancement in solving the MaxCut problem.