The minimum Gc cut problem

Itamar Elem 1 , Refael Hassin 2 , and Jérôme Monnot4,3

1. [email protected]

2. School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel. [email protected]

3. PSL, Université Paris-Dauphine,

Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France
4. CNRS, LAMSADE, UMR 7243
[email protected]

Abstract. In this paper we study the complexity and approximability of the Gc -cut problem. Given a
complete undirected graph Kn = (V ; E) with |V | = n, edge weighted by w(vi , vj ) ≥ 0 and an undi-
rected cluster graph, Gc = (Vc , Ec ), with |V c| = k, a k-cut is a partition V1 , . . . , VP
k of V (G) such that
Vi 6= ∅ for i = 1, . . . , k. The Gc -cut problem is to compute a k-cut minimizing (i,j)∈Ec w(Vi , Vj )
P
where w(Vi , Vj ) = p∈Vi ,q∈Vj w(p, q). Denote Gc as cluster graph and its vertices as clusters. We
show that the Gc -cut problem is NP-hard and even not approximable in the general case and remains
NP-hard for cluster trees. In particular, we give a complete characterization of hard cases for cluster
graphs with at most four vertices by proving that the Gc -cut problem is NP-hard if and only if Gc
is isomorphic to 2K2 . We also identify some cases where the Gc -cut problem is either polynomial or
NP-hard. Finally, we propose polynomial approximation results for the Gc -cut problem when the edge
weights of G satisfy the triangle inequality, or when the weights are strictly positive.

Keywords: Cut in graphs, NP-hardness, polynomial, approximation algorithms.

1 Introduction

The problem considered in this paper is a generalization of the the minimum k-cut problem, and it can be
defined as follows:

Definition 1. Let Kn = (V, E) be a complete undirected graph with |V | = n and edge weights w(vi , vj ) ≥
0. Given is also an undirected P cluster graph, Gc = (Vc , Ec ), with |Vc |P= k. The Gc - CUT PROBLEM is
to compute a k-cut minimizing (i,j)∈Ec w(Vi , Vj ), where w(Vi , Vj ) = (p,q)∈Vi ×Vj ,(p,q)∈E w(p, q). The
restriction to metric distance w (i.e., satisfying triangular inequality1) is called the METRIC Gc - CUT PROB -
LEM.

Cut problems in graphs are important optimization problems because VLSI system design, parallel com-
puting systems, clustering, network reliability and cutting planes, etc. appearing in real-life situations may
often be modeled as graph partitioning problems (see for instance [1, 22]). A survey on the approximability
of cut problems can be found in Shmoys [23]. The k- CUT PROBLEM has been well studied in the literature
and consists of finding a partition V1 , . . . , Vk such that Vi 6= ∅, i = 1, . . . , k (called k-cut) of the vertices
1
∀x, y, z ∈ V , w(x, y) ≤ w(x, y) + w(y, z).
2 Itamar Elem, Refael Hassin, Jérôme Monnot

P
V (G) of a simple graph G = (V, E) edge weighted by w(vi , vj ) ≥ 0, minimizing 1≤i<j≤k w(Vi , Vj ).
Goldschmidt and Hochbaum [6] proved that the problem in ordinary graphs is NP-hard when k is part of the
2
input and gave the first polynomial-time algorithm for fixed k with running time nO(k ) . Since the results
of Goldschmidt and Hochbaum [6] on the minimum k-cut problem, many other results are appeared in the
literature. For instance, the running time of their algorithm has been improved by Kamidoi et al. [15] and
Xiao [28]. Currently, the best results are the O(n2(k−1) log n3 )-time Monte Carlo algorithm due to Karger
and Stein [12] and the O(n2k )-time deterministic algorithm due to Thorup [26]. Furthermore, Nagamochi
et al. [19, 20] proved that the minimum k-cut problem can be solved in O(mnk ) time for k = 4, 5, 6. The
minimum k-cut problem has also drawn much attention in the literature for small values of k. The minimum
2-cut problem is commonly known as the minimum cut problem. Another version, the minimum 2-way cut
problem, is the minimum (s, t) cut problem, which asks to find a minimum cut that separates two given
vertices s and t. These two problems are fundamental problems in the subject of graph connectivity. For
ordinary graphs, the minimum cut problem can be solved in O(mn + n2 log n) time by Nagamochi and
Ibaraki’s algorithm [19] or Stoer and Wagner’s algorithm [24], and the minimum (s, t) cut problem can be
2
solved in O(mn log nm ) time by Goldberg and Tarjan’s algorithm [8]. For the minimum 3-cut problem in
ordinary graphs, Kapoor [10] and Kamidoi et al. [15] showed that it can be solved by using O(n3 ) maxi-
mum flow computations. Burlet and Goldschmidt [3] and Nagamochi and Ibaraki [19] improved the result
to O(n2 ). The Multiway k-cut problem for k ≥ 2 is one generalization of the minimum (s, t) cut problem.
This problem also known as the Multiterminal k-cut problem can be defined as follow: given a weighted
complete graph, Kn = (V, E) and a set of terminals S = {s1 , . . . , sk }, a multiway cut is a set of edges
that leaves each of the terminals in a separate component. In other words, the goal of the Multiway k-cut
problem is to find a k-cut (V1 , . . . , Vk ) where si ∈ Vi of minimum weight. The Multiway k-cut problem is
know to be polynomial for k = 2 and and NP-hard when k ≥ 3 is fixed [4].
When the cluster graph Gc is a k-clique, the k- CUT PROBLEM and the Gc - CUT PROBLEM coincide. In
contrast, we show that the Gc - CUT PROBLEM is NP-hard when k is fixed.
In this paper, we mainly study the complexity and the approximability of the Gc - CUT PROBLEM accord-
ing the structure of the cluster graph Gc . In Section 2, the notations and main definitions are introduced.
In Section 3, complexity results are presented while the Section 4 gives some polynomial solvable cases
for the Gc - CUT PROBLEM. For instance, as a corollary of the results given in this paper we will show for
the cluster graphs Gc with at most 4 vertices, the Gc - CUT PROBLEM is NP-hard if and only if Gc = 2K2 .
Finally, in Section 5, we propose polynomial approximation results when the weights are either positives or
satisfy the triangle inequality. More exactly for the general case, we present a α-approximation in linear time
where wmin = mine∈E w(e), wmax = maxe∈E w(e), and α = w wmin (here, we assume that wmin > 0) and
max

a 3-approximation is given for the METRIC Gc - CUT PROBLEM when the number of vertices of the cluster
graph is fixed.

2 Definitions and preliminaries

All graphs in this paper are finite, simple and loopless. Let G = (V, E) be a graph. An edge between u and
v will be denoted (u, v). For a vertex v ∈ V , let NG (v) denote the set of vertices in G that are adjacent to v,
i.e., the neighbors of v, and the degree of v is dG (v) = |NG (v)|. A leaf is a vertex v such that degG (v) = 1.
For S ⊂ V (G), the neighborhood of S is NG (S) = {v ∈ V : ∃u ∈ S, (u, v) ∈ E}. In particular,
2
NG (v) = NG (NG (v)). Vertex u is a nested neighbor of vertex v if (u, v) ∈ / E and NG (u) ⊆ NG (v).
They are twins if NG (u) = NG (v). The contracted graph of G from S, denoted G(S), is the simple graph
G(S) = (V ′ , E ′ ) where V ′ = V \ S ∪ {vS } and (u, v) ∈ E ′ if u, v ∈ / S ∪ {vS } and (u, v) ∈ E or if
 The minimum Gc cut problem 3

u = vS , v ∈
/ S ∪ {vS } and ∃s ∈ S with (s, v) ∈ E. Throughout
P this paper, we use the following notation for
′ ′
a edge weighted
P graph (G, w): for E ⊆ E(G), w(E ) = e∈E ′ w(e) and for v ∈ V (G) and U ⊆ V (G),
w(v, U ) = u∈U w(v, u).
Now, we indicate some classes of graphs used in this paper:
Definition 2. Consider a graph G = (V, E) such that |V | = k.
1. G is a matching graph, denoted wK2 , if k = 2w and deg(v) = 1 ∀v ∈ V .
2. G is a path graph, denoted Pk , if its edges form an induced path on k vertices.
3. G is a cycle graph, denoted Ck , if its edges constitute an induced cycle on k vertices.
4. G = Kd1 ,...,dr =
Pr(V, E) is a complete r-partite graph if there exists a partition L1 , . . . , Lr of V with
di = |Li |, and i=1 di = k such that for every i 6= j ∈ {1, . . . , r}, u, v ∈ Li ⇒ (u, v) ∈ / E and
u ∈ Li , v ∈ Lj ⇒ (u, v) ∈ E. The sets Li are the color classes of G. A biclique is a complete bipartite
graph.
5. G = (S, K; E) is a split graph if V (G) = S ∪ K where K ∩ S = ∅, S is a stable set and K is a clique
of G of maximum size. It is called restricted split graph if degG (v) < |V (G)| − 1 for every v ∈ K. For
instance, P4 = (v1 , v2 , v3 , v4 ) is a restricted split graph with K = {v2 , v3 } and S = {v1 , v4 }.
Let us start by giving some definitions:

Definition 3. Let Gc be a cluster graph with |V (Gc )| = k. The MULTIWAY Gc - CUT PROBLEM is the Gc -
CUT PROBLEM where given I = (G, w), S ⊆ V (Gc ) and |S| vertices {v1 , . . . , v|S| } ⊆ V with |S| ≤ k,
we want to find an optimal Gc -cut V1 , . . . , Vk on I such that vi ∈ Vi for i ∈ S. The d- SIZE RESTRICTED
Gc - CUT PROBLEM is the Gc -cut problem where an integer vector (d1 , . . . , dk ) is given with the instance.
Pk
The goal is to find an optimal Gc -cut (V1 , . . . , Vk ) on I where n ≥ i=1 di and such that |Vi | ≥ di . Finally,
the RESTRICTED Gc - CUT PROBLEM is the d- SIZE RESTRICTED Gc - CUT PROBLEM when n = ki=1 di . In
P
other words, |Vi | = di for every i = 1, . . . , k.

Note that if the cluster graph Gc is a complete r-partite for some r (in particular, a complete graph),
then the MULTIWAY Gc - CUT PROBLEM with |S| = 1 is equivalent to the Gc - CUT PROBLEM, and then is
polynomial if k is fixed.

Theorem 1. The complexity of the MULTIWAY Kk - CUT PROBLEM when k ≥ 2 is fixed is polynomial when
|S| = 2 and NP-hard when |S| > 2.

Proof. We divide the proof to the following sub cases.

1. |S| = k.
(a) |S| = 2. The problem is equivalent to the minimum (s, t) cut problem. Thus, the problem is poly-
nomial.
(b) |S| ≥ 3. The problem is equivalent to the minimum Multiway k-cut problem with |S| ≥ 3. Hence,
the problem is NP-hard.
2. where k > |S|. Denote l = k − |S| > 0
(a) |S| > 2. Let Kn = (V, E), S ⊂ V, |S| > 2 be an instance of the minimum Multiway |S|-cut
problem. Consider an instance of the MULTIWAY Kk - CUT PROBLEM described as follow:
– S ′ = S.
– Kn+l = (V ′ , E ′ ).
– V ′ = V ∪ {x1 , . . . , xl }
– E ′ = E ∪ E1 ∪ E2 where
4 Itamar Elem, Refael Hassin, Jérôme Monnot

– E1 = {(xi , v) : i = 1, . . . , l, v ∈ V } and w(e) = 0 for e ∈ E1 .

– E2 = {(xi , xj ) : 1 ≤ i < j ≤ l} and w(e) = 0 for e ∈ E2 .
Solving the MULTIWAY Gc - CUT PROBLEM where Gc = Kk for Kn+l , S ′ optimally we must assign
each xi , i ∈ 1, . . . , l to a single cluster of Kk so that the vertices of V must arrange in an optimal
minimum multiway cut on the rest of the |S| clusters of Kk , and the result follow.
(b) |S| = 2, S = {s, t}. We use the same construction as in [6] in a small modification that we enumer-
ate over all the cores S such that s ∈ S, and terminals T such that t ∈ t instead of enumerating all
the cores S and terminals T as done at [6]. The rest of the proof is exactly like in [6].
Lemma 1. Assume that vertex 1 is a nested neighbor of vertex 2 in the cluster graph Gc . In any feasible
Gc -cut (V1 , . . . , Vk ) of I = (G, w), one can assume that |V2 | = 1.
Proof. Let (V1 , . . . , Vk ) be a Gc -cut (V1 , . . . , Vk ) of I. Assume that |V2 | > 1 and let x ∈ V2 . Consider the
Gc -cut (V1′ , . . . , Vk′ ) where Vi′ = Vi if i 6= 1, 2, V1′ = V1 ∪ (V2 \ {x}), V2′ = {x}. The value of (V1′ , . . . , Vk′ )
is not larger than the value of (V1 , . . . , Vk ) because w is non-negative, (1, 2) ∈ / Ec and NGc (1) ⊆ NGc (2).
Using Lemma 1, we deduce the following result for the leaves:
Corollary 1. Assume that vertex 1 is a leaf of Gc where |V (Gc )| = k. In any feasible Gc -cut (V1 , . . . , Vk )
2
of I = (G, w), one can assume that |Vi | = 1 for all i ∈ NG c
(1) \ {1}.
2
Proof. If 1 is a leaf of Gc , then for every i ∈ NG c
(1) \ {1}, vertex 1 is a nested neighbor of vertex i in Gc .

3 Complexity results of the minimum Gc-cut problem

In this section we show that the complexity of Gc -cut problem depends on the structure of the cluster graph
Gc . We will use several reductions from the Biclique Vertex-Partition problem.
Definition 4. B ICLIQUE V ERTEX -PARTITION :
Instance: A graph G and positive integer k.
Question: Does G have a biclique vertex partition of size at most k consisting of mutually vertex-disjoint
bicliques? (where the bicliques are (not necessarily vertex-induced) subgraphs of G).
For every fixed k ≥ 3, Biclique vertex-partition is NP-complete, and remains NP-complete for bipartite
graphs, see [5]. The case k = 2 has been open since a long time, but very recently, Biclique vertex-partition
with k = 2 has been proved NP-complete, [17]. Because the case k = 1 is polynomial, the case k = 2 is
equivalent to Biclique vertex-partition of size exactly 2.
The K2 - CUT PROBLEM is polynomial because it is exactly the minimum cut problem. Surprisingly, by
replacing K2 by 2K2 (two disjoint edges), the problem becomes much harder.
Theorem 2. The 2K2 - CUT PROBLEM is NP-hard.
Proof. We propose a polynomial reduction from biclique vertex-partition. Let G = (V, E) with |V | = n and
k = 2 be an instance of biclique vertex-partition. Consider the complete graph (G, w) defined as follows:
w(e) = 0 if e ∈ E and w(e) = 1 otherwise.
We claim that there exists a 2K2 -cut of G with value 0 iff G admits a biclique vertex-partition of size
exactly 2. Let Gi = (Ai , Bi ; Ei ) with i = 1, 2 be a biclique vertex-partition of G. Clearly, V2i−1 = Ai ,
V2i = Bi for i = 1, 2 is a Gc -cut of G with value 0. Conversely, let (Vi )i≤4 be a a 2K2 -cut of G with
value 0. Thus, for every i ≤ 2, Gi = (V2i−1 , V2i ; Ei ) is a biclique of G and then, (G1 , G2 ) is a biclique
vertex-partition of G of size 2.
 The minimum Gc cut problem 5

Corollary 2. The 2K2 - CUT PROBLEM is not approximable.

Proof. In proof of Theorem 2, we have shown that for the 2K2 - CUT PROBLEM, it is NP-complete to distin-
guish between opt ≤ 0 and opt > 0, where opt is the value of an optimal Gc -cut. So, the result follows.

Now, we propose a way to extend the 2K2 case to larger cluster graphs and thus, preserving the hard
cases via the notion of H-extension:

Definition 5. H - EXTENSION :
Let H and G be two graphs and T ⊆ V (H). G′ = G + H is an H-extension of G with terminal T if (i) G′
is connected (all edges between G and H) are incident in H to some vertices of V (H)\ T ) and (ii) for every
induced subgraph G0 of G′ isomorphic to H (given by the bijection f ) such that degG0 (f (v)) = degH (v)
for v ∈ T , we get G ⊆ G′ − G0 .

Roughly speaking, an H-extension G′ of G with terminal T is such that degH (v) = degG′ (v) for any
v ∈ T and for any induced subgraph G0 isomorphic to H (given by f ) with the same restriction (i.e.„
degG0 (v) = degG′ (v) for any v ∈ f (T )), G is a subgraph of G′ − G0
For instance, Figure 1 gives an P3 -extension of 2K2 with P3 = (u1 , u2 , u3 ) and terminal T = {u2 , u3 }.
Actually, the only induced subgraphs of G′ isomorphic to P3 satisfying the condition of 5 are G1 =
(v1 , v2 , u1 ), G2 = (v3 , v4 , u1 ), and G2 = (u1 , u2 , u3 ). Finally, for every i = 1, 2, 3, we have: 2K2 =
G′ − Gi . The tree G′ will be called the 3-star of length 2 and denoted by S32 (more generally, the p-star of
length 2 is given by Sp2 = {(r, v1i ), (v1i , v2i ) : i = 1, . . . , p}).

v2
v1 v2 v1

u1 u2 u3
v3 v4 v3
v4

Fig. 1. Example of P3 -extension where G = 2K2 , H = P3 = (u1 , u2 , u3 ), G′ = S32 and T = {u2 , u3 }.

Figures 2 and 3 give another P4 -extension of 2K2 or 3K2 with P4 = (u1 , u2 , u3 , u4 ) and terminal
T = {u2 , u3 }.
In Figure 3, for the Ψ -graph, the only induced P4 satisfying the condition of 5 are G0 = (u1 , u2 , u3 , u4 )
and G1 = (u1 , v1 , v2 , u4 ) and we get Ψ -graph−Gi = 3K2 for i = 0, 1 while for the κ-graph, the only
induced P4 satisfying the hypothesis are G0 = (u1 , u2 , u3 , u4 ), G1 = (u1 , v1 , v2 , u4 ), G2 = (v2 , v1 , u1 , u2 )
and G3 = (u3 , u2 , u1 , v1 ). Moreover, we have κ-graph−Gi = 3K2 for i = 0, 1 and 3K2 ⊂ κ-graph−Gi
for i = 2, 3.
Now, we present some polynomial reductions preserving approximation from the Gc - CUT PROBLEM to
itself depending on the structure of cluster graph Gc .

Theorem 3. There exists a polynomial reduction preserving approximation from the Gc - CUT PROBLEM to
the G′c - CUT PROBLEM in the following cases:
6 Itamar Elem, Refael Hassin, Jérôme Monnot

v2
v1 v2 v1 u4 u3

v3 v4 v3
v4 u1 u2

Fig. 2. Example of P4 -extension where G = 2K2 , H = P4 = (u1 , u2 , u3 , u4 ) and T = {u2 , u3 }.

v5 v6 v3 v4 v3 v4
v1 v2 v1 v2

u1 u4 u1 u4

u2 u3 u2 u3
v5 v6

v3 v4

u4

u3
v5 v6

Fig. 3. Another example of P4 -extension where G = 3K2 , H = P4 = (u1 , u2 , u3 , u4 ) and T = {u2 , u3 }. On the top,
the Ψ -graph (left and top) and the κ-graph (right and top). On the bottom, the κ-graph minus G2 = (v2 , v1 , u1 , u2 ). We
get 3K2 ⊂ κ-graph−G2 .
 The minimum Gc cut problem 7

(i) Assume that the smallest connected component of the cluster graph Gc has s ≥ 2 vertices. G′c = Gc +H
where H is a connected graph of at least 2 vertices and at most s vertices, disconnected from Gc and if
|V (H)| = s, then H is contained in every connected component of Gc with exactly s vertices.
(ii) G′c = Gc + P 0 is an Pi -extension of Gc with i ≥ 3, Pi = (k + 1, . . . , k + i) and terminal T =
{k + 1, . . . , k + i}.
(iii) G′c = Gc + P 0 is an Pi -extension of Gc with i ≥ 4, minimum degree 2, Pi = (k + 1, . . . , k + i) and
terminal T = {k + 2, . . . , k + i − 1}.

Proof. For (i). Let Gc and H be two graphs satisfying the condition at 5 and consider the cluster graph
G′c = Gc + H where V (H) = {k + 1, . . . , k + p}, 2 ≤ p ≤ s. Let (Kn , w) be an instance of the Gc -cut
problem and consider the instance (Kn+p , w′ ), V (Kn+p ) \ V (Kn ) = {u1 , . . . , up } of the G′c -cut problem
defined as follows: if u, v ∈ V (Kn ), then w′ (u, v) = w(u, v). If u ∈ V (Kn ) and v ∈ / V (Kn ), w′ (u, v) = ∞
2 ′ ′
Finally, w (ui , uj ) = 0 if (i, j) ∈ E(H) and w (ui , uj ) = ∞ otherwise.
Clearly, any Gc -cut of (Kn , w) can be converted into a G′c -cut of (Kn+p , w′ ) with same value by setting
Vk+i = {ui }. Conversely, consider any G′c -cut (V1 , . . . , Vk+p ) of (Kn+p , w′ ). From the previous part, we
can assume that this G′c -cut has a finite value. Assume u1 ∈ Vi1 . We get Vi1 ∩V (Kn ) = ∅ because each con-
nected component of G′c has a size at least two and Vi2 ⊆ {u1 , . . . , up } for every (i1 , i2 ) ∈ E(G′c ). Hence,
6 ∅. Now, we must get Vij = {uj } for j = 1, . . . , p
we deduce Vj ⊆ {u1 , . . . , up } if Vj ∩ {u1 , . . . , up } =
because each connected component G′c has a size at least 2 and at most p. Hence, the subgraph G induced
by {i1 , . . . , ip } is a connected component of G′c . If p < s or G is isomorphic to H, then clearly, we must get
G = H and the restriction of this G′c -cut to (Kn , w′ ) is a Gc -cut of (Kn , w) with same value. Now, assume
p = s and G 6= H. Since, by assumption E(H) ⊆ E(Kn ), we get E(Kn ) \ E(H) 6= ∅ and then the value
of the G′c -cut restricted to H has an infinite value, leading to contradiction. Hence, G = H and the result
follows.

For (ii). We first prove the case i = 3. Let (Kn , w) be an instance of the Gc -cut problem where Gc =
(Vc , Ec ) is a graph with |Vc | = k ≥ 1 vertices, and let P 0 = (k + 1, k + 2, k + 3). Now, let G′c = (Vc′ , Ec′ ) =
Gc + P 0 be any P3 -extension of Gc with terminal T = {k + 2, k + 3} (which means that the edges between
the P 0 and Gc are only connected to endpoint k + 1). Consider the following instance (Kn+3 , w′ ) of the
G′c -cut problem: V (Kn+3 ) \ V (Kn ) = {u1 , u2 , u3 } and w′ (u, v) = w(u, v) for u, v ∈ V , w′ (u1 , v) = 0,
w′ (u2 , v) = w′ (u3 , v) = +∞ for v ∈ V , and w′ (u1 , u2 ) = w′ (u3 , u2 ) = 0, and w′ (u1 , u3 ) = +∞.
Any Gc -cut of (Kn , w) can be converted into a G′c -cut of (Kn+3 , w′ ) with same value by setting Vk+i =
{ui } for i = 1, 2, 3. Conversely, assume that (V1 , . . . , Vk+3 ) is a G′c -cut of (Kn+3 , w′ ) with finite value.
Assume that u2 ∈ Vi2 and (i3 , i2 ) ∈ Ec′ (because G′c is a connected graph with at least 4 vertices). We get
Vi3 ∩ V (Kn ) = ∅, Vi2 ∩ {u1 , u3 } = ∅ and Vi3 ⊆ {u1 , u3 } because by construction w′ (u2 , v) = w′ (u3 , v) =
+∞ for v ∈ V and w′ (u1 , u3 ) = +∞. Hence, we deduce Vi2 = {u2 } since Vi2 ∩ V (Kn ) = ∅.
If Vi3 = {u1 , u3 }, then vertex i1 must be a leaf of G′c and vertex i2 has a neighbor i1 6= i3 in G′c
(because G′c is connected with at least 4 vertices). But Vi1 ⊆ V (Kn ) and w′ (u3 , v) = +∞ for v ∈ V (Kn ),
contradiction. Now, since w′ (u3 , v) = w′ (u3 , u1 ) = +∞ for v ∈ V (Kn ) and G′c is connected with at least
4 vertices we get Vi3 = {u3 } and vertex i3 is a leaf of G′c . Because i3 is a leaf of G′c , then vertex i2 must
get exactly one neighbor i1 6= i3 and Vi1 = {u1 }. So, P = (i3 , i2 , i1 ) is an induced P3 of G′c with terminal
{i2 , i3 }. Since, G′c is an P3 -extension of Gc , then the value of the G′c -cut is minimum if Vk+ i = {ui } for
i = 1, 2, 3 (because G′c − P 0 = Gc . Actually, if we flip the sets corresponding to P by the sets correspond-
ing to P 0 , the value of the G′c -cut does not increase). Hence, the restriction of this G′c -cut to (Kn , w′ ) is a
2
In the rest of the paper, we set +∞ in order to simplify, but the sufficient value will be for instance (n + 1)wmax
where wmax = maxe∈E(G) w(e).
8 Itamar Elem, Refael Hassin, Jérôme Monnot

Gc -cut of (Kn , w) with same value.

For the general case, let P 0 = (k + 1, . . . , k + i) with i ≥ 3. We replace (Kn+3 , w′ ) by (Kn+i , w′ )

where:

– V (Kn+i ) \ V (Kn ) = {u1 , . . . , ui } and w′ (u, v) = w(u, v).

– For u, v ∈ V (Kn ), w′ (u1 , v) = 0, w′ (uj , v) = +∞ for v ∈ V and j = 2, . . . , i.
– Finally, w′ (uj , uj+1 ) = 0, for j = 1, . . . , i − 1 and w′ (uj , uj ′ ) = +∞ otherwise.

The rest of the proof is completely similar to the previous one.

For (iii). We first prove the case i = 4. Let (Kn , w) be an instance of the Gc -cut problem where the
cluster graph Gc = (Vc , Ec ) has k ≥ 1 vertices and let P 0 = (k + 1, . . . , k + 4). Now, let G′c = (Vc′ , Ec′ ) =
Gc + P 0 be any P4 -extension of Gc with terminal T = {k + 2, k + 3} such that G′c is without a leaf.
Consider the following instance (Kn+4 , w′ ) of the G′c -cut problem: V (Kn+4 ) \ V (Kn ) = {u1 , . . . , u4 },
and w′ (u, v) = w(u, v) for u, v ∈ V (Kn ). Moreover, w′ (uj , v) = 0 for j = 1, 4, and w′ (uj , v) = +∞ for
j = 2, 3. Finally, w′ (uj , uj+1 ) = 0, for j = 1, . . . , 3, and w′ (uj , uj ′ ) = +∞ otherwise.
Any Gc -cut of (Kn , w) can be converted into a G′c -cut of (Kn+4 , w′ ) with same value by setting
Vk+i = {ui } for i = 1, . . . , 4. Conversely, assume that (V1 , . . . , Vk+4 ) is a G′c -cut of (Kn+4 , w′ ) with
finite value. Assume that u3 ∈ Vi3 and (i3 , i4 ), (i3 , i2 ) ∈ Ec′ (because G′c has minimum degree 2). By con-
struction, we get Vi3 ∩ V = ∅ because otherwise Vij ∩ V = ∅ for j = 1, 3 and Vij ∩ {u4 , u2 } = 6 ∅ for
every j = 2, 4 (thus, this G′c -cut will get an infinite value because either u1 ∈ Vij or u2 ∈ Vij for some
j = 2, 4). Hence, we deduce Vij ⊆ {u4 , u2 } for j = 2, 4 and then we can assume Vij = {uj } for j = 2, 4.
Moreover, i3 must have a degree 2 in G′c and (i2 , i4 ) ∈ / E(G′c ). Now, because i2 has a degree has at least
′ ′
2 in Gc , there is an edge (i1 , i2 ) ∈ E(Gc ) with i1 ∈ / {i3 , i4 }. Thus, Vi1 = {u1 }, and on the one hand i2
must have a degree 2 in G′c , and on the other hand (i1 , i4 ) ∈ / E(G′c ). Hence P = (i1 , . . . , i4 ) is an induced
′ ′
P4 of Gc with terminal {i2 , i3 }. Finally, since Gc is a P4 -extension of Gc with terminal {k + 2, k + 3}, we
can assume that Vk+i = {ui } for i = 1, . . . , 4. In conclusion, the restriction of this G′c -cut to (Kn , w′ ) is a
Gc -cut of (Kn , w) with same value.

For the general case, let P 0 = (k + 1, . . . , k + i) with i ≥ 4. We replace the instance (Kn+4 , w′ ) by
(Kn+i , w′ ) where:

– V (Kn+i ) \ V (Kn ) = {u1 , . . . , ui }.

– w′ (u, v) = w(u, v) for u, v ∈ V (Kn ).
– w′ (uj , v) = 0 for j = 1, i.
– w′ (uj , v) = +∞ for v ∈ V (Kn ) and j = 2, . . . , i − 1.
– Finally, w′ (uj , uj+1 ) = 0, for j = 1, . . . , i − 1 and w′ (uj , uj ′ ) = +∞ otherwise.

The rest of the proof is completely similar to the previous one.

We saw at all the above constructions that the new i added vertices placed at the new i added clusters in
an optimal solution and the original vertices must placed in an optimal way at the original clusters. Since the
construction can perform in polynomial time the result are follow.

Corollary 3. The Gc - CUT PROBLEM is NP-hard and not approximable in the following cases:
 The minimum Gc cut problem 9

(i) Gc = pK2 with p ≥ 2.

(ii) Gc = Sp2 with p ≥ 3.
(iii) Gc = Ψ -graph or Gc = κ-graph.
Proof. For (i). By applying part (i) of Theorem 3 with Gc = 2K2 and H = K2 , we deduce from Theorem
2 that the 3K2 -cut problem is NP-hard and not approximable. By induction on p ≥ 2, with Gc = pK2 and
H = K2 we deduce the claimed result.

2
For (ii). The (p + 1)-star of length 2 Sp+1 (recall that Sp2 is defined by {(r, v1i ), (v1i , v2i ) : i = 1, . . . , p})
0
is a P3 -extension of pK2 and P = (2p + 1, 2p + 2, 2p + 3) with terminal T = {2p + 2, 2p + 3}. Hence,
2
using part (ii) of Theorem 3 and part (i) of Corollary 3, we get that the Sp+1 -cut problem is NP-hard and
not approximable for any p ≥ 2.

For (iii). The Ψ -graph and the κ-graph are P4 -extensions of 3K2 and P 0 = (7, 8, 9, 10) with terminal
T = {8, 9} and are without leaf. Hence, using part (iii) of Theorem 3 and Theorem 2, the result follows.
In part (i) of Theorem3, we have proved that the complexity of the Gc - CUT PROBLEM does not depend
on the connectivity of the cluster graph Gc as long as, the size of each connected component is a at least 2.
In Section 4, we will see that the Gc - CUT PROBLEM is polynomial time solvable if the cluster graph Gc has
a fixed number of vertices and at least one isolated vertex. So now, we will assume that Gc is connected.
In Corollary 3, all of the different connected graphs Gc such that the Gc - CUT PROBLEM is NP-hard have a
maximum degree at least 3. Here, we prove the prove that this result remains true for the MULTIWAY Gc - CUT
PROBLEM on a connected graphs Gc of maximum degree 2.

Theorem 4. The MULTIWAY Pk - CUT PROBLEM is NP-hard and not approximable in the following cases:
(i) k = 5 or k ≥ 8, even when only one vertex is specified (i.e., |S| = 1).
(ii) k = 6, even when only two vertices are specified (i.e., |S| = 2).
Proof. We give a reduction preserving approximation from the 2K2 - CUT PROBLEM proved NP-hard and
not approximable in Theorem 2 and Corollary 2. Let I = (Kn , w) be an instance of the 2K2 -cut problem.

For (i) and k = 5, consider the instance I ′ = (Kn+1 , w′ ) where V (Kn+1 ) \ V (Kn ) = {x}, w′ (u, v) =
w(u, v) if u, v 6= x, and w′ (u, x) = 0 for u ∈ V (Kn ). Let S = {3} with x ∈ V3 . Assume that Gc = P5 =
(1, 2, 3, 4, 5).
Let (V1 , V2 , V3 , V4 ) be any 2K2 -cut of I. (V1′ , V2′ , V3′ , V4′ , V5′ ) with V1′ = V1 , V2′ = V2 , V4′ = V3 ,
V5′ = V4 and V3′ = {x} is a P5 -cut of I ′ with same value. Conversely, let (V1′ , V2′ , V3′ , V4′ , V5′ ) be any P5 -cut
of I ′ such that x ∈ V3 . Using Corollary 1 with leaf 1 and NP25 (1) \ {1} = {3}, we know that we can assume
that V3′ = {x}. Hence, (V1 , V2 , V3 , V4 ) where V1 = V1′ , V2 = V2′ , V3 = V4′ , V4 = V4′ is a 2K2 -cut of I with
the same value.

For k ≥ 8, using the Pi -extension of P5 for i ≥ 3 given in part 2 of Theorem 3 and the result given
above for the MULTIWAY P5 - CUT PROBLEM, the result follows.

For (ii) and k = 6, consider the instance I ′ = (Kn+2 , w′ ) where V (Kn+2 ) \ V (Kn ) = {x, y},
w (u, v) = w(u, v) if u, v 6= x, u, v 6= y and w′ (u, x) = w′ (u, y) = 0 for u ∈ V , Let S = {3, 4} with
′

x ∈ V3 and y ∈ V4 . Assume that Gc = P6 = (1, 2, 3, 4, 5, 6). Since, vertices 1 and 6 are leaves of P6 and
NP26 ({1, 6}) \ {1, 6} = {3, 4}, the same proof as previously gives the expected result.
10 Itamar Elem, Refael Hassin, Jérôme Monnot

In Section 4, we will see that the Pk - CUT PROBLEM is polynomial if k ≤ 4 (note that these results also
holds for the MULTIWAY Pk - CUT PROBLEM).
In conclusion of this section, we have obtained many cases where the Ck - CUT PROBLEM that the problem
is NP-hard. In particular, when Gc is a tree that is quite surprising. In future research, we leave some open
problems: what is the complexity of the Ck - CUT PROBLEM or the MULTIWAY Ck - CUT PROBLEM where
k ≥ 5? Nevertheless, these restrictions are NP-hard when the number of vertices is unbounded because the
Cn - CUT PROBLEM on (Kn , w) (resp., Pn -cut) is clearly equivalent to solve the traveling salesman problem
on (Kn , w), (resp., Hamiltonian path problem). Same question for the the Pk - CUT PROBLEM with k ≥ 5
since as we will see in Section 4, the Ck - CUT PROBLEM for k ≤ 4 and the Pk - CUT PROBLEM for k ≤ 4 are
polynomial time solvable.

4 Polynomially solvable cases

In this section, we will see some cluster graphs where the Gc - CUT PROBLEM is polynomial. It is the cases
when the cluster graph Gc contains twins (stable set with same neighborhood), two nested neighbors (a
stable set of two vertices with included neighborhood), leaves or isolated vertices (see Section 2 for formal
definitions).

4.1 Complete r-partite graphs

Here, we mainly Pshow that if the cluster graph Gc is a complete r-partite graph Kd1 ,...,dr (see Definition
r
2) where k = i=1 di is fixed, then the Gc - CUT PROBLEM can be solved in polynomial time, using an
extension of the algorithm of [6]. Some simple complete r-partite graphs are the following: the stable graph
K¯n (ie., E = ∅) is complete 1-partite, and the complete graph is complete n-partite. We also look at the case
where Gc is a restricted split graphs.
Let us begin by some properties of complete r-partite. As we will see, these graphs are recognizable
within polynomial-time. The graph H3 = K2 + K1 is the graph G = (V, E) with |V | = 3 and |E| = 1
depicted in Figure 4.1.

1 2

Fig. 4. An H3 = K2 + K1 graph

Lemma 2. G = (V, E) is complete r-partite if and only if G is H3 -free.

Proof. Suppose that G is complete r-partite. It is clear from the definition that ∀u, v, w ∈ V we have three
cases, none of which defines an H3 graph:
1. u, v, w reside at different color classes, so the graph induced by them is a 3-clique.
 The minimum Gc cut problem 11

2. u, v reside at the same color class, and w belongs to a different color class, so the graph induced by them
contains the edges (u, w), (v, w).
3. u, v, w reside at same color class so the graph induced by them contains no edge.

The opposite direction is done by induction on n = |V (G)|. Assume that any graph G with less than
n vertices which does not contain H3 as an induced subgraph is complete r-partite for some r > 0, and
consider a graph G = (V, E) with n vertices which does not contain H3 as an induced subgraph. Let v ∈ V .
G′ = G − v is also H3 -free, and then by inductive hypothesis is a complete r-partite graph. We study two
cases.

1. degG (v) = n − 1. We add v in a new color class Lr+1 . Obviously, G is complete (r + 1)-partite.
2. degG (v) < n − 1. So, there is u ∈ Li such that (u, v) ∈/ E. We add v in the color class Li . Let us prove
that G is complete r-partite. First, Li ∪ {v} is a stable set because Li is a stable set and G is H3 -free.
Second, ∀j 6= i, ∀u ∈ Lj , (u, v) ∈ E. Otherwise, ∃u ∈ Lj with (u, v) ∈ / E. Let w ∈ Li . The graph
induced by {u, v, w} is isomorphic to H3 , a contradiction.

Using Lemma 2, it is clear that we can check in O(|V (G)|3 ) whether a graph is complete r-partite.
Actually, a careful analysis of Lemma 2 gives a O(|E(G)|) time algorithm to recognizable such graphs.

Theorem 5. The Kd1 ,...,dr - CUT PROBLEM can be solved in polynomial time if k = ri=1 di is fixed and is
P
NP-hard, if there exists di and dj unbounded.

Proof. Assume k = ri=1 di fixed and Gc = Kd1 ,...,dr . Since Gc is a complete r-partite graph, any two
P
vertices u, v ∈ Li of the same layer are twins where we recall that a twin is a stable set of two vertices
with same neighborhood. Hence, the Kd1 ,...,dr -cut problem is equivalent to solve the d′ -size restricted Kr -
cut problem on I = (G, w) where d′i = di , for i = 1, . . . , r which is itself equivalent to computing a
minimum r-cut (V1 , . . . , Vr ) of G with the constrains |Vi | ≥ di . Finally, this later problem can be computed
in polynomial time using the same lines of the proof that those given in [6].
Now, we first prove that the case of complete bipartite graph is NP-complete if k = d1 +d2 is unbounded.
The bisection graph problem consists of finding a cut of minimum size of a graph such that the two cut sets
have the same size. Assume n even and consider d1 = d2 = n/2. The Kd1 ,d2 -cut problem on (G, w) is
equivalent to solve the bisection graph problem on G = (V, E) (by setting w(e) = 1 if e ∈ E and w(e) = 0
if e ∈
/ E) which is known to be NP-hard [7]. Now, we reduce the Kd1 ,d2 case to the Kd1 ,d2 ,d3 case. An
inductive proof on r allows us to conclude the proof.
Given an instance I = (Kn , w) of the Kd1 ,d2 -cut problem, consider the following instance I ′ =
(Kn+d3 , w′ ) of the Kd1 ,d2 ,d3 -cut problem: V (Kn+d3 ) \ V (Kn ) = {u1 , . . . , ud3 } and if u, v ∈ V (Kn ),
w′ (u, v) = w(u, v). If u ∈ V (Kn ) and v ∈ / V (Kn ), w′ (u, v) = 0. Finally, w′ (ui , uj ) = ∞.
Consider a solution of the Kd1 ,d2 ,d3 -cut problem with color classes L1 , L2 , L3 . By construction, {u1 , . . . , ud3 }
belongs to the same color class, say Li because Gc is complete 3-partite and w′ (ui , uj ) = ∞. We study two
cases:

• |Li | =
6 d3 . Wlog., we can assume that d3 sets of Li are such that Vi = {ui } with i = 1, . . . , d3 because
Gc is 3-partite. Let |Lj | = d3 . We flip the sets of Li different to Vi in Lj (as new sets). We obtain a new
solution of the Kd1 ,d2 ,d3 -cut problem.
• |Li | = d3 . Wlog., we can assume that {ui } ⊆ Vi for i = 1, . . . , d3 , because Gc is 3-partite. We move
the vertices of Li \ {u1 , . . . , ud3 } to the color class Lj with j 6= i. Again, we obtain a new solution of
the Kd1 ,d2 ,d3 -cut problem with ≤ value.
12 Itamar Elem, Refael Hassin, Jérôme Monnot

Now, let S be the vertices which have been flipped. For each of the two cases, the new solution loses
w(S, Cj ) and wins w(S, {u1 , . . . , ud3 }) = 0. Hence, the new solution has a better cost and then we can
assume the restriction of Kn is a Kd1 ,d2 -cut with same value.
For instance, K4 −K2 the graph depicted in Figure 5 is a complete 3-partite K2,1,1 and then, the K4 −K2 -cut
problem is solvable in polynomial time.

L1 L2

v1 v3

v2 v4

L3

Fig. 5. A K4 − K2 .

If only d1 depends on the instance and r is fixed, then the complexity of the Kd1 ,...,dr -cut problem is an
open problem.

4.2 Restricted split graphs

Recall that a restricted split graph is a split graph where the degree of each vertex of the clique is at most
n − 2 (see Definition 2).
Theorem 6. If Gc = (Sc , Kc ; Ec ) is restricted split graph where |Kc | is upper bounded by a constant, then
the Gc - CUT PROBLEM can be solved in polynomial time.
Proof. Let Gc = (Vc , Ec ) be a restricted split graph on k ≥ 3 vertices and let OP T = (V1∗ , . . . , Vk∗ ) be an
optimal Gc -cut of I = (G, w). Then, for every i ∈ K, there exists i′ ∈ S such that i′ is nested neighbor
of vertex i in Gc because Gc is a restricted split graph. Using Lemma 1, we know that |Vi∗ | = 1 for all
i ∈ Kc . Hence, we can guess the |Kc | vertices of Vi∗ = {vi∗ } for i ∈ Kc . After, consider the following
complete bipartite graph BP = (Sc , V \ {vi∗ : i ∈ Kc }; E(BP )), edge weighted by d where d(i, v) =
∗
P
j∈NGc (i) w(v, vj )), and find a b-matching M saturating Sc of minimum weight d (the algorithm is the
same as finding a b-matching of maximum weight d′ where d′ (e) = dmax −d(e), dmax = maxe∈E(BP ) d(e))
with b− (i) = 1 and b+ (i) = |V | for i ∈ Sc and b− (v) = b+ (v) = 1 for v ∈ V \ {vi∗ : i ∈ Kc }. Recall
that a b-matching of a graph G = (V, E) is a subset M such that if G′ = (V, M ), then ∀v ∈ V , b− (v) ≤
degG′ (v) ≤ b+ (v). A b-matching of maximum weight can be done in polynomial-time O(|V (G)|3 ), see [21]
section 21 page 337. Since any Gc -cut corresponds to a b-matching M saturating Sc with value d(M ) (when
vi∗ for i ∈ Kc have been guessed), the previous algorithm finds an optimal solution in time O(n|Kc |+3 ).
In particular, the P4 -cut problem on (G, w) can be solved in O(n5 ) time. However, for the P4 -cut prob-
lem on (G, w), we can improve the complexity to O(n3 ). Instead of applying a b-matching algorithm, we
 The minimum Gc cut problem 13

apply the following greedy algorithm: each vertex v of V \ {v2∗ , v3∗ } (here Kc = {2,P 3} and Sc = {1, 4})
is assigned to the Vi∗ with i = 1, 4 minimizing its contribution (i.e., i = arg mins∈Sc j∈NGc (s) w(v, vj∗ )).
Careful attention must be taken to avoid to get V1∗ = ∅ or V4∗ = ∅. For instance, if V1∗ = ∅, then we
find v ∗ = arg min{d(1, v) − d(4, v) : v ∈ V \ {v2∗ , v3∗ }} and we add v ∗ to V1∗ . The time complexity
of this algorithm is O(n3 ). Also note that in the same spirit of the proof of Theorem 6 the result holds if
2
S ∪ NG c
(S) = V (Gc ) where S is the leaves of Gc .
2
Lemma 3. If S ∪ NG c
(S) = V (Gc ), where S is leaves of Gc , then the Gc - CUT PROBLEM can be solved in
polynomial time.

4.3 When Gc contains isolated vertices

Definition 6. G is an H0 graph if it contains at least one isolated vertex v, i.e., degG (v) = 0. Let S(G) =
{v ∈ V : degG (v) = 0}.

Lemma 4. Let Gc be an H0 graph. The Gc - CUT PROBLEM can be solved in polynomial time iff |V (Gc ) \
S(Gc )| is fixed.

Proof. Consider the unbounded case of |V (Gc ) \ S(Gc )|. Gc = Cn + K1 is an H0 graph and the Gc -cut
problem is clearly equivalent to solve the minimum traveling salesman problem. Now, let Gc be an H0 graph
such that |V (Gc ) \ S(Gc )| = k − 1 is fixed and consider an instance I = (G, w) of the Gc -cut problem.
Denote the clusters corresponding to vertices of S(Gc ) as Vk , . . . , Vp and the k−1 clusters corresponding
to V (Gc ) \ S(Gc ) by V1 , . . . , Vk−1 . Enumerate the ordered subsets H ⊂ V , |H| = k − 1. Insert the vertices
from H into the clusters V1 , . . . , Vk−1 so that each cluster contains exactly one vertex according to the order,
and insert arbitrarily the vertices of V \H into the remaining clusters  Vk , .
. . , Vp . Let SH be this
 solution and
n 2
S be the minimum one. Since k − 1 is fixed the complexity is O k−1 · (k − 1)!(k − 1) = O(nk−1 ).
The obtained solution is optimal since any assignment of the vertices of V into the clusters V (Gc ) \ S(Gc )
which results with one of these clusters having more than one vertex, can be improved by moving all these
vertices except one from this cluster into any one cluster among Vk , . . . , Vp . This new solution is an improved
solution to the original, since the subset of edges in the new solution is strictly contained in the original
solution.

Definition 7. A complete r − H0 graph is a graph G = (V, E) where V (G) = ∪ri=1 Li such that (i) for
every i ∈ {1, . . . , r} the graph induced by Li is an H0 graph, and (ii) for every i, j ∈ {1, . . . , r} with i 6= j,
(u, v) ∈ E for every u ∈ Li , v ∈ Lj t.

In particular a complete 1 − H0 graph is a H0 graph and K3 ± K2 3 (see Figure 6) is a complete 2 − H0

graph (where L1 = {1} and L2 = {2, 3, 4}).
The following result extends Lemma 4 to complete 2 − H0 graphs.

Theorem 7. Suppose that Gc is a complete 2−H0 cluster graph and |Vc | = k is constant. Then the Gc - CUT
PROBLEM can be solved in polynomial time.

Proof. Denote Vc = Vc1 ∪Vc2 such that the two induced graphs Gc (Vc1 ), Gc (Vc2 ) are H0 -graphs, |Vc1 | = k1 ,
and |Vc2 | = k2 , where k1 + k2 = k. Let I = (G, w) be an instance and assume that optimal solution assigns
the vertices V1∗ ⊂ V to the clusters of Gc (Vc1 ) and V2∗ ⊂ V (with V1∗ ∪ V2∗ = V ) to the clusters of Gc (Vc2 ).
3
± means that K3 and K2 share a common vertex.
14 Itamar Elem, Refael Hassin, Jérôme Monnot

2 3

Fig. 6. A K3 +K2 .

The optimal solution on V1∗ must assign k1 − 1 vertices to k1 − 1 clusters and the rest of its vertices to the
cluster represented by the isolated vertices. Similarly with V2∗ . So again we iterate over all ordered subsets
K1 , K2 ⊂ V such that |K1 | = k1 , |K2 | = k2 , and compute a min-cut on G which separates K1 from K2 .
Denote the cost of the assignment of K1 vertices to the clusters Vc1 according to the order as W1 . Denote
the cost of the assignment of K2 vertices to the clusters Vc2 according to the order as W2 . Denote the cost
of min-cut on G which separates K1 from K2 as W3 , and let W = W1 + W2 + W3 . Compute K1 , K2
minimizing W . The clustering derived from them is the optimal solution and has a polynomial runtime
complexity in |V |.
We now list several types of the cluster graph Gc for which the previous Theorems imply a polynomial
algorithm.
(1.) If Gc has at most four vertices, then the Gc - CUT PROBLEM is polynomial iff Gc 6= 2K2 .
(2.) Vc = {0, , . . . , k}, Ec = {(0, 1), . . . , (0, k)} ∪ {(1, 2), . . . , (k − 2, k − 1)}. Gc is a complete 2 − H0
graph where L1 = {0}, L2 = {1, . . . , k} depicted in Figure 7 .
For (1.), the only cases to study are the graphs which contain a P4 as multiway subgraph, because the
remaining cases are the H0 -graphs, 2K2 , or the connected graphs on at most 3 vertices (and then isomorphic
to K1 , K2 , K3 or P3 = K1,2 ). Thus, the graphs which contain a P4 are K4 , C4 = K2,2 , K3 ± K2 (see
Figure 6), K4 − K2 = K2,1,1 (see Figure 5), but all are polynomial as proved previously.
It is easy to see that complete r-partite graphs generalize the k-cut problem, because Gc is a k-clique and
we can look at each vertex as a different color class. It is also clear that complete r − H0 graphs generalize
complete r-partite graphs, because each color class is an H0 -graph. We are still left with the open problem
whether when Gc is a complete r − H0 graph, the problem is polynomial or NP-hard for r > 2.

5 Approximation results
In this section, we give some approximation results for the Gc - CUT PROBLEM when the weights satisfy the
triangle inequality or are positive.

The version of the k-cut problem on (Kn , w) with the additional requirement that cluster Vi must have a
Pk
size of di ∈ N, where i=1 di = n, is studied in [18], and it is shown there that under the triangle inequality
 The minimum Gc cut problem 15

2 3

0
k−1

Fig. 7. A complete 2 H0 Example.

and fixed k it possible to obtain an approximation of at most three times the optimal value. We extend this
result to the cluster graphs in two steps: first, we demonstrate the idea assuming that Gc is a ring (ie., an
induced cycle Ck on k vertices). Second, we apply the same arguments to any cluster graph on k vertices.
We use an auxiliary problem, the MIN - ADJACENT- STAR PROBLEM, as explained in the next lines. For a
given Gc = (Vc , Ec ) and a given set of centers C = {c1 , . . . , ck } ⊆ V with ci ∈ Vi , we wish to arrange
the vertices of V \ C into |Vc | = k clusters. After the arrangement we will get |Vi | = di and we want
Pk P P
to minimize i=1 ( {j|(i,j)∈Ec } v∈Vj \{cj } w(ci , v)). Thus, we want to arrange the clusters so that the
arrangement yields the minimum sum of distances from the rest of the vertices to the given centers of the k
stars according to the neighborhood relations between the stars.

5.1 The metric restricted cyclic k-cut problem

Let Kn = (V, E) be a complete undirected graph with |V | = n. The edges e ∈ E have nonnegative weights
w(e) ≥ 0 that satisfy the triangle inequality (i.e., ∀x, y, z ∈ V , w(x, y) ≤ w(x, y) + w(y, z)). Given is also
Pk
a set of integers K = {di }ki=1 such that i=1 di = n.

Definition 8. For any k ≥ 3, the METRIC RESTRICTED CYCLIC k- CUT PROBLEM computes, given an
Pk
instance I = (G, w) satisfying the triangle inequality and k integers di with i=1 di = n, k disjoint subsets
of vertices Vi ⊆ V with size |Vi | = di for i ≤ k, minimizing the total weight of edges whose two ends are
in the i and i + 1 sets for i = 1, . . . , k, where k + 1 ≡ 1.

Actually, the METRIC RESTRICTED CYCLIC k- CUT PROBLEM is the METRIC RESTRICTED Ck - CUT
PROBLEM as indicated in Definition 3. The METRIC RESTRICTED CYCLIC 3- CUT PROBLEM is NP-hard
because it is the 3-cut problem with the additional requirement, proved NP-hard in [18]. Here, we strengthen
this result by proving that it is the case even if the weights are either one or two.
16 Itamar Elem, Refael Hassin, Jérôme Monnot

Theorem 8. For any k ≥ 3, the METRIC RESTRICTED CYCLIC k- CUT PROBLEM is NP-hard, even if w(e) ∈
{1, 2}.

Proof. Let k ≥ 3. We propose several polynomial reductions depending on the parameter k. These reduc-
tions are quite similar and are done from the bisection graph problem in complete graphs K2n with weights
in {1, 2} which is know to be NP-hard. Recall that the bisection graph problem consists of finding a mini-
mum cut of an unweighted graph such that the two cut sets have the same size. The bisection graph problem
is NP-hard [7] and it is easy to see that the metric bisection graph problem on complete graphs restricted
to weights 1 and 2 remains NP-hard. Let I = (K2n = (V, E), w) be a complete graph on 2n vertices and
edges weighted by w(e) ∈ {1, 2}, instance of the metric bisection graph problem.

For k = 3. Consider the instance I ′ = K2n+1 , w′ ) with d1 = d2 = n and d3 = 1 of the METRIC

METRIC RESTRICTED CYCLIC 3- CUT PROBLEM described as follows: V (K2n+1 ) = V ∪ {x1 } and for any
u, v ∈ V w′ (u, v) = w(u, v), w′ (x1 , v) = 1 for every v ∈ V .
We claim that there is a bisection of K2n of value w(V1 , V2 ) at most B iff there is a cyclic 3-cut (with
d1 = d2 = n and d3 = 1) of value at most B + 2n.

Clearly, if (V1 , V2 ) is a bisection of K2n of value at most w(V1 , V2 ) ≤ B, then (V1 , V2 , V3 = {x1 })
is a cyclic 3-cut with value w′ (V1 , V2 , V3 ) ≤ B + 2n. Conversely, let (V1 , V2 , V3 ) be a cyclic 3-cut with
value at most w′ (V1 , V2 , V3 ) ≤ B + 2n and such that |V1 | = |V2 | = n and |Vi | = 3. Let us prove that
we can polynomially transform it into a cyclic 3-cut (V1′ , V2′ , V3′ ) with w′ (V1 , V2 , V3 ) ≤ w′ (V1′ , V2′ , V3′ )
and such that V3′ = {x1 }. So, assume that V3′ = {v} with v ∈ V and x1 ∈ V1 . By setting (V1′ =
V1 \ {x1 } ∪ {v}, V2′ = V2 , V3′ = {x1 }), we get: w′ (V1′ , V2′ , V3′ ) − w′ (V1 , V2 , V3 ) = 2n + w(v, V2 ) −
(n + 1 + w(v, V \ {v})) = n − 1 − w(v, V1 \ {v}) ≤ 0. Hence, (V ′ 1, V2′ ) is a bisection of K2n of value
w(V ′ 1, V2′ ) = w′ (V1′ , V2′ , V3′ ) − 2n ≤ −w′ (V1 , V2 , V3 ) − 2n ≤ B.

For k = 4. We assume that n is even; actually, it is easy to see that the bisection graph problem in com-
plete graphs K4n with weights in {1, 2} remains NP-hard. Let I = (K4n = (V, E), w) be a complete graph
on 4n vertices and edges weighted by w(e) ∈ {1, 2}, instance of this restriction. By setting I ′ = (K4n , w)
and di = n for every i = 1, . . . , 4, we can easily prove that (V1′ , . . . , V4′ ) is a restricted cyclic 4-cut of value
w(V1′ , . . . , V4′ ) ≤ B iff (V1 = V1′ ∪ V3′ , V2 = V2′ ∪ V4′ ) is a bisection of value w(V1 , V2 ) ≤ B.

For k ≥ 5. Consider the instance I ′ = K32n+(k−5)18n , w′ ) with d1 = d2 = n, d3 = dk = 6n and

d4 = · · · = dk−1 = 18n of the METRIC RESTRICTED CYCLIC k- CUT PROBLEM described as follows:
V (K32n+(k−5)18n ) = V ∪ {x1 , . . . , x30n+(k−5)18n } and for any u, v ∈ V w′ (u, v) = w(u, v), w′ (xi , v) =
2 for every i = 1, . . . , 30n + (k − 5)18n and v ∈ V , and finally, w′ (xi , xj ) = 1 for 1 ≤ i < j ≤
30n + (k − 5)18n.
We claim that there is a bisection of K2n of value w(V1 , V2 ) at most B iff there is a cyclic k-cut (with
d1 = d2 = n, d3 = dk = 6n and d4 = · · · = dk−1 = 18n) of value at most B + 132n2 + (k − 5)(18n)2 .

Clearly, if (V1 , V2 ) is a bisection of K2n of value at most w(V1 , V2 ) ≤ B, then (V1 , . . . , Vk ) where
V3 ∪ · · · ∪ V5 = {x1 , . . . , x30n+(k−5)18n } is a cyclic k-cut with value w′ (V1 , . . . , Vk ) ≤ B + 132n2 +
(k − 5)(18n)2 . Conversely, let (V1 , . . . , Vk ) be a cyclic k-cut with value at most w′ (V1 , . . . , Vk ) ≤ B +
132n2 + (k − 5)(18n)2 and such that |V1 | = |V2 | = n, |V3 | = |Vk | = 6n and |V4 | = · · · = |Vk−1 | = 18n.
Let us prove that we can polynomially transform it into a cyclic k-cut (V1′ , . . . , Vk′ ) with w′ (V1′ , . . . , Vk′ ) ≤
w′ (V1 , . . . , Vk ) and such that ∪ki=3 Vi′ = {x1 , . . . , x30n+(k−5)18n }.
 The minimum Gc cut problem 17

We prove this claim in two steps using a 2-exchange procedure. First, we demonstrate that the result
holds for V4 ∪ · · · ∪ Vk−1 and then we prove it for V3 ∪ Vk . Concerning the first step, we distinguish two
cases: k = 5 and k ≥ 6.
k = 5. So, assume that v ∈ V4 ∩ V . Then, there exists xi ∈ Vj with j ∈ {1, 2}. Consider the cyclic 5-cut
(V1′ , . . . , V5′ ) where from (V1 , . . . , V5 ), we make a 2-exchange between v and xi ; so, Vj′ = (Vj \{xi })∪{v},
V4′ = (V4 \ {v}) ∪ {xi } and Vp′ = Vp for p 6= j, 4. Assume that w is the neighbor (distinct of 3 − j) of
j in Gc (so, w = 5 if j = 1 and w = 3 if j = 2). The contribution of v and xi in the cyclic 5-cut
(V1 , . . . , V5 ) at least w′ (v, V3 ∪ V5 ) + w′ (xi , V3−j ∪ Vw ) ≥ (2 × 10n + 2n) + 7n = 29n (because on
the one hand v is linked to at least 10n vertices of {x1 , . . . , x30n } and at most 2n vertices of V and on
the other hand, v is linked to 7n = |V3−j ∪ Vw | vertices) while the contribution of v and xi in the cyclic
5-cut (V1′ , . . . , V5′ ) is at most w′ (xi , V3 ∪ V5 ) + w′ (v, V3−j ∪ Vw ) ≤ 10n + 4n + 2 × 7n = 28n. Hence,
w′ (V1′ , . . . , V5′ ) − w′ (V1 , . . . , V5 ) ≤ 28n − 29n ≤ 0.

k ≥ 6. First, assume that v ∈ (V4 ∪ Vk−1 ∩ V . By symmetry, suppose that v ∈ V4 . Then, there ex-
ists xi ∈ Vj with j ∈ {1, 2}. Consider the cyclic k-cut (V1′ , . . . , Vk′ ) where from (V1 , . . . , Vk ), we make
a 2-exchange between v and xi . The contribution of v and xi in the cyclic k-cut (V1 , . . . , Vk ) is at least
w′ (v, V5 ∪ V3 ) ≥ 2 × 22n + 2n = 46n (because |V5 ∪ V3 | = 24n and |V | = 2n; hence, v is linked
to at least 22n vertices of {x1 , . . . , x30n+(k−5)18n } and at most 2n vertices of V ). On the other hand the
contribution of v and xi in the cyclic k-cut (V1′ , . . . , Vk′ ) is at most w′ (xi , V3 ∪ V5 ) + 2(|V2j−1 | + |Vw |) ≤
22n + 2 × 2n + 2(n + 6n) = 40n where w ∈ {3, k} is the neighbor of j different of 3 − j in Gc . In
conclusion, w′ (V1′ , . . . , Vk′ ) − w′ (V1 , . . . , Vk ) ≤ 40n − 46n ≤ 0.

Now assume v ∈ Vp with 5 ≤ p ≤ k − 2 (in this case, note that k ≥ 7). The contribution of v and xi
in the cyclic k-cut (V1 , . . . , Vk ) is at least w′ (v, Vp−1 ∪ Vp+1 ) ≥ 2 × 34n + 2n (because |Vp−1 ∪ Vp+1 | =
36n and |V | = 2n). On the other hand the contribution of v and xi in the cyclic k-cut (V1′ , . . . , Vk′ ) is
at most w′ (xi , Vp−1 ∪ Vp+1 ) + 2(|Vj | + |Vw |) ≤ 34n + 2 × 2n + 2(n + 6n) = 52n (because xi is
linked to at least 34n vertices of {x1 , . . . , x30n+(k−5)18n } and at most 2n vertices of V ). In conclusion,
w′ (V1′ , . . . , Vk′ ) − w′ (V1 , . . . , Vk ) ≤ 34n − 52n ≤ 0.

In any cases (k = 5 or k ≥ 6), by repeating this process, we get a cyclic k-cut (V1′ , . . . , Vk′ ) satisfying
V4 ∪ · · · ∪ Vk−1 ⊂ {x1 , . . . , x30n+(k−5)18n } and w′ (V1′ , . . . , Vk′ ) ≤ w′ (V1 , . . . , Vk ).

Now, assume that v ∈ (V3 ∪ Vk ) ∩ V (by symmetry, suppose v ∈ V3 ). Then, there exists xi ∈ Vj
with j ∈ {1, 2}. As previously, consider the cyclic k-cut (V1′ , . . . , Vk′ ) resulting of a 2-exchange between
v and xi and let w be the neighbor different of 3 − j of j in Gc . The contribution of v and xi in the
cyclic k-cut (V1 , . . . , Vk ) at least w′ (v, V4 ) ≥ 2 × 18n = 36n (because from the previous case we know
V4 ⊆ {x1 , . . . , x30n+(k−5)18n } while the contribution of v and xi in the cyclic k-cut (V1′ , . . . , Vk′ ) is at most
w′ (xi , V2 ∪ V4 ) + w′ (v, V3−j ∪ Vw ) ≤ |V4 | + 2|V2 | + 2(|V3−j | + |Vw |) = 18n + 2n + 2(n + 6n) = 34n.
Thus, w′ (V1′ , . . . , Vk′ ) − w′ (V1 , . . . , Vk ) ≤ 34n − 36n ≤ 0.

In conclusion, from (V1 , . . . , Vk ) we polynomially obtain a cyclic k-cut (V1′ , . . . , Vk′ ) such that ∪ki=3 Vi′ =
{x1 , . . . , x30n+(k−5)18n } and such that w′ (V1′ , . . . , Vk′ ) ≤ w′ (V1 , . . . , Vk ). Hence, (V1′ , V2′ ) is a bisection of
K2n with value w(V1′ , V2′ ) = w′ (V1′ , . . . , Vk′ ) − 132n2 − (k − 5)(18n)2 ≤ w′ (V1 , . . . , Vk ) − 132n2 − (k −
5)(18n)2 ≤ B.
Note that if k is unbounded, then the METRIC RESTRICTED CYCLIC k- CUT PROBLEM is APX-hard
because this problem contains the METRIC TSP PROBLEM.
18 Itamar Elem, Refael Hassin, Jérôme Monnot

We demonstrate that for any fixed k it is possible to obtain in polynomial time an approximation of at
most three times the optimal value. We start by defining a new problem which we solve optimally for a
constant k, and then use its solution to approximate the METRIC RESTRICTED CYCLIC k- CUT PROBLEM.

Definition 9. The MIN - ADJACENT- STAR PROBLEM finds vertices v1 , . . . , vk and a k-cut, such that vi ∈ Vi ,
|Vi | = di , i = 1, . . . , k, and
p 
X 
di w(vi , Vi+1 ) + di+1 w(vi+1 , Vi ) + di di+1 w(vi , vi+1 )
i=1

is minimized, where indices are (mod k).

Theorem 9. Algorithm FindCyclicPartition (see Algorithm 1) solves the MIN - ADJACENT- STAR PROBLEM.
It can be executed in time O(nk+1 ).

input :
1. A complete graph Kn = (V,P E), |V | = n, with weights w(e) ≥ 0, e ∈ E.
2. Integers d1 . . . , dk such that ki=1 di = n.
output:
1. v1 , . . . , vk ⊆ V .
2. A partition V1 , . . . , Vk of V such that vi ∈ Vi , |Vi | = di , i = 1, . . . , k.
foreach subset {v1 , . . . , vk } ⊆ V do
{a1 , . . . , an−k } := V \ {v1 , . . . , vk }.
Compute x̃, Pan optimal solution to the following transportation problem:
minimize ki=1 n−k
P P
j=1 l∈{−1,1} di w(vi , aj )xi+l,j
subject
Pk to:
xij = 1, j = 1, . . . , n − k,
Pi=1
n−k
i=1 xij = di − 1, i = 1, . . . , k,
xij ∈ {0, 1}, i = 1, . . . , k, j = 1, . . . , n − k.
{v ,...,vk } S
Vi 1 := {vi } {aj |1 ≤ j ≤ n − k, x̃ij = 1}, i = 1, . . . , k.
{v ,...,vk } {v ,...,vk }
d{v1 ,...,vk } := pi=1 di w(vi , Vi+11
P
) + ki+1 w(vi+1 , Vi 1 ) + di di+1 w(vi , vi+1 )
end
∗ ∗
Find {v1∗ , . . . , vk∗ } ⊆ V for which d{v1 ,...,vk } is minimal, denote it by S ∗ .
∗ ∗ ∗ ∗
{v1 ,...,vk } {v1 ,...,vk }
return (v1∗ , . . . , vk∗ , V1 , . . . , Vk ).
Algorithm 1: FindCyclicPartition

Proof. Let ṽ1 , . . . , ṽk , Ṽ1 , . . . , Ṽk be an optimal solution to the min-adjacent-star problem. Since the algo-
rithm checks all the subsets of V of size k it also checks the subset {ṽ1 , . . . , ṽk }. For this subset the sum
Pp Pk
1 di di+1 w(ṽi , ṽi+1 ) is constant, so we need to find a partition (V1 , . . . , Vk ) which minimizes 1 [di w(v˜i , Vi+1 )+
di+1 w(vi+1˜ , Vi )]. This is achieved by finding an optimal solution to a transportation problem (where xij = 1
if vertex aj is assigned to the subset Vi ). For a fixed value of k we can solve the transportation problem in
time O(n), using the algorithms of [27]. There are O(nk ) subsets {v1 , . . . , vk } ⊆ V , so altogether the time
complexity is O(nk+1 ).
 The minimum Gc cut problem 19

We now show that the weight of the partition found as an optimal solution for the MIN - ADJACENT- STAR
PROBLEM is no more than 3opt, where opt is the value of the optimal solution of the METRIC CYCLIC
k- CUT PROBLEM. Denote by apx the value of the partition constructed by Algorithm 1.
Theorem 10. Algorithm FindCyclicPartition is a 3-approximation for the METRIC RESTRICTED CYCLIC
k- CUT PROBLEM when k is constant.
Proof. Let (v1 , . . . , vk , V1 , . . . , Vk ) be the output of Algorithm FindCyclicPartition and let O1 , . . . , Ok be
an optimal solution of the METRIC RESTRICTED CYCLIC k- CUT PROBLEM; obviously, ∀i ≤ k, |Oi | = di
by hypothesis. We will prove that
k
X k
X
apx = w(Vi , Vi+1 ) ≤ 3 w(Oi , Oi+1 ) = 3opt.
i=1 i=1

By construction, we have:

k
X
apx = w(Vi , Vi+1 )
i=1
k
X X
= w(ui , uj )
i=1 ui ∈Vi
uj ∈Vi+1

k
X X  
≤ w(vi , vi+1 ) + w(ui , vi+1 ) + w(vi , ui+1 )
i=1 ui ∈Vi
uj ∈Vi+1

k 
X 
= di w(vi , Vi+1 ) + di+1 w(vi+1 , Vi ) + di di+1 w(vi , vi+1 )
i=1
∗
≡S .

On the other hand, according to Theorem 9, FindCyclicPartition solves the MIN - ADJACENT- STAR PROB -
LEM, so that for every (u1 , . . . , uk ) such that u1 ∈ O1 , . . . , uk ∈ Ok ,
k 
X 
∗
S = di w(vi , Vi+1 ) + di+1 w(vi+1 , Vi ) + di di+1 w(vi , vi+1 )
i=1
k 
X 
≤ di w(ui , Oi+1 ) + di+1 w(ui+1 , Vi ) + di di+1 w(ui , ui+1 ) .
i=1

Qk
Summing over all (u1 , . . . , uk ) such that u1 ∈ O1 , . . . , uk ∈ Ok , since we have j=1 dj equalities as
above leaving the left side of each inequality as is meaning S ∗ we have that:

k
Y k  Y
X k k
Y k
Y 
S∗ dj ≤ ( di )w(Oi , Oi+1 ) + ( di )w(Oi+1 , Oi ) + ( di )w(Oi , Oi+1 )
j=1 i=1 j=1 j=1 j=1
20 Itamar Elem, Refael Hassin, Jérôme Monnot

k
Y k 
X 
=( di ) w(Oi , Oi+1 ) + w(Oi+1 , Oi ) + w(Oi , Oi+1 )
j=1 i=1
k
Y k
X
=( di )3 w(Oi , Oi+1 )
j=1 i=1
k
Y
= 3( di )opt
i=1

Hence S ∗ ≤ 3opt, giving apx ≤ S ∗ ≤ 3opt.

5.2 Approximation algorithms for the METRIC RESTRICTED Gc - CUT PROBLEM when k is constant
At subsection 5.1, we have proposed an approximation algorithm for the METRIC RESTRICTED CYCLIC k-
CUT PROBLEM. Now, we will solve the general case of the METRIC RESTRICTED Gc - CUT PROBLEM when
Gc is an arbitrary cluster graph with a constant number of vertices.
Definition 10. The MIN - ADJACENT-Gc PROBLEM finds vertices v1 , . . . , vk and a Gc -cut, such that vi ∈ Vi ,
|Vi | = di , i = 1, . . . , k, and
X  
di w(vi , Vj ) + dj w(vj , Vi ) + di dj w(vi , vj )
(i,j)∈Ec

is minimized.
The idea of the algorithm is similar to the previous one and is described below.
Theorem 11. Algorithm FindGcPartition (see Algorithm 2) solves the MIN - ADJACENT-Gc PROBLEM in
time O(nk+1 ).

Proof. Let ṽ1 , . . . , ṽk , Ṽ1 , . . . , Ṽk be an optimal solution to the MIN - ADJACENT-Gc PROBLEM. Since the
algorithm
P checks all the subsets of V of size k, it also checks the subset {ṽ1 , . . . , ṽk }. For thisPsubset the
(i,j)∈Ec di dj w(ṽi , ṽj ) is constant, so we need to find a partition (V1 , . . . , Vk ) which minimizes (i,j)∈Ec di w(ṽi , Vj ).
This is achieved by solving the transportation problem (where xij = 1 if and only if aj assigned to the subset
Vi ).
For a fixed value of k we can solve the transportation problem in linear time in n, using the algorithms
in [27]. There are O(nk ) subsets (v1 , . . . , vk ), so altogether the time complexity is O(nk+1 ).
Theorem 12. Algorithm FindCyclicPartition is a 3-approximation for the METRIC RESTRICTED Gc - CUT
PROBLEM when k is constant.

Proof. Let (v1 , . . . , vk , V1 , . . . , Vk ) be the output of Algorithm FindCyclicPartition and let O1 , . . . , Ok be

an optimal solution of the METRIC RESTRICTED Gc - CUT PROBLEM; obviously, ∀i ≤ k, |Oi | = di by
hypothesis. Let (v1 , . . . , vk , V1 , . . . , Vk ) be the outputted solution and let O1 , . . . , Ok be an optimal solution
of the METRIC RESTRICTED Gc - CUT PROBLEM. Assume that ∀i ≤ k, |Oi | = d∗i and consider the step of
Algorithm 2 where (d∗1 , . . . , d∗k ) is given in input. We have: Let (v1 , . . . , vk , V1 , . . . , Vk ) be the outputted
solution and let O1 , . . . , Ok be an optimal solution of the METRIC Gc - CUT PROBLEM. Assume that ∀i ≤ k,
|Oi | = d∗i and consider the step of Algorithm 2 where (d∗1 , . . . , d∗k ) is given in input. We have:
 The minimum Gc cut problem 21

input :
1. A complete graph Kn = (V, E), |V | = n, with weights w(e) e ∈ E.
2. A cluster graph Gc (Vc , Ec ), |V Pc | = k.
3. Integers d1 , . . . , dk such that ki=1 di = n.
output:
1. v1 , . . . , vk ⊆ V .
2. A Gc -cut V1 , . . . , Vk such that vi ∈ Vi , i = 1, . . . , k.
1 (i, j) ∈ Ec
For i, j ∈ Vc let αij =
0 otherwise
foreach {v1 , . . . , vk } ⊂ V do
{a1 , . . . , an−k } := V \ {v1 , . . . , vk }.
Compute x̃, Pan optimal solution to the following transportation problem:
minimize ki=1 kj=1 n−k
P P
l=1 αij di w(vi , al )xlj
subject
Pk to:
Pn−ki=1 xij = 1, j = 1, . . . , n − k,

i=1 xij = ki − 1, i = 1, . . . , k,
xij ∈ {0, 1}, i = 1, . . . , k, j = 1, . . . , n − k.
end
{v ,...,vk }
Let Vi 1 := {vi } ∪h{aj |1 ≤ j ≤ n − k, x̃ij = 1}, i = 1,i. . . , k.
{v ,...,vk }
d{v1 ,...,vk } := (i,j)∈Ec di w(vi , Vj 1
P
) + di dj w(vi , vj ) .
{v1∗ , . . . , vk∗ } := arg min{d{v1 ,...,vk } |{v1∗ , . . . , vk∗ } ∈ V .
{v ∗ ,...,vk
∗
} {v ∗ ,...,vk
∗
}
return (v1∗ , . . . , vk∗ , V1 1 , . . . , Vk 1 ).

Algorithm 2: FindGcPartition
22 Itamar Elem, Refael Hassin, Jérôme Monnot

X
apx ≤ w(Vi , Vj )
(i,j)∈Ec
X X
= w(ui , uj )
(i,j)∈Ec ui ∈Vi
uj ∈Vj
X X  
≤ w(vi , vj ) + w(ui , vj ) + w(vi , uj )
(i,j)∈Ec ui ∈Vi
uj ∈Vj
X  
= d∗i w(vi , Vj ) + d∗j w(vj , Vi ) + d∗i d∗j w(vi , vj ) = S ∗ .
(i,j)∈Ec

On the other hand, according to Theorem 11, FindGcPartition solves the MIN - ADJACENT-Gc PROBLEM so
that for every (u1 , . . . , uk ) such that u1 ∈ O1 , . . . , uk ∈ Ok ,
X  
S∗ = d∗i w(vi , Vj ) + d∗j w(vj , Vi ) + d∗i d∗j w(vi , vj )
(i,j)∈Ec
X  
≤ d∗i w(ui , Oj ) + d∗j w(uj , Oi ) + d∗i d∗j w(ui , uj ) .
(i,j)∈Ec

Summing over all (u1 , . . . , uk ) such that u1 ∈ O1 , . . . , uk ∈ Ok :

k
" k k k
#
Y X Y Y Y
∗ ∗ ∗ ∗ ∗
S di ≤ ( di )w(Oi , Oj ) + ( di )w(Oj , Oi ) + ( di )w(Oi , Oj )
i=1 (i,j)∈Ec i=1 i=1 i=1
k
Y X
= d∗i [w(Oi , Oj ) + w(Oj , Oi ) + w(Oi , Oj )]
i=1 (i,j)∈Ec
k
Y X
=3 d∗i w(Oi , Oj )
i=1 (i,j)∈Ec
k
Y
= 3( d∗i )opt
i=1

Hence, S ≤ 3opt, leading to the conclusion that apx ≤ S ∗ ≤ 3opt.

∗

5.3 Approximation algorithms for the metric Gc -cut problem

Here, we will solve the case where w is metric, Gc = (Vc , Ec ) is a general graph but |Vc | is constant and
without constraint on cluster sizes. Let G = (V, E) be a complete undirected graph, with V = {v1 . . . vn },
and edge weights w(vi , vj ) ≥ 0 that satisfy the triangle inequality.
Theorem 13. There is a 3-approximation for the METRIC Gc - CUT PROBLEM when k is constant.
Pk k
Proof. Let |V | = n, |Vc | = k. Enumerate all D = (d1 , . . . , dk ), i=1 di = n we have an O(n ) such
ordered sets. For each such ordered set solve the METRIC RESTRICTED Gc - CUT PROBLEM by using the
algorithm from 5.2 algorithm 2, and get a 3 approximation as in 5.2. Choose the smallest Gc -cut among all
the Gc -cuts. Since the optimal solution yields a specific D, the result follows.
 The minimum Gc cut problem 23

5.4 Approximation of the Gc -cut problem with positive weights

In Section 3, we saw that the Gc - CUT PROBLEM is not approximable at all in general graphs (see for instance
Corollaries 2 or 3) due to the weight 0 for some edges. Here, we propose an approximation ratio for the Gc -
CUT PROBLEM when w(e) > 0 for every e ∈ E which works even when the number k of the vertices of Gc
depends on the instance (we only assume k ≤ n). Let wmin = mine∈E w(e), wmax = maxe∈E w(e), and
α= w wmin .
max

Theorem 14. The Gc - CUT PROBLEM with positive weights is α-approximable in linear time, where α =
wmax
wmin , even if |Vc | is not fixed.

Proof. Let I = (Kn , w) with w(e) > 0 for every e ∈ E be an instance of the Gc -cut problem. Let
m′i0 = n − k + 1 where i0 = arg mini∈Vc degGc (i), and m′j = 1 for j ∈ {1, . . . , k}, j 6= i0 . Arbitrarily
assign m′i vertices of Kn to Vi for i = 1, . . . , k and let (V1 , . . . , Vk ) be the resulting Gc -cut with value apx.
Let opt be the value of an optimal solution (V1∗ , . . . , Vk∗ ) of the Gc - CUT PROBLEM on (Kn , w). We will
prove that apx ≤ α · opt. Let optu = (i,j)∈Ec m′i m′j .
P

By construction, since w(e) ≤ wmax we get:

apx ≤ wmax · optu (1)

Let mi = |Vi∗ | for i = 1, . . . , k. We mainly prove that:
X
optu ≤ mi mj (2)
(i,j)∈Ec

′
Pthat optu is the value of an optimal Gc -cut on (Kn , w ) where
To see this, we will show w′ (e) = 1 for
′
every e ∈ E. Hence, since (i,j)∈Ec mi mj is the value of a particular Gc -cut on (Kn , w ), inequality (2)
will follows.

Property 1. Let (V1∗ , . . . , Vk∗ ) be an optimal Gc -cut on (Kn , w′ ) where m∗i = |Vi∗ | for i = 1, . . . , k. The
following properties hold:

(i) If e = (i, j) ∈ Ec , then min(m∗i , m∗j ) = 1.

/ Ec , then one can assume that min(m∗i , m∗j ) = 1.
(ii) If e = (i, j) ∈

Proof. For (i). Let e = (i, j) ∈ Ec and m = m∗i + m∗j ; denote Di = ∗

P
r∈NGc (i)\{j} mr and Dj =
∗
P
r∈NGc (j)\{i} mr . Assume Di ≥ Dj . Then, the contribution of the portion of the optimal solution where
one cluster is either Vi∗ or Vj∗ can be written as Di · m∗i + m∗j · Dj + m∗i · m∗j (because ∀e ∈ E, w′ (e) = 1),
or equivalently (using m∗j = m − m∗i ), f (mi ) = −(m∗i )2 + m∗i · (m + Di − Dj ) + m · Dj . This expression
is a decreasing parabola and it reaches its minimum value for m∗i = 1 or m∗i = m − 1 because Di , Dj and
m are constant (actually, when m∗i decreases by one unit, m∗j increases by one unit).

/ Ec and m = m∗i + m∗j and suppose m∗i > 1, m∗j > 1. Assume degGc (i) ≤
For (ii). Let (i, j) ∈
degGc (j) where we recall that degGc (i) is the degree of vertex i in Gc . The contribution of clusters Vi∗ , Vj∗ in
the optimal solution is degGc (i)·m∗i +degGc (j)·m∗j because by (i) we know that m∗w = 1 for w ∈ NGc (i)∪
NGc (j). Substituting m∗j = m−m∗i and rearranging the above expression we obtain (degGc (i)−degGc (j))·
m∗i + degGc (j) · m. This expression is strictly decreasing with m∗i as its argument when degGc (i) <
degGc (j), and constant when degGc (i) = degGc (j). In conclusion, we can always assume that m∗j = 1.
24 Itamar Elem, Refael Hassin, Jérôme Monnot

Using Property 1, we deduce that m∗i0 = n − k + 1 and m∗j = 1 for j ∈ {1, . . . , k}, j 6= i0 , that is
exactly m′i = m∗i for i ∈ {1, . . . , k}. Now, combining inequalities (1) and (2), we obtain:
X
apx ≤ wmax · mi mj . (3)
(i,j)∈Ec

On the other hand, by construction we have:

X
opt ≥ wmin · mi mj . (4)
(i,j)∈Ec

Using inequalities (3) and (4), the result follows.

6 Conclusion

In this paper, we have studied the complexity and the approximation of the Gc CUT PROBLEM. Some results
are given, but many open problems exist. What is the exact complexity of the Gc CUT PROBLEM on lines or
rings (ie., induced paths or cycles)? Is the METRIC Gc- CUT PROBLEM admit a PTAS or is APX-complete?
Another interesting direction for further research is to study the maximum Gc cut problem.

References
1. C. F. Ball, P.V. Kraus, and D. A. Mlynski, “Fuzzy partitioning applied to VLSI-partitioning and placement,”
IEEE International Symposium on Circuits and Systems, ISCAS’94 1 (1994) 177-180.
2. D. Bein, W. Bein, Z. Meng, L. Morales, C.O. Shields, Jr., and I.H. Sudborough, “Clustering and the biclique par-
tition problem,” Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS
2008) (2008).
3. M. Burlet, and O. Goldschmidt, “A new and improved algorithm for the 3-cut problem,” Operations Res. Lett.
21 (1997) 225-227.
4. E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, “The Complexity of
Multiterminal Cuts,” SIAM J. Comput. 23 (1994) 864-894.
5. H. Fleischner, E. Mujuni, D. Paulusma and S. Szeider, “Covering graphs with few complete bipartite sub-
graphs,” Theoretical Computer Science 410 (2009) 2045-2053.
6. O. Goldschmidt and D. S. Hochbaum, “A polynomial algorithm for the k-cut problem for fixed k,” Mathematics
of Operations Research 19 (1994) 24-37.
7. M. R. Garey and D. S. Johnson “Computers and Intractability: A Guide to the Theory of NP-Completeness
Freeman, San Francisco (1979).
8. A.V. Goldberg, and R.E. Tarjan, “A new approach to the maximum-flow problem,” J. ACM 35 (1988) 921-940.
9. H. Saran and V.V. Vazirani, “Finding k-cuts within twice the optimal,” SIAM J. Computing 24 (1995) 101-108.
10. S. Kapoor, “On minimum 3-cuts and approximating k-cuts using cut trees,” in: Proceedings of the 5th Interna-
tional IPCO Conference on Integer Programming and Combinatorial Optimization, Springer-Verlag, London,
UK, 1996 132-146.
11. G. Karypis, V. Kumar, “Multilevel k-way hypergraph partitioning,” VLSI Design 11 (2000) 285-300.
12. D.R. Karger, and C. Stein, “A new approach to the minimum cut problem,” J. ACM 43 (1996) 601-640.
13. R. Klimmek, and F. Wagner, “A simple hypergraph min cut algorithm.” Internal Report B 96-02 Bericht FU
Berlin, Fachbereich Mathematik und, Informatik, 1995.
14. Y. Kamidoi, S. Wakabayashi, and N. Yoshida, “A divide-and-conquer approach to the minimum k-way cut
problem,” Algorithmica 32 (2002) 262-276.
 The minimum Gc cut problem 25

15. Y. Kamidoi, N. Yoshida, and H. Nagamochi, “A deterministic algorithm for finding all minimum k-way cuts,”
SIAM J. Comput. 36 (2006) 1329-1341.
16. W.-K. Mak, and D.F. Wong, “A fast hypergraph min-cut algorithm for circuit partitioning,” Integration, VLSI
J. 30 (2000) 1-11.
17. B. Martin and D. Paulusma, “The computational complexity of disconnected cut and 2K2-partition,” Proceed-
ings of the 17th International Conference on Principles and Practice of Constraint Programming (CP 2011),
Perugia, Italy, September 12-16, 2011, LNCS 6876 (2011) 561-575.
18. N.Guttmann-Beck and R. Hassin, “Approximation algorithms for minimum K-Cut,” Algorithmica 21 (2000)
198-207.
19. H. Nagamochi, and T. Ibaraki, “Computing edge connectivity in multigraphs and capacitated graphs”, SIAM J.
Discrete Math. 5 (1992) 54-66.
20. H. Nagamochi, S. Katayama, and T. Ibaraki, “A faster algorithm for computing minimum 5-way and 6-way
cuts in graphs”, COCOON 99, LNCS, 1627 (1999) 164-173.
21. A. Schrijver,Combinatorial optimization, polyhedra and efficiency, Springer Volume A (2002).
22. J. Shi, and J. Malik, “Normalized cuts and image processing,” IEEE Transactions on Pattern Analysis and
Machine Intelligence 22(8) (2000) 888-905.
23. D. B. Shmoys. "[Approximation algorithms for] Cut problems and their application to divide-and-conquer".
In: Approximation Algorithms for NP-hard Problems, (D.S. Hochbaum, ed.) PWS, 1997, 192-235., J. ACM 44
(1997) 585-591.
24. M. Stoer, and F. Wagner, A simple min-cut algorithm, J. ACM 44 (1997) 585-591.
25. T. Ito, M. Kaminski, D. Paulusma and D. M. Thilikos, “Parameterizing cut sets in a graph by the number of
their components” Lecture Notes in Computer Science 5878 (2009) 605-615.
26. M. Thorup, "Minimum k-way cuts via deterministic greedy tree packing", in: Proceedings of the 40th Annual
ACM Symposium on Theory of Computing (STOC 2008), 2008, 159-166.
27. T.Tokuyama and J. Nakano “Geometric algorithms for the minimum cost assignment problem,” Random Struc-
tures & Algorithms 6 (1995) 393-406.
28. M. Xiao, “Finding minimum 3-way cuts in hypergraphs,” Information Processing Letters 110 (2010) 554-558.