Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs

DOI10.1016/J.TCS.2020.11.030MaRDI QIDQ2220841zbMATH OpenOpenAlexFDO

Authors Christine Dahn, Nils Kriege, Julian Schilling, Petra Mutzel

Publication date 25 January 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

1-planar graphsfixed-parameter tractabilityweighted maximum cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We propose two fixed-parameter tractable algorithms for the weighted Max-Cut problem on embedded 1-planar graphs parameterized by the crossing number $k$ of the given embedding. A graph is called 1-planar if it can be drawn in the plane with at most one crossing per edge. Our algorithms recursively reduce a 1-planar graph to at most $3^k$ planar graphs, using edge removal and node contraction. Our main algorithm then solves the Max-Cut problem for the planar graphs using the FCE-MaxCut introduced by Liers and Pardella [23]. In the case of non-negative edge weights, we suggest a variant that allows to solve the planar instances with any planar Max-Cut algorithm. We show that a maximum cut in the given 1-planar graph can be derived from the solutions for the planar graphs. Our algorithms compute a maximum cut in an embedded weighted 1-planar graph with $n$ nodes and $k$ edge crossings in time $O(3^{k}cdot{n}^{3/2}logn)$.

Recommendations

• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• Maximum cut parameterized by crossing number
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• Parameterized complexity of 1-planarity
• Parameterized complexity of 1-planarity

Cites work

• 1-planarity of graphs with a rotation system
• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• 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
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• 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
• Graphs drawn with few crossings per edge
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Linear kernels and linear-time algorithms for finding large cuts
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Maximum balanced subgraph problem parameterized above lower bound
• Maximum cut parameterized by crossing number
• On some weakly bipartite graphs
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• Optimization, approximation, and complexity classes
• Parameterized complexity of 1-planarity
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• Reducibility among combinatorial problems
• 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

(6)

• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• Delta invariant for Eulerian digraphs
• Parameterized analysis and crossing minimization problems
• Complexity and polynomially solvable special cases of QUBO
• Quantum annealing versus digital computing. An experimental comparison
• Maximum cut parameterized by crossing number

This page was built for publication: Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs

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