Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded\n 1-Planar Graphs

2018/11/29 by Christine Dahn, Dahn, Christine, Nils M. Kriege +5
Computer Science · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1812.03074

openalex publication_date 2018/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• An FPT Algorithm for Max-Cut Parameterized by Crossing Number
• Parameterized Algorithms for Maximum Cut with Connectivity Constraints
• On the size of maximum cut in planar graphs
• Approximation Algorithms for Connected Maximum Cut and Related Problems
• Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs