Maximum cut parameterized by crossing number

DOI10.7155/JGAA.00523MaRDI QIDQ5119374zbMATH OpenOpenAlexFDO

Authors Markus Chimani, Christine Dahn, Martina Kubitzke, Nils Kriege, Petra Mutzel, Alexander Nover

Publication date 4 September 2020

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1903.06061

zbMATH Keywords

edge-weighted graphfixed-parameter tractable algorithm

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 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 $O(2^{k}cdotp(n+k))$, where $p$ is the polynomial running time for planar Max-Cut. The only previously known similar algorithm [8] is restricted to 1-planar graphs (i.e., at most one crossing per edge) and its dependency on $k$ is of order $3^k$ . A direct consequence of our result is that Max-Cut is fixed-parameter tractable w.r.t. the crossing number, even without a given drawing. Moreover, the results naturally carry over to the minor crossing number.

Recommendations

• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• Max-Cut parameterized above the Edwards-Erdős bound
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Crossing Numbers and Parameterized Complexity

Cites work

• (Meta) kernelization
• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An improved fixed-parameter algorithm for max-cut parameterized by crossing number
• Application of cut polyhedra. I
• Applications of cut polyhedra. II
• Computing crossing numbers in quadratic time
• Crossing Number is NP-Complete
• Crossing numbers of beyond-planar graphs
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Dividing a Graph into Triconnected Components
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Genus characterizes the complexity of certain graph problems: Some tight results
• Graph minors. XIII: The disjoint paths problem
• Graphs drawn with few crossings per edge
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 6783430 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Maximum s-t-flow with k crossings in O(k^3 n n) time
• On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
• Optimization via enumeration: A new algorithm for the max cut problem
• Optimization, approximation, and complexity classes
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• Reducibility among combinatorial problems
• String graphs. II: Recognizing string graphs is NP-hard
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Unifying maximum cut and minimum cut of a planar graph
• Weakly bipartite graphs and the max-cut problem

Cited in

(9)

• Parameterized analysis and crossing minimization problems
• Exact crossing number parameterized by vertex cover
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• An improved fixed-parameter algorithm for max-cut parameterized by crossing number
• Finding Folkman Numbers via MAX CUT Problem
• On the Maximum Crossing Number
• Complexity and polynomially solvable special cases of QUBO
• Quantum annealing versus digital computing. An experimental comparison
• Storylines with a protagonist

This page was built for publication: Maximum cut parameterized by crossing number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5119374)