Connected max cut is polynomial for graphs without K₅ backslash e as\n a minor

2019/03/29 by Brahim Chaourar, Chaourar, Brahim
Computer Science · #90C27 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1903.12641

openalex publication_date 2019/03/29 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28

Abstract

Given a graph G=(V, E), a connected cut \δ (U) is the set of edges of\nE linking all vertices of U to all vertices of V backslash U such that the\ninduced subgraphs G[U] and G[V backslash U] are connected. Given a positive\nweight function w defined on E, the connected maximum cut problem (CMAX\nCUT) is to find a connected cut \Ω such that w(\Ω) is maximum among\nall connected cuts. CMAX CUT is NP-hard even for planar graphs. In this paper,\nwe prove that CMAX CUT is polynomial for graphs without K₅ backslash e as a\nminor. We deduce a quadratic time algorithm for the minimum cut problem in the\nsame class of graphs without computing the maximum flow.\n

Related

• Approximation Algorithms for Connected Maximum Cut and Related Problems
• A linear time algorithm for a variant of the max cut problem in series parallel graphs
• Parameterized Algorithms for Maximum Cut with Connectivity Constraints
• Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
• Computing the Largest Bond and the Maximum Connected Cut of a Graph