An FPT 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\mathrm{/}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)$\mathrm{.}Ourresultsimultaneouslyimprovestherunningtimeandremovesthe$1$-planarity restriction.