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

Authors: Brahim Chaourar
Journal: Advances in Operations Research
 (2017)

---

## Abstract

Given a graphG=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.


---

## Body

## 1. Introduction

Sets and their characteristic vectors will not be distinguished. We refer to Bondy and Murty [1] about graph theory terminology and facts.Given an undirected graphG=V,E and positive weights wij=wji on the edges i,j∈E, the maximum cut problem (MAX CUT) is that of finding the set of vertices S that maximizes the weight of the edges in the cut S,V\S or δS or δV\S, that is, the weight of the edges with one endpoint in S and the other in V\S. The (decision variant of the) MAX CUT is one of the Karp s original NP-complete problems [2] and has long been known to be NP-complete even if the problem is unweighted, that is, if wij=1 for all i,j∈E [3]. This motivates the research to solve the MAX CUT problem in special classes of graphs. The MAX CUT problem is solvable in polynomial time for the following special classes of graphs: planar graphs [4–6], line graphs [7], graphs with bounded treewidth, or cographs [8]. But the problem remains NP-complete for chordal graphs, undirected path graphs, split graphs, tripartite graphs, graphs that are the complement of a bipartite graph [8], and planar graphs if the weights are of arbitrary sign [9]. Besides its theoretical importance, the MAX CUT problem has applications in circuit layout design and statistical physics [10]. For a comprehensive survey of the MAX CUT problem, the reader is referred to Poljak and Tuza [11] and Ben-Ameur et al. [12]. The best known algorithm for MAX CUT in planar graphs has running time complexity On3/2log⁡n, where n is the number of vertices of the given graph [13]. This algorithm is not a linear time one. The main result of this paper is to exhibit a linear time algorithm for a special variant of MAX CUT in series parallel graphs. Series parallel graphs can be used to model series and parallel electric circuits [14]. Another motivation is that there is not a known linear time algorithm for the MAX CUT problem or any one of its NP-hard versions in any special class of graphs till today. This motivates the research on linear time algorithms in special classes of graphs for our problem which is an NP-hard variant of MAX CUT. Finally, many NP-hard problems have been studied in series parallel graphs [15–31] but not all outputed a linear time algorithm for the considered problem.Let us give some definitions. Given an undirected graphG=V,E and a subset of vertices U, a connected sides cut δU is a cut where both induced subgraphs GU and GV\U are connected. Special connected sides cuts are trivial cuts, that is, cuts with one single vertex in one side (when this vertex is not a disconnecting vertex). The corresponding weighted variant of MAX CUT for connected sides cuts is called MAX CONNECTED SIDES CUT problem (MAX CS CUT). It is clear that MAX CUT and MAX CS CUT are the same problem for complete graphs. Since MAX CUT is NP-hard for complete graphs (see [2]), then MAX CS CUT is NP-hard in the general case. Another motivation is that MAX CS CUT gives a lower bound for MAX CUT.A parallel closure of a graph is an induced subgraph on two vertices. A series extension of the graphG=V,E based on the edge e∈E is adding a vertex v of degree 2 in the middle of e in order to have two edges instead of e. A parallel extension of G based on the edge e is adding an edge f having the same incident vertices as e. Series parallel graphs are graphs obtained by applying recursively series and/or parallel extensions starting from one edge. A series degree of a vertex v in a graph G is the degree of v after replacing every parallel closure of G by one single edge. A series labeling of the vertices of a series parallel graph is a labeling of the vertices from 0 to n-1=V-1 starting from the first two vertices v0 and v1 and so on to the last added vertex. Any series parallel graph contains at least one vertex of series degree 2. So, given a vertex v of series degree 2 with the two parallel closures P0 and P1 incident to v, and the two adjacent vertices u0 and u1 to v, we can contract all edges of P0 (or P1) and replace v by u0 (or u1), and we obtain a new series parallel graph with a new vertex of series degree 2. Each involved graph in any step of this process is labeled Gj, 0≤j≤n-1, with Gn-1=G, and G1 is the induced subgraph on the two vertices v0 and v1.LetG1 and G2 be two graphs with ej an edge of Gj, j=1,2. The 2-sum of G1 and G2, denoted by G1⊕eG2 or G1⊕2G2, based on the edges e1 and e2 is the graph obtained by identifying e1 and e2 on an edge e and keeping Gj\ej, j=1,2, as they are.We say that a problem is linear for a class of graphs if there is a linear time algorithm to solve it in such class.The remaining of the paper is organized as follows: in Section2, we give a linear time algorithm for MAX CS CUT in series parallel graphs; in Section 3, we prove that 2-sums preserve the linearity of MAX CS CUT. We deduce a linear time algorithm for MIN CUT in series parallel graphs in Section 4, and we conclude in Section 5.


## 2. MAX CS CUT Is Linear for Series Parallel Graphs

MAXCSCUTSP AlgorithmInput.A series parallel graph G=(V,E) with a series labeling of V, a positive weight function w defined on E.Output.A w-maximum connected sides cut Ω in G.(0)
Begin(1)
j≔n-1;(2)
Whilej>1 do(3)
Begin(4)
LetP0 and P1 be the two parallel closures incident to vj in Gj:(5)
IfwP0>wP1 then contract P1;(6)
Else: contractP0;(7)
j≔j-1;(8)
End of While(9)
j≔2;(10)
Ω≔E(G1);(11)
Whilej≤n-1 do(12)
Begin(13)
LetP0 and P1 the two parallel closures incident to vj in Gj:(14)
IfwP0+wP1>wΩ then Ω≔P0∪P1;(15)
j≔j+1;(16)
End of While(17)
End of MAXCSCUTSP algorithm.This algorithm has two phases: Phase I (steps (1)–(6)) and Phase II (steps (9)–(16)). In each step, we do roughlyn operations, so the complexity of MAXCSCUTSP is On, where n=V.Theorem 1.
MAXCSCUTSP algorithm solves MAX CS CUT in series parallel graphs.Proof.
The summary of the algorithm is as follows: MAXCSCUT chooses a vertexv with series degree 2 (step (4)) and contracts the less weighted parallel closure incident to v (steps (5) and (6)), and so on, until the resulting graph becomes G1, which is the starting single parallel closure (Phase I). In G1, the w-maximum connected sides cut is EG1 (step (10)). After that, it goes in the reverse path (Phase II): the w-maximum connected sides cut is either the trivial cut based on the current vertex vj with series degree 2 or the current computed connected sides cut (step (14)). Let vj be the chosen vertex with series degree 2 in Gj, and let P0 and P1 be the two parallel closures incident to vj. Without loss of generality, we can suppose that wP0<wP1 and Gj-1=Gj/P0. Let Ωj be the w-maximum connected sides cut in Gj, 1≤j≤n-1. It suffices to prove that Ωj=max⁡wΩj-1,wP0∪P1.
LetΩ be a connected sides cut in Gj distinct from P0∪P1. Since wP0<wP1, we have only two cases.
Case 1. P1⊆Ω, then Ω is a connected sides cut in Gj-1=Gj/P0 containing P1. And vice versa, any connected sides cut in Gj-1=Gj/P0 containing P1 is a connected sides cut in Gj containing P1.
Case 2. P1⊈Ω, then Ω is a connected sides cut in Gj-1=Gj/P0 not containing P1. And vice versa, any connected sides cut in Gj-1=Gj/P0 not containing P1 is a connected sides cut in Gj not containing P1.
So the connected sides cuts candidates for thew-maximum connected sides cut in Gj and Gj-1 are the same, except P0∪P1.Note that MAXCSCUTSP algorithm solves MAX CS CUT in series parallel graphs even for arbitrary sign weight functions.


## 3. 2-Sums Preserve Linearity of MAX CS CUT

LetCG be the class of connected sides cuts of G. We need the following lemma.Lemma 2.
One hasCG1⊕2G2=Ωj∈CGj:ej∉Ωj,j=1,2∪Ω1⊕2Ω2:Ωj∈CGjandej∈Ωj,j=1,2.We can now state one consequence of this as follows.Theorem 3.
If MAX CS CUT is linear for two given graphsG1 and G2, then it is also linear for G1⊕2G2.Proof.
It follows from Lemma2 that a w-maximum connected sides cut in G1⊕eG2 is one of the three following connected sides cuts:
(cases 1-2) one of the twow-maximum connected sides cuts in Gj which does not contain ej,j=1,2, or
(case 3) the 2-sum of thew-maximum connected sides cuts containing ej, j=1,2.
To find aw-maximum connected sides cut in Gj which does not contain ej, j=1,2 (case 2), we have to contract ej. We need then to perform at most cj1nj-1 operations, where cj1, j=1,2, is the linearity coefficient of the algorithm solving MAX CS CUT in Gj/ej, j=1,2, and nj, j=1,2, is the number of vertices of Gj, j=1,2 (by induction).
To findΩ1⊕2Ω2 (case 3), we have to put w(ej), j=1,2, as big as possible, for example, sum of the positive weights of all edges, and find Ωj, j=1,2. In this case, we need to perform at most c12n1+c22n2 operations (by induction), where cj2, j=1,2, is the linearity coefficient of the algorithm solving MAX CS CUT in Gj, j=1,2.
So we have to compute MAX CS CUT twice in each graph and compare three cuts. The total number of operations is then bounded byc11+c12n1+c21+c22n2-c11+c21≤cmaxn+1, where n is the number of vertices of G1⊕2G2 and cmax=max⁡c11+c12,c21+c22. So linearity of the problem is preserved.The same property holds forK4, the unique excluded minor for series parallel graphs, which means that the class of graphs for which MAX CS CUT is linear is larger than series parallel graphs.Lemma 4.
MAX CS CUT is linear forK4.Proof.
It is not difficult to see thatCK4=7: for any perfect matching of K4 (there are 3 perfect matchings in K4), we have a connected sides cut (by removing the perfect matching), and for any vertex of K4 (there are 4 vertices), the corresponding trivial cut is a connected sides one. We can reduce the number of cuts to be considered as follows.
Lete=uv∈EK4 and f=ab∈EK4 such that e,f is a perfect matching of K4. We have the following property. (1)2we≥wδuiffwδv≥wδu,v.So by such comparisons (for each perfect matching of K4), we eliminate step-by-step cuts to be considered for comparison between them.We have then the following corollary directly from Theorems1 and 3 and Lemma 4.Corollary 5.
MAX CS CUT is linear for 2-sums of series parallel graphs and copies ofK4.


## 4. MIN CUT Is Linear for Series Parallel Graphs

MINCUTSP AlgorithmInput.A series parallel graph G=V,E with a series labeling of V, a positive weight function w defined on E.Output.A w-minimum connected sides cut Ω in G.We keep the same steps as MAXCSCUTSP algorithm except the following changes in two steps:(5)
IfwP0<wP1 then contract P1;(14)
IfwP0+wP1<wΩ then Ω≔P0∪P1;Since this algorithm is similar to MAXCSCUTSP, then its complexity isO(n), where n=|V|.And it is not difficult to see, similarly to MAXCSCUTSP, that MINCUTSP gives the minimum weighted connected sides cut in a series parallel graph without computing the maximum flow.We can conclude with the following result.Theorem 6.
Given a connected graphG=(V,E) and a positive weight function w defined on E, then any w-minimum cut is a connected sides cut of G.Proof.
LetδU be a cut with GU disconnected. It suffices to prove that δU is not a w-minimum cut. Let G[U1] be one connected component of GU. Since G is connected, then w(V\U,U1)>0 (i.e., there are edges between V\U and U1). It follows that wδU\U1=w(δ(U))-wV\U,U1<wδU.Other consequences of Lemma2 and Theorem 6 are the following corollaries.Corollary 7.
2-sums preserve the linearity of MIN CUT.Corollary 8.
MIN CUT is linear for 2-sums of series parallel graphs and copies ofK4.


## 5. Conclusion

We have introduced a new variant of MAX CUT: MAX CS CUT, which is also NP-hard. We have provided two linear time algorithms for MAX CS CUT and MIN CUT, respectively, in series parallel graphs. We have proved that 2-sums preserve the linearity of MAX CS CUT and MIN CUT. Further directions are to study MAX CS CUT in larger classes of graphs than series parallel graphs.



---

*Source: 1267108-2017-12-10.xml*