Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00523
Maximum Cut Parameterized by Crossing Number
Markus Chimani,
Christine Dahn,
Martina Juhnke-Kubitzke,
Nils M. Kriege,
Petra Mutzel, and
Alexander Nover
Vol. 24, no. 3, pp. 155-170, 2020. Regular paper.
Abstract 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} \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 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.
|
Submitted: August 2019.
Reviewed: December 2019.
Revised: January 2020.
Accepted: February 2020.
Final: February 2020.
Published: March 2020.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|