An FPT Algorithm for Max-Cut Parameterized by Crossing Number

Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki +1

The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algo…