An FPT Algorithm for Max-Cut Parameterized by Crossing Number
share
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 (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 n). Our result simultaneously improves the running time and removes the 1-planarity restriction.
READ FULL TEXT