Geodesic
Maximum Cut Parameterized by Crossing Number
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 155-170.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00523
Keywords: maximum cut, crossing number, minor crossing number, fixed parameter tractable 
@article{JGAA_2020_24_3_a1,
     author = {Markus Chimani and Christine Dahn and Martina Juhnke-Kubitzke and Nils Kriege and Petra Mutzel and Alexander Nover},
     title = {Maximum {Cut} {Parameterized} by {Crossing} {Number}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {155--170},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2020},
     doi = {10.7155/jgaa.00523},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00523/}
}
TY  - JOUR
AU  - Markus Chimani
AU  - Christine Dahn
AU  - Martina Juhnke-Kubitzke
AU  - Nils Kriege
AU  - Petra Mutzel
AU  - Alexander Nover
TI  - Maximum Cut Parameterized by Crossing Number
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 155
EP  - 170
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00523/
DO  - 10.7155/jgaa.00523
LA  - en
ID  - JGAA_2020_24_3_a1
ER  - 
%0 Journal Article
%A Markus Chimani
%A Christine Dahn
%A Martina Juhnke-Kubitzke
%A Nils Kriege
%A Petra Mutzel
%A Alexander Nover
%T Maximum Cut Parameterized by Crossing Number
%J Journal of Graph Algorithms and Applications
%D 2020
%P 155-170
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00523/
%R 10.7155/jgaa.00523
%G en
%F JGAA_2020_24_3_a1
Markus Chimani; Christine Dahn; Martina Juhnke-Kubitzke; Nils Kriege; Petra Mutzel; Alexander Nover. Maximum Cut Parameterized by Crossing Number. Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 155-170. doi : 10.7155/jgaa.00523. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00523/

Cité par Sources :