Given an edge-weighted graph G on n nodes, the NP-hard MAX-CUT problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximized. We propose a fixed-parameter tractable algorithm parameterized by the number k of crossings in a given drawing of G. Our algorithm achieves a running time of O(2k⋅p(n+k)), where p is the polynomial running time for planar MAX-CUT. The only previously known similar algorithm [Dahn et al, IWOCA 2018] is restricted to embedded 1-planar graphs (i.e., at most one crossing per edge) and its dependency on k is of order 3k. Finally, combining this with the fact that crossing number is fixed-parameter tractable with respect to itself, we see that MAX-CUT is fixed-parameter tractable with respect to the crossing number, even without a given drawing. Moreover, the results naturally carry over to the minor-monotone-version of crossing number.

Top