arXiv:1606.05240v2 [cs.DS] 18 Mar 2017

A LINEAR TIME ALGORITHM FOR A VARIANT OF
THE MAX CUT PROBLEM IN SERIES PARALLEL
GRAPHS
BRAHIM CHAOURAR
Abstract. 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 G[U ]
and G[V \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.

2010 Mathematics Subject Classification: 90C27, 90C57.
Key words and phrases: maximum cut, maximum connected sides
cut, linear time algorithm, series parallel graphs, minimum cut.
1. Introduction
Sets and their characterisitic vectors will not be distinguished. We
refer to Bondy and Murty [5] about graph theory terminolgy and facts.
Given an undirected graph G = (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 Karps original NP-complete problems
[9], 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 [6]. 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 [2, 8, 10], line graphs [7], graphs
with bounded treewidth, or cographs [4]. 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
[4] and planar graphs if the weights are of arbitrary sign [13]. Besides
1

2

BRAHIM CHAOURAR

its theoretical importance, the MAX CUT problem has applications in
circuit layout design and statistical physics [1]. For a comprehensive
survey of the MAX CUT problem, the reader is referred to Poljak and
Tuza [11] and Ben-Ameur et al. [3]. The best known algorithm for
MAX CUT in planar graphs has running time complexity O(n3/2 logn),
where n is the number of vertices of the graph [12]. The main result of
this paper is to exhibit a linear time algorithm for a special variant of
MAX CUT in series parallel graphs.
Let us give some definitions. Given an undirected graph G = (V, E) and
a subset of vertices U, a connected sides cut δ(U) is a cut where both
induced subgraphs G[U] and G[V \U] are connected. Special connected
sides cuts are trivial cuts, i.e. cuts with one single vertex in one side.
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 [9]) 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 graph G = (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 .
Let G1 and G2 be two graphs with ej an edge of Gj , j = 1, 2. The
2-sum of G1 and G2 , denoted G1 ⊕e G2 , based on the edges e1 and e2 is
the graph obtained by identifying e1 and e2 on an edge e, and keeping

A LINEAR TIME ALGORITHM FOR A VARIANT OF THE MAX CUT PROBLEM IN SERIES PARALLEL GR

Gj /ej , j = 1, 2, as it is.
We say that MAX CS CUT 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 section 2, 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 Algorithm:
Input: 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) While j > 1 do
3) Begin
4) Let P0 and P1 be the two parallel closures incident to vj in Gj :
5) If w(P0 ) > w(P1 ) then contract P1 ;
6) Else: contract P0 ;
7) j := j − 1;
6) End of While
7) j := 2;
8) Ω := E(G1 );
9) While j ≤ n − 1 do
10) Begin
11) Let P0 and P1 the two parallel closures incident to vj in Gj :
12) If w(P0 ) + w(P1 ) > w(Ω) then Ω := P0 ∪ P1 ;
13) j := j + 1;
14) End of While
15) End of MAXCSCUTSP algorithm.
This algorithm has two phases: Phase I (steps 1-6) and Phase II (steps
7-14). In each step, we do roughly n operations, so the complexity of
MAXCSCUTSP is O(n), where n = |V |.
Theorem 2.1. MAXCSCUTSP algorithm solves MAX CS CUT in
series parallel graphs.
Proof. The summary of the algorithm is as follows: MAXCSCUT chooses
a vertex v with series degree 2 (step 4) and contract the less weighted
parallel closure incident to v (steps 5 and 6). And so on the resulted
graph until it reaches G1 , the starting single parallel closure (Phase

4

BRAHIM CHAOURAR

I). In G1 , the w-maximum connected sides cut is E(G1 ) (step 8). 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 12).
Let vj be the chosen vertex with series degree 2 in Gj , P0 and P1 the
two parallel closures incident to vj . Without loss of generality, we can
suppose that w(P0) < w(P1) and Gj−1 = Gj /P0 . Let Ωj be the wmaximum connected sides cut in Gj , 1 ≤ j ≤ n − 1. It suffices to prove
that w(Ωj ) = Max{w(Ωj−1 ), w(P0 ∪ P1 )}.
Let Ω be a connected sides cut in Gj distinct from P0 ∪ P1 . Since
w(P0) < w(P1 ), 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 the w-maximum connected
sides cut in Gj and Gj−1 are the same, except P0 ∪ P1 .

Note that MAXCSCUT algorithm solves MAX CS CUT in series
parallel graphs even for arbitrary sign weight functions.
3. 2-sums preserve linearity of MAX CS CUT
Let C(G) be the class of connected sides cuts of G. We need the
following lemma.
Lemma 3.1. C(G1 ⊕e G2 ) = {Ωj ∈ C(Gj ) : ej ∈
/ Ωj , j = 1, 2} ∪ {Ω1 ⊕e
Ω2 : Ωj ∈ C(Gj ) and ej ∈ Ωj , j = 1, 2}.
It follows that a w-maximum connected sides cut in G1 ⊕e G2 is one
of the three following connected sides cuts:
(cases 1-2) one of the two w-maximum connected sides cuts in Gj which
does not contain ej , j = 1, 2,
(case 3) or the 2-sum of the w-maximum connected sides cuts containing ej , j = 1, 2.
To find a w-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 c(nj − 1) operations, where c is the linearity coefficient and
nj , j = 1, 2 is the number of vertices of Gj (by induction).
To find Ω1 ⊕e Ω2 (case 3), we have to put w(ej ), j = 1, 2, as big as possible, e.g. sum of the positive weights of all edges, and find Ωj , j = 1, 2.

A LINEAR TIME ALGORITHM FOR A VARIANT OF THE MAX CUT PROBLEM IN SERIES PARALLEL GR

In this case, we need to perform at most c(n1 + n2 ) operations (by induction).
So we have to compute MAX CS CUT twice in each graph and compare three cuts. The total number of operations is bounded then by
2c(n1 + n2 − 1) = 2c(n − 1), where n is the number of vertices of
G1 ⊕e G2 . So linearity of the problem is preserved.
4. MIN CUT is linear for series parallel graphs
MINCUTSP Algorithm:
Input: 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) If w(P0 ) < w(P1 ) then contract P1 ;
12) If w(P0 ) + w(P1 ) < w(Ω) then Ω := P0 ∪ P1 ;
Since this algorithm is similar to MAXCSCUTSP, then its complexity
is O(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 4.1. Given a connected graph G = (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 G[U] disconnected. It suffices to prove
that δ(U) is not a w-minimum cut. Let G[U1 ] be one connected component of G[U]. 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)) − w(V \U, U1 ) < w(δ(U)).

Another consequence of Lemma 3.1 and Theorem 4.1 is the following
corollary.
Corollary 4.2. 2-sums preserves the linearity of MIN CUT.
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

6

BRAHIM CHAOURAR

and MIN CUT. Further directions are to study MAX CS CUT in larger
classes of graphs than series parallel graphs.
Acknowledgements The author is grateful to the deanship of Scientific Research at Al Imam Mohammad Ibn Saud Islamic University
(IMSIU) for supporting financially this research under the grant No
331203.
References
[1] F. Barahona, M. Grtschel, M. Jnger, and G. Reinelt (1988), An application
of combinatorial optimization to statistical physics and circuit layout design,
Operations Research 36: 493-513.
[2] F. Barahona, (1990), Planar multicommodity flows, max cut, and the Chinese
postman problem, in: Polyhedral Combinatorics, Proceedings DIMACS Workshop, Morristown, New Jersey, 1989, W. Cook, P.D. Seymour (eds.) [DIMACS
Series in Discrete Mathematics and Theoretical Computer Science, Volume 1],
American Mathematical Society, Providence, Rhode Island: 189202.
[3] W. Ben-Ameur, A. R. Mahjoub, and J. Neto, The maximum cut problem, in:
Paradigms of Combinatorial Optimization, Problems and New Approaches, 2nd
edition, J. Wiley and Sons, USA, V. T. Paschos (ed.), 2014.
[4] H. L. Bodlaender and K. Jansen (2000), On the Complexity of the Maximum
Cut Problem, Nordic Journal of Computing 7(1): 14-31.
[5] J. A. Bondy and U. S. R. Murty (2008), Graph Theory with Applications, Elsevier, New York.
[6] M. R. Garey, D. S. Johnson, and L. Stockmeyer (1976), Some simplified NPcomplete graph problems, Theoretical Computer Science 1: 237-267.
[7] V. Guruswami (1999), Maximum cut on line and total graphs, Discrete Applied
Mathematics 92 (2-3): 217-221.
[8] F. Hadlock (1975), Finding a maximum cut of a planar graph in polynomial
time, SIAM Journal on Computing 4: 221-225.
[9] R. M. Karp (1972), Reducibility among combinatorial problems, in: Complexity
of Computer Computations, Miller and Thatcher, Plenum Press: 85-104.
[10] G. I. Orlova and Y. G. Dorfman (1972), Finding the maximal cut in a graph,
Engineering Cybernetics: 502-506.
[11] Poljak and Tuza (1995), The max-cut problem – a survey, in: Special Year
on Combinatorial Optimization, W. Cook, L. Lovasz and P. Seymour (eds.),
DIMACS series in Discrete Mathematics and Theoretical Computer Science,
American Mathematical Society, 1995.
[12] W.-K. Shih, S. Wu, and Y. S. Kuo (1990), Unifying maximum cut and minimum cut of a planar graph, IEEE Transactions on Computers 39 (5): 694697.
[13] A. P. Terebenkov (1991), NP-completeness of maximum-cut and cycle-covering
problems for a planar graph, Cybernetics and Systems Analysis 27 (1): 16-20.
Department of Mathematics and Statistics, Al Imam Mohammad Ibn
Saud Islamic University (IMSIU), P.O. Box 90950, Riyadh 11623, Saudi
Arabia, Correspondence address: P.O. Box 287574, Riyadh 11323, Saudi
Arabia
E-mail address: bchaourar@hotmail.com

