Maximum Cut Parameterized by Crossing Number
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(2^k · 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 3^k. 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., number=3, journal=Journal of Graph Algorithms and Applications, author=Chimani, Markus and Dahn, Christine and Juhnke-Kubitzke, Martina and Kriege, Nils and Mutzel, Petra and Nover, Alexander, year=2020, month=Mar., pages=155–170