A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs (Q1748508)

Summary: Given a graph \(G = \left(V, E\right)\), a connected sides cut \(\left(U, V \backslash U\right)\) or \(\delta \left(U\right)\) 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 \left[U\right]\) and \(G \left[V \backslash U\right]\) 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 \(\Omega\) such that \(w \left(\Omega\right)\) 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.