Maximum Cut Parameterized by Crossing Number - Chimani, Markus; Dahn, Christine; Juhnke-Kubitzke, Martina; Kriege, Nils; Mutzel, Petra; Nover, Alexander (Journal of Graph Algorithms and Applications, 2020)
Given an edge-weighted graph $G$ on $n$ nodes, the NP-hard $\rm{M\small{AX}}$-$\rm{C\small{UT}}$ 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 $\mathcal{O}(2^{k} · p(n+k))$, where $p$ is the polynomial running time for planar $\rm{M\small{AX}}$-$\rm{C\small{UT}}$.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 $\rm{M\small{AX}}$-$\rm{C\small{UT}}$ 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.