A linear time algorithm for a variant of the max cut problem in series parallel graphs

2016/06/15 by Chaourar, Brahim
#90C27 #90C57 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1606.05240

Abstract

Given a graph G=(V, E), a connected sides cut (U, V\backslash U) or δ(U) is the set of edges of E linking all vertices of U to all vertices of V\backslash U such that the induced subgraphs G[U] and G[V\backslash U] are connected. Given a positive weight function w defined on E, the maximum connected sides cut problem (MAX CS CUT) is to find a connected sides cut Ω such that w(Ω) is maximum. MAX CS CUT is NP-hard. In this paper, we give a linear time algorithm to solve MAX CS CUT for series parallel graphs. We deduce a linear time algorithm for the minimum cut problem in the same class of graphs without computing the maximum flow.

Related

• Connected max cut is polynomial for graphs without K₅ backslash e as\n a minor
• Exact Algorithms for MaxCut on Split Graphs
• Approximation Algorithms for Connected Maximum Cut and Related Problems
• Near-optimal approximation algorithm for simultaneous Max-Cut
• Parameterized Algorithms for Maximum Cut with Connectivity Constraints