Maximum Cut Parameterized by Crossing Number

Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke +3

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 maximiz…