An FPT Algorithm for Max-Cut Parameterized by Crossing Number

Abstract

The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algorithm for the problem on `almost' planar graphs: Given an $n$-vertex graph and its drawing with $k$ crossings, our algorithm runs in time $O(2^k(n+k{)}^{3/2}\log (n+k))$. Previously, Dahn, Kriege and Mutzel (IWOCA 2018) obtained an algorithm that, given an $n$-vertex graph and its $1$-planar drawing with $k$ crossings, runs in time $O(3^k{n}^{3/2}\log n)$. Our result simultaneously improves the running time and removes the $1$-planarity restriction.

The same running time bound has been obtained independently and simultaneously by Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, and Alexander Nover arXiv:1903.06061