Maximum cut parameterized by crossing number

Abstract

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 join-ing 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 [8] 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. © 2020, Brown University. All rights reserved.