An FPT Algorithm for Max-Cut Parameterized by Crossing Number

2019/04/10 by Yasuaki Kobayashi, Yusuke Kobayashi, Kobayashi, Yasuaki +5
Computer Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1904.05011

Abstract

The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algorithm for the problem on `almost' planar graphs: Given an n-vertex graph and its drawing with k crossings, our algorithm runs in time O(2^k(n+k)^3/2 log (n + k)). Previously, Dahn, Kriege and Mutzel (IWOCA 2018) obtained an algorithm that, given an n-vertex graph and its 1-planar drawing with k crossings, runs in time O(3^k n^3/2 log n). Our result simultaneously improves the running time and removes the 1-planarity restriction.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Related

• On Graph Crossing Number and Edge Planarization
• Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded\n 1-Planar Graphs
• An Algorithm for the Graph Crossing Number Problem
• A Unified FPT Framework for Crossing Number Problems
• On the Maximum Crossing Number