# Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs

**Authors:** Christine Dahn, Nils M. Kriege, Petra Mutzel, Julian Schilling  
**arXiv:** [1812.03074](https://arxiv.org/abs/1812.03074)  
**Date:** 2018-11-29  
**Summary page:** https://www.summarizepaper.com/en/paper/1812.03074v1/

## Key points

- The paper proposes two fixed-parameter tractable algorithms to solve the weighted Max-Cut problem on embedded 1-planar graphs.
- A graph is considered 1-planar if it can be drawn in the plane with at most one crossing per edge.
- The proposed algorithms are parameterized by the crossing number k of the given embedding and recursively reduce a 1-planar graph to at most 3^k planar graphs using edge removal and node contraction techniques.
- Their main algorithm then solves the Max-Cut problem for these planar graphs using FCE-MaxCut, which was introduced by Liers and Pardella [21].
- In case of non-negative edge weights, they suggest a variant that allows solving planar instances with any planar Max-Cut algorithm.
- The authors demonstrate that a maximum cut in a given 1-planar graph can be derived from solutions for its corresponding planar graphs.
- Their algorithms compute a maximum cut in an embedded weighted 1-planar graph with n nodes and k edge crossings in time O(3^kn^{3/2} log n).
- This work is an extension of their conference version (available as arXiv:1803.10983), which is currently under review at TCS.
- The proposed algorithms have significant implications for real world applications such as network design and optimization problems where finding a maximum cut in a graph is crucial.

## Summary

In their paper titled "Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs," Christine Dahn, Nils M. Kriege, Petra Mutzel, and Julian Schilling propose two fixed-parameter tractable algorithms to solve the weighted Max-Cut problem on embedded 1-planar graphs. A graph is considered 1-planar if it can be drawn in the plane with at most one crossing per edge. The proposed algorithms are parameterized by the crossing number k of the given embedding and recursively reduce a 1-planar graph to at most 3^k planar graphs using edge removal and node contraction techniques. Their main algorithm then solves the Max-Cut problem for these planar graphs using FCE-MaxCut, which was introduced by Liers and Pardella [21]. In case of non-negative edge weights, they suggest a variant that allows solving planar instances with any planar Max-Cut algorithm. The authors demonstrate that a maximum cut in a given 1-planar graph can be derived from solutions for its corresponding planar graphs. Their algorithms compute a maximum cut in an embedded weighted 1-planar graph with n nodes and k edge crossings in time O(3^kn^{3/2} log n). This work is an extension of their conference version (available as arXiv:1803.10983), which is currently under review at TCS. The proposed algorithms have significant implications for real world applications such as network design and optimization problems where finding a maximum cut in a graph is crucial.