The Complexity of Maximum k-Order Bounded Component
Set Problem
Sounaka Mishra1
Department of Mathematics, Indian Institute of Technology Madras, Chennai 600 036, India

Shijin Rajakrishnan

arXiv:1712.02870v3 [cs.DS] 28 Mar 2018

Department of Computer Science, Cornell University, New York, USA

Abstract
Given a graph G = (V, E) and a positive integer k, in M AXIMUM k-O RDER B OUNDED
C OMPONENT S ET (M AX -k-OBCS), it is required to find a vertex set S ⊆ V of maximum
size such that each component in the induced graph G [S] has at most k vertices. We
prove that for constant k, M AX -k-OBCS is hard to approximate within a factor of n1−e ,
for√any e > 0, unless P = NP. This is an improvement on the previous lower bound
of n for M AX -2-OBCS due to Orlovich et. el. [1]. We provide lower bounds on the
approximability when k is not a constant as well. M AX -k-OBCS can be seen as a generalization of M AXIMUM I NDEPENDENT S ET (M AX -IS). We generalize Turán’s greedy
algorithm for M AX -IS and prove that it approximates M AX -k-OBCS within a factor of
(2k − 1)d + k, where d is the average degree of the input graph G. This approximation
factor is a generalization of Turán’s approximation factor for M AX -IS.
Keywords: Approximation algorithms, Graph algorithm, Dissociation set, k-order
bounded component

1. Introduction
In this paper, we consider the computational complexity of an optimization problem
called the M AXIMUM k-O RDER B OUNDED C OMPONENT S ET problem (M AX -k-OBCS).
In M AX -k-OBCS, given a graph G = (V, E) and a positive integer k, it is required to
find a vertex set S ⊆ V of maximum size such that order of each component in G [S] is
at most k.
This is a generalization of several important problems in combinatorics. For k =
1, this problem is the same as the M AXIMUM I NDEPENDENT S ET problem (M AX -IS),
where given a graph G = (V, E), the objective is to find a subset of vertices S ⊆ V of
maximum size such that there is no edge between any pair of vertices in G [S]. The case
Email addresses: sounak@iitm.ac.in (Sounaka Mishra ), sr986@cornell.edu (Shijin Rajakrishnan )
author

1 Corresponding

Preprint submitted to Elsevier

March 29, 2018

of k = 2 gives rise to the M AXIMUM D ISSOCIATION S ET problem (M AX -D ISSO -S ET),
where given a graph G, the objective is to find a vertex set S ⊆ V of maximum size such
that the degree of each vertex in G [S] is at most 1. Both these problems are NP-hard and
thus M AX -k-OBCS is NP-hard as well.
Finding a maximum sized independent set is one of the widely studied problems in
combinatorics and its hardness to compute has prompted several attempts at developing approximate solutions. Håstad [2] proved that , for any e > 0, M AX -IS cannot be
approximated within a factor of n1−e , unless NP = ZPP. Later, Zukerman [3] proved
that M AX -IS cannot be approximated within a factor of n1−e , unless P = NP, for any
e > 0. This lower bound result rules out the existence of a polynomial time efficient algorithm on general graphs. However, the situation is not quite as grim when restricted
to special graph classes. It is polynomial time solvable to find a maximum independent
set in claw-free graphs [4], P5 -free graphs [5], and perfect graphs [6]. For other classes,
although finding a polynomial time optimal solution might be out of the question unless P = NP, we can nevertheless provide good approximation algorithms. In planar
graphs, there exists a PTAS for M AX -IS [7] whereas for graphs with bounded degree, the
problem can be approximated within a constant factor [8]. One such algorithm greedily includes a vertex of minimum degree into the solution set, deletes that vertex along
with its neighbors from the graph and then repeats this selection process until there are
no more vertices to process. This simple greedy algorithm returns an independent set
which is within a factor of (d + 1) from the optimal solution (Turán’s Theorem) [9]. A
tighter analysis has improved the approximation factor to 15 (2d + 3) [10].
In [11], Yannakakis defined dissociation set and proved that it is NP-complete to
find a vertex set S of minimum size in a given bipartite graph G such that G [V \ S] has
maximum degree 1. From this result it follows that M AX -D ISSO -S ET is NP-complete
even when restricted to bipartite graphs. It is also known to be NP-complete for K1,4 -free
bipartite graphs, C4 -free bipartite graphs of maximum degree 3 [12], planar graphs with
maximum degree 4 [13] and planar line graphs of planar bipartite graphs [1]. However,
M AX -D ISSO -S ET is polynomial time solvable when the input graph is restricted to some
hereditary classes of graphs, such as {chair, bull }-free graphs, {chair, K3 }-free graphs,
{mK2 }-free graphs with m ≥ 2 [1].
Approximation algorithms for the complementary problem of M AX -k-OBCS have
been designed by various researchers. In this minimization problem, we are asked to
find a vertex set S of minimum size in a given graph G such that each component in
G [V \ S] has at most k vertices. When k = 1 and 2, these minimization problems are
known as M INIMUM V ERTEX C OVER and M INIMUM D ISSOCIATION S ET, respectively.
In M INIMUM D ISSOCIATION S ET it is required to find a vertex set S of minimum cardinality in a given graph G = (V, E) such that degree of each vertex in G [V \ S] is at
most 1. It is interesting to observe that M INIMUM D ISSOCIATION S ET is equivalent to
M INIMUM P3 V ERTEX C OVER in which it is required to find a vertex set S of minimum
size such that G [V \ S] does not have a P3 (path on 3 vertices) as a subgraph. Both M INI MUM V ERTEX C OVER and M INIMUM D ISSOCIATION S ET are known to be approximable
within a factor of 2 [14]. For larger values of k, the deletion problem is known to be approximable within a factor of k and approximable within a factor of (k − 1) when the
input graph has girth at least k [15]. However, to the best of our knowledge, there is no
known result about the approximability of M AX -k-OBCS for arbitrary graphs.
2

Our Contribution. In this paper, we explore the approximability and inapproximability of M AX -k-OBCS, for different integral values of k. In Section 3, we prove inapproximability results by establishing an approximation preserving reduction from
M AX -IS, which shows that for constant k, this problem has no efficient approximation
algorithms for general graphs. The reduction used can be composed to prove hardness
results even for non-constant k. In particular, we show that for k = O( logn n ), it is not
possible to develop an algorithm with a better approximation guarantee than O(log n),
unless P = NP. Having established the hardness of computing efficient solutions to this
problem, in the subsequent sections we concentrate on developing upper bounds. In
Section 4, we prove that M AX -W EIGHTED -k-OBCS can be approximated within a factor of ∆, where ∆ is the maximum degree of the input graph G. This also proves that the
problem can be approximated within a constant factor for degree bounded graphs. It is
important to note that this bound holds not just for the unweighted case but also for the
weighted version of the problem, where there is a weight function w : V → R+ as an
additional input and the objective is to find a vertex set S of maximum weight such that
G [S] has no component whose order exceeds k. The technique used in the algorithm
is the Local Ratio Method [16]. In Section 5, we build upon the algorithm for M AX -IS
to develop a greedy algorithm for M AX -D ISSO -S ET, with a performance guarantee of
(3d + 2), where d is the average degree of the graph. We then generalize the algorithm
and the analysis to the larger problem with arbitrary values of k and prove that the
extension of the algorithm yields a solution which is within a factor of (2k − 1)d + k
from the optimal solution. This can be observed as a generalization of Turán’s bound
mentioned earlier for M AX -IS. Finally, in Section 6, we establish a reduction to M AX IS and use existing upper bounds for M AX -IS [17] to prove that M AX -k-OBCS can be
k∆ log log ∆
approximated within a factor of O( log ∆ ), for sufficiently large values of ∆.
2. Notations
Throughout this paper, we assume that any graph G = (V, E) mentioned is simple
and undirected, with |V | = n vertices and | E| = m edges. Given a graph G = (V, E),
the open neighborhood NG (v) of a vertex v is the set of vertices those are adjacent to v
in G and the closed neighborhood NG [v] of v is defined as NG [v] = NG (v) ∪ {v}. For
a given set P ⊆ V, we define NP (v) = NG (v) ∩ P, for each v ∈ V. The degree of a
vertex v in the graph G is defined as dG (v) = | NG (v)|, the maximum degree of the
graph is ∆G = maxv∈V dG (v). When the underlying graph G is unambiguous, we drop
the subscript, for example we use just ∆ to denote the maximum degree in G instead
of ∆G . The average degree of the graph G is d = n1 ∑v∈V dG (v). There is an interesting
relationship between the average degree of a graph and the total number of edges in
the graph, which we use in this paper, viz. the sum of the degrees of all the vertices in a
graph is twice the number of edges. So ∑v∈V dG (v) = 2| E|, which gives us |V |d = 2| E|.
Given a subset of vertices, S ⊆ V, the graph induced on this set, G [S], is the subgraph
whose vertex set is S and the edge set is the subset of edges E such that both endpoints
are in S, i.e, G [S] = (V 0 , E0 ) where V 0 = S and E0 = {(u, v) ∈ E | u ∈ S and v ∈ S}.
A vertex set S ⊆ V is called an independent set if G [S] has no edges. We shall denote
α( G ) as the size of a maximum independent set in G. An independent set S is maximal
3

if it is not a proper subset of another independent set of G. A set of vertices S of G is
called a dissociation set if degree of each vertex in G [S] is at most 1 (equivalently, each
component in G [S] has at most two verices). In the maximum dissociation set problem
(M AX -D ISSO -S ET), the objective is to find a dissociation set of maximum size in a given
graph G. A set S ⊆ V is called a k-component set in G if each component in G [S] has
at most k vertices. We shall denote the size of a maximum k-component set in G by
compk ( G ).
3. Hardness of approximation
In this section, we shall prove inapproximability results for M AX -k-OBCS by establishing an AP-reduction [18] from M AX -IS. The following lower bound result for
M AX -IS makes this reduction useful.
Theorem 3.1. [3] Unless P = NP, for any e > 0, M AX -IS is not approximable within a factor
of n1−e .
The hardness result mentioned in Theorem 3.1 establishes the hardness of approximation for M AX -1-OBCS. Next, we establish the hardness of approximation for M AX k-OBCS for any constant positive integer k. We make use of the following reduction for
this purpose.
Lemma 3.2. For any k > 0, M AX -k-OBCS ≤AP M AX -2k-OBCS.

Proof. Given an instance G = (V, E) of M AX -k-OBCS, we construct an instance G 0 =
(V 0 , E0 ) of M AX -2k-OBCS as follows. First we make two copies G1 = (V1 , E1 ) and
G2 = (V2 , E2 ) of the graph G with V1 = {v1 | v ∈ V }, V2 = {v2 | v ∈ V } and E1 , E2
are defined accordingly. Then, for each edge (u, v) ∈ E, we add two edges (u1 , v2 )
and (u2 , v1 ). Finally, we introduce the edge (u1 , u2 ) for each u ∈ V. Thus we have
V 0 = V1 ∪ V2 and E0 = E1 ∪ E2 ∪ {(u1 , v2 ), (u2 , v1 ) | (u, v) ∈ E} ∪ {(u1 , u2 ) | u ∈ V }. It
is easy to observe that |V 0 | = 2|V |. For an illustration we refer to Figure 1.

u

V

x

G

V1

u2

v1

v

y

u1

V2

v2
x2

x1
y1

y2
G0

Figure 1: Sketch of the construction of G 0 from G

Let S∗ be a maximum k-component set in G and S0∗ be a maximum 2k-component
set in G 0 . From the construction of G 0 from G, it follows that the set S0 = {v1 , v2 | v ∈ S}
is a 2k-component set in G 0 , for every k-component set S in G. Also |S0 | = 2|S|. Since
these two problems are maximization problems we have 2|S∗ | ≤ |S0∗ |.
4

Let S0 be a 2k-component set in G 0 , consisting of t components. From S0 we will
construct a k-component set S in G with |S| ≥ 12 |S0 |.
First, we prove a property of the components in G 0 [S0 ] which is as follows. For
any two distinct components T1 and T2 , if we look at the vertices in G induced by the
components then there are no common vertices. In other words, the sets {v ∈ V | v1 ∈
T1 or v2 ∈ T1 } and {v ∈ V | v1 ∈ T2 or v2 ∈ T2 } are disjoint. Suppose that these two
sets have a common vertex, say u. Then by construction, u1 ∈ T1 and u2 ∈ T2 and
(u1 , u2 ) ∈ E0 . This implies that T1 and T2 are connected, which is a contradiction.
Now, we construct a set S ⊆ V from S0 as follows. Let T1 , T2 , . . . , Tt be the components in G 0 [S0 ]. For each component Ti in G 0 [S0 ], if | Ti ∩ V1 | ≥ | Ti ∩ V2 | and | Ti ∩ V1 | ≥ k
choose a set Ji of any k vertices from Ti ∩ V1 ; otherwise if | Ti ∩ V1 | < k, take Ji = Ti ∩ V1 .
Finally, we update S = S ∪ {u ∈ V | u1 ∈ Ji }. If | Ti ∩ V2 | > | Ti ∩ V1 |, then we take
vertices from V2 into the set Ji and update S = S ∪ {u ∈ V | u2 ∈ Ji }.
Let S = J1 ∪ J2 ∪ . . . ∪ Jt , where Ji is the vertex set selected from the component Ti
of G 0 [S0 ]. We claim that S is a k-component set in G. It is easy to observe that G [ Ji ]
can have at most k vertices. Next, we need to prove that there is no edge between a
vertex u in Ji and a vertex v in Jj , for i 6= j. The existence of such an edge would
imply that the corresponding components Ti and Tj are not distinct (because of the
edges (u1 , v1 ), (u1 , v2 ), (u2 , v1 ), (u2 , v2 )).
From the construction of vertex set Ji from the component Ti , it follows that cardinality of Ji is at least half of the vertices in Ti . Therefore, |S| ≥ 12 |S0 |.
Therefore, for any given 2k-component set S0 in G 0 , one can construct a k-component
set S in G in polynomial time, such that

|S∗ |
|S|

≤

|S0∗ |
.
|S0 |

Corollary 3.3. For k > 0, M AX -IS is AP-reducible to M AX -k-OBCS with size amplification
of kn, where n is the number of vertices in the input instance of M AX -IS and k = 2i , for some
nonnegative integer i.
Proof. We reduce M AX -IS to M AX -k-OBCS by composing the reduction in Lemma 3.2
dlog ke times to get an instance of M AX -k-OBCS. Since the size of the new instance in
the reduction of Lemma 3.2 doubles, on applying the reduction dlog ke times, the size of
the M AX -k-OBCS instance is 2dlog ke n ≈ kn. Since the reduction in Lemma 3.2 is a ratio
preserving reduction, the composite reduction from M AX -IS to M AX -k-OBCS is a ratio
preserving reduction. Therefore, M AX -IS ≤AP M AX -k-OBCS.
Using Theorem 3.1 and Corollary 3.3 we have the following result for M AX -k-OBCS.
Corollary 3.4. For any e > 0, M AX -2i -OBCS is hard to approximate within a factor of n1−e ,
unless P = NP, where i is a constant nonnegative integer.
Next we will extend this lower bound result for M AX -k-OBCS, where k is a constant
nonnegative integer.
Theorem 3.5. For any e > 0, M AX -k-OBCS is hard to approximate within a factor of n1−e ,
unless P = NP, where k is a constant nonnegative integer.
Proof. Now consider a positive integer k such that 2i < k < 2i+1 for some non-negative
integer i. Suppose that M AX -k-OBCS can be approximated within a factor of β, to obtain
5

a subset Sk such that |Sk | ≥
M AX -2i -OBCS,

1 ∗
β | Sk |.

We can use this subset Sk to produce a solution for

by considering each component in Sk and dropping vertices arbitrarily
from each component until its size is at most 2i . Notice that the number of components
|S |
in Sk with size more than 2i can be at most 2ki , and the number of vertices we drop from
each such component is at most k − 2i . Thus the size of the constructed solution to M AX i +1
|S |
2i -OBCS, S2i is at least |Sk | − 2ki (k − 2i ) = |Sk | 2 2i−k . We also know that |S2∗i | ≤ |Sk∗ |,
and thus the approximation ratio of this constructed set is

| S2i |
2i + 1 − k 1
2i + 1 − k 1
≥ | Sk |
≥
∗
∗
| S2i |
| Sk |
β
2i
2i
Now the hardness result of M AX -2i -OBCS implies that β ∈ ω (n1−ε ), and thus M AX k-OBCS cannot be approximated within a factor of n1−ε for any constant k, unless P =
NP.
The authors in [1] have proved that, for any e > 0, M AX -D ISSO -S ET is hard to ap1
proximate within a factor of n 2 −e , unless P = NP. When i = 1, M AX -2i -OBCS is same
as M AX -D ISSO -S ET and we have the following result which is a stronger negative result
for M AX -D ISSO -S ET.
Theorem 3.6. For any e > 0, M AX -D ISSO -S ET is hard to approximate within a factor of n1−e ,
unless P = NP.
Next, we consider the inapproximability of M AX -k-OBCS when k is not a constant
and our result is as follows.
Theorem 3.7. If k is not a constant, then for any e > 0, M AX -k-OBCS cannot be approximated
in polynomial time with a better factor than n

log(n/k )
−e
log(n)

, unless P = NP.

Proof. Note that in the previous theorem, the graph G 0 constructed in the reduction
of M AX -k-OBCS from M AX -IS has size n0 = n2log k = nk, where n is the number of
vertices in an instance G of M AX -IS.
0

Now suppose that M AX -k-OBCS can be approximated within a factor of n0
in polynomial time, then

log(n /k)
−e
log(n0 )

log(n)
α( G )
compk ( G 0 )
−e
log(nk )
≤
≤
(
nk
)
|S|
|S0 |
log k
log n
n
−
· n log nk k log nk
=
e
(nk)

 1
n
− log k log k log nk
=
·
n
n
(nk)e
n
1− e 0
=
< n 1− e ,
0 = n
e
(n)
h
i
log k
where e0 = e 1 + log n . The last inequality holds as e0 > e. This contradicts the lower
bound for M AX -IS available in Theorem 3.1.
6

From Theorem 3.7, we have the following corollary,
Corollary 3.8. If k = O( logn n ), then M AX -k-OBCS is hard to approximate within a factor of
O(log n), unless P = NP.
4. Approximation algorithms for M AX -W EIGHTED -k-OBCS
We now turn to the weighted version of the problem, M AX -W EIGHTED -k-OBCS.
The input, in addition to a graph G = (V, E), consists of a weight function on the
vertices of the graph, w : V → R+ . Given a subset of vertices A ⊆ V, the weight of
the subset is defined as w( A) = ∑v∈ A w(v). In M AX -W EIGHTED -k-OBCS, the objective
is to find a subset of vertices S ⊆ V of maximum weight w(S) such that the size of the
largest component in G [S] is at most k. Since the unweighted case looked at thus far is
a special case of the weighted case (with the weight function being uniform), the lower
bounds derived in the previous section hold for the weighted version as well.
In this section, we look at an approximation algorithm for this problem and prove
an approximation guarantee of ∆, the maximum degree of the input graph.
Algorithm 4.1: k-Weighted-OBCS(G,w)

1
2
3
4
5
6
7
8

9
10
11

Input: An undirected simple graph G = (V, E) and w : V → R+
Output: S ⊆ V such that each component in G [S] has at most k vertices
if G = ∅ then
Return ∅;
end
if there exists a vertex u such that w(u) ≤ 0 then
Return k-Weighted-OBCS(G \ {u},w);
else
Let (s, t) be the edge in G that maximizes
 w ( s ) + w ( t );
w(u), u ∈ N [{s, t}]
Define the weight functions w1 (u) =
, and
0,
o.w.
w2 = w − w1 ;
S0 ← k-Weighted-OBCS( G, w2 );
Return S0 ∪ {s, t};
end

The algorithm is described in Algorithm 4.1 and the analysis makes use of the local
ratio theorem.
Theorem 4.1. [16] Let ( G = (V, E), w) be an instance of M AX -W EIGHTED -k-OBCS having
n vertices. Let w1 , w2 ∈ Rn such that w = w1 + w2 . Let S ⊆ V be an r-approximate feasible
solution of M AX -W EIGHTED -k-OBCS for G with respect to w1 and w2 . Then S is an rapproximate solution of M AX -W EIGHTED -k-OBCS for G with respect to w.
By using this theorem we have the following result.
Theorem 4.2. M AX -W EIGHTED -k-OBCS can be approximated within a factor of ∆, where ∆
is the maximum degree of the input graph G.
7

Proof. We prove the correctness by induction. In the base case, Line 2 is executed, and
it is ∆-approximate. In the inductive step, when Line 9 is executed, S0 is ∆-approximate
with respect to w2 . Now, the only vertices with a non zero weight in w1 are the vertices
s, t, and their neighbors. We will now prove that the weight w1 (s) + w1 (t) is at least a
1/∆ fraction of the total weight of N [{s, t}] (with respect to w1 ), which will prove the
theorem. First note that since (s, t) was the edge with the maximum combined weight,
we have that for any neighbour u of s, w1 (u) = w(u) ≤ w(t) = w1 (t), and likewise for
any neighbour v of t, we have w1 (v) = w(v) ≤ w(s) = w1 (s). Now we have,
w1 ( s ) + w1 ( t )
1
w1 ({s, t})
≥
≥
w1 ( N [{s, t}])
w1 ( s ) d G ( s ) + w1 ( t ) d G ( t )
∆
where the first inequality follows from our observation above, and the second inequality
holds since the degree of each vertex is at most ∆.
Thus using the local ratio theorem, we get a ∆-factor approximation algorithm for
M AX -W EIGHTED -k-OBCS.
It should be noted that due to the relation between the weighted and unweighted
cases, the upper bound derived here holds even for the unweighted case.
5. Approximation algorithms for M AX -D ISSO -S ET
A subset of vertices S ⊆ V in a graph G = (V, E) is called a dissociation set if
it induces a subgraph with vertex degree of at most 1. In Theorem 3.6 we show that
M AX -D ISSO -S ET is hard to approximate within a factor of n1−e , unless P = NP. In
this section, we prove that a greedy algorithm approximates M AX -D ISSO -S ET within a
factor of 3d + 2.
In this algorithm, we keep track of the components of size 1 and 2 in G [S]. S1 is the
set of vertices in S which form components of size 1 and S2 is the set of vertices which
form components of size 2 in G [S]. Each time we include a vertex into S, we update the
set X such that each component in G [S ∪ X ] has at least 3 vertices.
We first prove the correctness of the Algorithm 5.1 and then turn to its approximation
guarantee. Assume that the algorithm runs for q iterations. Since we include one vertex
in each iteration, it is clear that the size of the solution set is q. Let vi be the vertex
included in the ith iteration and so the solution set returned is S = {v1 , . . . , vq }.
Lemma 5.1. At any iteration of the algorithm, for each vertex v ∈ S2 , NV 0 (v) ⊆ X.
Proof. We prove this statement by induction on the iteration number. For the base case
S2 = ∅ and the statement trivially holds. Assume that the statement is true for the ith
iteration. Let vi+1 be the vertex added to S in (i + 1)th iteration. If vi+1 has no neighbor
in S1 then S2 remains unchanged and the statement holds. Otherwise, a new pair of
vertices is added to S2 and line 9 ensures that the neighbors of these two vertices are
included in X. Thus the lemma holds in this case as well.

8

Algorithm 5.1: M AX -D ISSO -S ET

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Input: An undirected simple graph G = (V, E)
Output: S ⊆ V such that each component in G [S] has at most 2 vertices
S1 = ∅; S2 = ∅; X = ∅; S = ∅; V 0 = V; i = 1;
while [V 0 6= ∅] do
choose a vertex v ∈ V 0 of minimum degree in G [V 0 ];
d i = d G [V 0 ] ( v ) ;
S = S ∪ { v };
if there exists a vertex p ∈ S1 such that ( p, v) ∈ E then
S2 = S2 ∪ {v, p};
S1 = S1 \ { p } ;
X = X ∪ NV 0 ( p) ∪ NV 0 (v);
V 0 = V \ ( S ∪ X );
else
S1 = S1 ∪ S
{ v };
X = X ∪ [ t∈S1 [ NV 0 (v) ∩ NV 0 (t)]];
V 0 = V \ ( S ∪ X );
end
i = i + 1;
end
Return S;

The correctness of the algorithm can be observed easily using the above lemma.
Consider a solution set S = S1 ∪˙ S2 returned by this algorithm. From Lemma 5.1, we can
see that each of the vertices in S2 are in a component of size exactly 2. Now consider a
vertex v ∈ S1 . It cannot be a neighbor to a vertex in S2 , again by lemma 5.1. In addition,
it cannot have a neighbor in S1 , since if it did, Line 7 would have moved these two
vertices to the set S2 during the run of the algorithm. Thus we see that the set S1 forms
an independent set in G [S] and thus the maximum size of a component in G [S] is 2,
implying that S is a feasible solution.
q

Lemma 5.2. n ≤ ∑i=1 (di + 1) ≤ 2n, where n is the number of vertices in the input graph.

Proof. When we choose a vertex v ∈ G [V 0 ] of minimum degree, we denote it as a chosen
vertex and denote its neighbors in G [V 0 ] as looked-at vertices. From the algorithm it is
clear that a chosen vertex is always included in S. Every time a vertex is looked-at, exactly
one of its neighbours is included in S. Once a vertex is looked-at twice, the algorithm
includes it in the set X. Therefore, a vertex can be looked-at at most twice and can be
chosen at most once.
Based on these notions, it follows that X is the set of vertices which are marked as
looked-at twice by the algorithm. In the ith step of the algorithm a minimum degree
vertex can be a looked-at vertex in V 0 . A chosen vertex vi can make at most di vertices
as looked-at twice. Thus inclusion of vi into S can add at most di vertices into the set X.
q
Also the set X is constructed in q steps. Therefore, ∑i=1 di ≥ | X |. From this observation
q
it follows that ∑i=1 (di + 1) ≥ | X | + |S| = n.
The greedy algorithm finally partitions the vertex set V as S∪˙ X. Each vertex in V is
probed at most twice (as chosen, or looked-at and chosen, or looked-at and looked-at) before
9

it is put in S or X. At the ith step (di + 1) represents the number of looked-at vertices
q
plus the chosen vertex. Therefore, ∑i=1 (di + 1) ≤ 2n.
q

Lemma 5.3. ∑i=1 (di + 1)di ≤ 3nd.
Proof. Every time we choose a vertex v ∈ V 0 = [V \ (S ∪ X )], we assign a token to each
edge e incident on a vertex of NV 0 [v].
Since the degree of vertex v in the ith step is di and it is of minimum degree, we
assign at least 21 di (di + 1) tokens in ith step. We claim that at the end of the algorithm,
an edge can have at most 3 tokens. Let vi be the vertex chosen in ith step. Let ( p, q)
be an edge in G [V 0 ] such that p ∈ NV 0 (vi ) and q ∈
/ NV 0 (vi ). While including vi into
S, we are assigning a token to ( p, q) and it remain in the subgraph G [V 0 ] with updated
vertex set V 0 . If a neighbor of p or p is chosen as a vertex of smallest degree in any of
the subsequent steps then ( p, q) will get one more token and the updated graph G [V 0 ]
will not have this edge. So we assume that in a subsequent jth step let v j be chosen as
smallest degree vertex and it a neighbor of q and not a neighbor of p. While including
v j in S we are assigning the 2nd token to ( p, q) and it remains as an edge in the updated
subgraph G [V 0 ]. Till now both p and q are looked-at once each. In a subsequent kth step
when a vertex u ∈ NV 0 [ p] ∪ NV 0 [q] is chosen and included in S, the edge ( p, q) receives
the 3rd token and it will no more in the updated subgraph G [V 0 ] (as p or q will be
looked-at twice and will not be present in the updated set V 0 ).
q
q
Therefore, we have ∑i=1 12 (di + 1)di ≤ 3| E| = 32 nd, and thus ∑i=1 (di + 1)di ≤ 3nd.
Lemma 5.4. The solution set returned by Algorithm 5.1 has size at least

n
.
3d+2

Proof. By using the inequalities in Lemma 5.2 and Lemma 5.3, we have
q

q

q

i =1

i =1

i =1

∑ ( d i + 1)2 = ∑ d i ( d i + 1) + ∑ ( d i + 1)
≤ 3nd + 2n.

From the Cauchy-Schwarz inequality, we get


q

∑ ( d i + 1)2 ≥

q

∑ i =1 ( d i + 1 )
q

∑i=1 12

i =1

≥

2

n2
.
q

Combining these two inequalities yields q ≥

n
.
3d+2

From the above lemma, we have the following result.
Theorem 5.5. M AX -D ISSO -S ET can be approximated within a factor of (3d + 2), where d is
the average degree of the input graph G.
10

5.1. Approximation algorithm for M AX -k-OBCS
In this section, we will generalize the (3d + 2) factor approximation algorithm for
M AX -D ISSO -S ET to get an algorithm for M AX -k-OBCS which is a (2k − 1)d + k factor
approximation algorithm. The following is a generalization of Algorithm 5.1.
Algorithm 5.2: Algorithm for M AX -k-OBCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Input: An undirected simple graph G = (V, E)
Output: S ⊆ V such that each component in G [S] has at most k vertices
S = ∅; X = ∅; V 0 = V; i = 1;
while [V 0 6= ∅] do
choose a vertex v ∈ V 0 of minimum degree in G [V 0 ];
d i = d G [V 0 ] ( v );
S = S ∪ { v };
for each vertex p ∈ V 0 and p 6= v do
if G [S ∪ { p}] has a component of size at least k + 1 then
X = X ∪ { p };
end
end
V 0 = V \ ( S ∪ X );
i = i + 1;
end
Return S;
By using a similar argument we have the following results.

Lemma 5.6. Let q be the number of iterations made by the while loop in the Algorithm 5.2.
q
(a) n ≤ ∑i=1 (di + 1) ≤ nk
q
(b) ∑i=1 di (di + 1) ≤ d(2k − 1)n.
Proof. (a) By assigning token to the vertices, as given in the proof of Lemma 5.2, it can
q
q
be proved that ∑i=1 di ≥ | X |. Hence, we get n ≤ ∑i=1 (di + 1). For the other inequality,
consider the following argument. In each iteration, when a vertex v is picked, assign
one token to that vertex and each of its neighbors in the graph G [V 0 ]. Thus, in the
ith iteration, the number of tokens assigned is exactly di + 1, and the total number of
q
tokens assigned is ∑i=1 (di + 1). Now, we look at the maximum number of tokens that
any particular vertex can get. Note that a vertex gets a token if it is either chosen or
looked-at, and once a vertex is chosen or included in the set X, it gets no more tokens.
Suppose that at the end of the algorithm, a vertex u has (k + 1) or more tokens. This
implies that either it was looked-at at least k + 1 times and then moved to the set X or it
was looked-at at least k times and then chosen. Neither of these cases is possible, since
when the vertex u is looked-at k times k of its neighbors have been chosen, and thus the
Line 6 will remove u after k of its neighbors have been chosen. Thus, any vertex can
have at most k tokens, and thus the total number of tokens available is at most nk. This
proves the second inequality.
(b) In the ith iteration, assume that vertex v is chosen. Assign a token to all the edges
incident on v and its neighbors from the set V 0 of the ith iteration. As argued in the case
q
of the dissociation set problem, due to minimality of di , we assign at least ∑i=1 21 di (di +
11

1) tokens. Now, we produce an upper bound on the total number of tokens by seeing
the maximum number of tokens that can be assigned to any edge. Consider an edge
e = (u, v) - it gets a token whenever at least one of its endpoints is either looked-at
or chosen. Now, from the proof of (a), it follows that any vertex is looked-at at most k
times and put into the set X, or looked-at at most k − 1 times and then chosen. Thus the
edge e can have at most (2k − 1) tokens, since if it receives that amount, then at least
one of its endpoints has been moved to either the set X or the set S and the edge no
longer receives any tokens. Thus the total number of tokens that any edge can receive
is (2k − 1) and the total number of tokens given out is at most | E|(2k − 1). Thus we get
q
∑i=1 di (di + 1) ≤ 2| E|(2k − 1) = d(2k − 1)n.
By using the inequalities in Lemma 5.6 and Cauchy-Schwarz inequality, we have
Theorem 5.7. M AX -k-OBCS can be approximated within a factor of (2k − 1)d + k, where d
is the average degree of the input graph G.
6. Upper bound for M AX -k-OBCS with large ∆
In this section, we provide a reduction from the M AX -D ISSO -S ET problem to the
M AX -IS problem, and use the upper bound result for M AX -IS from [17] to provide a
∆ log log ∆
O( log ∆ ) approximation factor, for sufficiently large values of ∆.
Lemma 6.1. M AX -D ISSO -S ET ≤AP M AX -IS.
Proof. The reduction is a straight forward one, where we solve the M AX -IS on the input
instance. Formally, the reduction is the identity mapping, and given an instance G =
(V, E) of M AX -D ISSO -S ET, it maps G = (V, E) as an instance of M AX -IS.
Given an independent set I in G, we construct a dissociation set S = I from I with
|S| = | I |. Given a maximum cardinality dissociation set S∗ in G, we construct an independent set I with | I | ≥ 12 |S∗ | as follows. The induced graph G [S∗ ] will have maximum degree of at most 1, and we can partition the set S∗ into two sets S0 = {v ∈
S∗ |dG[S∗ ] (v) = 0} and S1 = {v ∈ S∗ |dG[S∗ ] (v) = 1}. It is important to observe that
G [S1 ] forms an induced matching. We construct an independent set I in G by taking all
the vertices in S0 and exactly one vertex from each edge in G [S1 ]. This set I of vertices
is an independent set and | I | = |S0 | + 12 |S1 | ≥ 21 (|S0 | + |S1 |) = 12 |S∗ |. Thus we have
|S∗ | ≤ 2| I | ≤ 2α( G ), yielding
|S∗ |
α( G )
≤2
.
|S|
|I|
∆ log log ∆
log ∆ )

for suffi-

∆ log log ∆
log ∆ )

for suffi-

Theorem 6.2. [17] M AX -IS can be approximated within a factor of O(
ciently large values of ∆, where ∆ is the maximum degree of the input graph.
From Lemma 6.1 and Theorem 6.2, we get the following result,
Theorem 6.3. M AX -D ISSO -S ET is approximable within a factor of O(
ciently large values of ∆, where ∆ is the maximum degree of the input graph.
12

The reduction in the proof of Lemma 6.1 is also a reduction from M AX -k-OBCS to
M AX -IS. Here, given an instance G = (V, E) of M AX -k-OBCS, we take G = (V, E) as an
instance of M AX -IS. If I is an independent set in G then S = I is also a k-component set
in G. From a maximum cardinality k-component set S∗ in the graph G, we can construct
an independent set I in G with | I | ≥ 1k |S∗ |. Therefore, we have |S∗ | ≤ k| I | ≤ kα( G ).
From these inequalities we have

|S∗ |
α( G )
≤k
|S|
|I|
and the following result.
Theorem 6.4. For k > 0, M AX -k-OBCS is approximable within a factor of O(
sufficiently large values of ∆, where ∆ is the maximum degree of the input graph.

k∆ log log ∆
)
log ∆

for

7. Conclusion
We have proved that M AX -k-OBCS is hard to approximate like M AX -IS. We also
show that for k = O( logn n ), M AX -k-OBCS is hard to approximate within a factor of
O(log n). We generalize the greedy algorithm for M AX -IS to obtain an algorithm for
M AX -k-OBCS with an approximation factor of (2k − 1)d + k. This approximation factor
is a generalization of Turán’s bound for M AX -IS.
References
[1] Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, F. Werner, The complexity of dissociation set problems in
graphs, Discrete Applied Mathematics 159 (13) (2011) 1352–1366.
[2] J. Håstad, Clique is hard to approximate within n1−e , in: Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, IEEE, 1996, pp. 627–636.
[3] D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number,
in: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, ACM, 2006, pp.
681–690.
[4] D. Nakamura, A. Tamura, A revision of minty’s algorithm for finding a maximum weight stable set of a
claw-free graph, Journal of the Operations Research Society of Japan 44 (2) (2001) 194–204.
[5] D. Lokshantov, M. Vatshelle, Y. Villanger, Independent set in P5 -free graphs in polynomial time, in:
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for
Industrial and Applied Mathematics, 2014, pp. 570–581.
[6] M. Grötschel, L. Lovász, A. Schrijver, Geometric algorithms and combinatorial optimization, Vol. 2,
Springer Science & Business Media, 2012, pp. 296–298.
[7] B. S. Baker, Approximation algorithms for np-complete problems on planar graphs, Journal of the ACM
(JACM) 41 (1) (1994) 153–180.
[8] C. H. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes, Journal of
computer and system sciences 43 (3) (1991) 425–440.
[9] D. S. Hochbaum, Efficient bounds for the stable set, vertex cover and set packing problems, Discrete
Applied Mathematics 6 (3) (1983) 243–254.
[10] M. M. Halldórsson, J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and
bounded-degree graphs, Algorithmica 18 (1) (1997) 145–163.
[11] M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM Journal on Computing 10 (2) (1981)
310–327.
[12] R. Boliac, K. Cameron, V. V. Lozin, On computing the dissociation number and the induced matching
number of bipartite graphs, Ars Comb. 72.

13

[13] C. H. Papadimitriou, M. Yannakakis, The complexity of restricted spanning tree problems, Journal of the
ACM (JACM) 29 (2) (1982) 285–309.
[14] T. Fujito, A unified approximation algorithm for node-deletion problems, Discrete applied mathematics
86 (2) (1998) 213–231.
[15] Y. Zhang, Y. Shi, Z. Zhang, Approximation algorithm for the minimum weight connected k-subgraph
cover problem, Theoretical Computer Science 535 (2014) 54–58.
[16] R. Bar-Yehuda, K. Bendel, A. Freund, D. Rawitz, Local ratio: A unified framework for approximation
algorithms. in memoriam: Shimon even 1935-2004, ACM Computing Surveys (CSUR) 36 (4) (2004) 422–
463.
[17] M. M. Halldórsson, Approximations of weighted independent set and hereditary subset problems, in:
Graph Algorithms And Applications 2, World Scientific, 2004, pp. 3–18.
[18] G. Ausiello, Complexity and Approximability Properties: Combinatorial Optimization Problems and
Their Approximability Properties, Springer, 1999.

14

