A Linear Time Algorithm for a Variant of the MAX CUT Problem in Series Parallel Graphs

Abstract EN

Given a graph G=V,E, a connected sides cut U,V\U or δU is the set of edges of E linking all vertices of U to all vertices of V\U such that the induced subgraphs GU and GV\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.