Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00523
Maximum Cut Parameterized by Crossing Number
Markus Chimani,
Christine Dahn,
Martina JuhnkeKubitzke,
Nils M. Kriege,
Petra Mutzel, and
Alexander Nover
Vol. 24, no. 3, pp. 155170, 2020. Regular paper.
Abstract Given an edgeweighted graph $G$ on $n$ nodes,
the NPhard $\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 fixedparameter 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} \cdot 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 1planar 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 fixedparameter tractable with respect to itself, we see that $\rm{M\small{AX}}$$\rm{C\small{UT}}$ is fixedparameter tractable with respect to the crossing number, even without a given drawing.
Moreover, the results naturally carry over to the minormonotoneversion of crossing number.

Submitted: August 2019.
Reviewed: December 2019.
Revised: January 2020.
Accepted: February 2020.
Final: February 2020.
Published: March 2020.
Communicated by
Giuseppe Liotta

Journal Supporters
