An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number

摘要

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~kn~(3/2) log n). Our result simultaneously improves the running time and removes the 1-planarity restriction.