Information Technology Reference
In-Depth Information
TEST CASES
The quality of an approximation to the clique function
f
(
n
)
clique
,
k
is determined
by providing positive and negative test inputs. A
k
-positive test input
is a binary
n
(
n
−
1
)
/
2-
tuple that describes a graph containing a single
k
-clique.
The negative test inputs, defined below, describe graphs that have many edges but not
quite enough to contain a
k
-clique. A special set of negative test inputs is associated with
balanced partitions of the vertices of an
n
-vertex graph
G
=(
V
,
E
)
.A
(
k
−
1
)
-balanced
partition
of
V
=
{
v
1
,
...
,
v
n
}
is a collection of
k
−
1 disjoint sets,
V
1
,
V
2
,
...
,
V
k−
1
,such
that each set contains either
n/
(
k
−
10
or
n/
(
k
−
1
)
elements. (By Problem
9.5
there are
w
=
n
mod (
k
−
1
)
sets of the first kind and
k
−
1
−
w
sets of the second kind.) The graph
associated with a particular
(
k
1
)
-balanced partition has an edge between each pair of vertices
in different sets and no other edges. For each
(
k
−
−
1
)
-balanced partition, a
k
-negative test
input
is a binary
n
(
n
−
1
)
/
2-tuple
x
describing the graph
G
associated with that partition.
LEMMA
9.6.5
There are
τ
+
k
-positive test inputs, where
τ
+
=
n
k
=
n
!
k
!(
n
−
k
)!
and
τ
−
k
-negative test inputs, where for
w
=
n
mod (
k
−
1
)
n
!
τ
−
=
n
n
w
)!
Proof
It is well known that
τ
+
=
k
. To derive the expression for
τ
−
(
1
!)
w
(
1
!)
k−
1
−w
w
!(
k
−
−
1
k
−
k
−
we index each
element of each set in a
(
k
−
1
)
-balanced partition. Such a partition has
w
=
n
mod (
k
−
1
)
sets containing
n/
(
k
−
1
)
elements and
k
−
1
−
w
sets containing
n/
(
k
−
1
)
elements.
The elements in the first
w
sets are indexed by the pairs
{
(
i
,1
)
,
(
i
,2
)
,
...
,
(
i
,
n/
(
k
−
1
)
)
}
for 1
≤
i
≤
w
. Those in the remaining
k
−
1
−
w
sets are indexed by the pairs
{
P
be the set of all such pairs. To define a
k
-negative graph, we assign each vertex in the set
V
=
(
i
,1
)
,
(
i
,2
)
,
...
,
(
i
,
n/
(
k
−
1
)
)
}
for
w
+
1
≤
i
≤
k
−
1.
(See Fig.
9.13
.) Let
1 sets. If vertices
v
a
and
v
b
are in the same set, the edge variable
x
a
,
b
=
0; otherwise
x
a
,
b
=
1. These
assignments define the edges in a graph
G
=(
V
,
E
)
.Thereare
n
!
assignments of vertices
to pairs. Of these, there are
(
{
1, 2,
...
,
n
}
to a unique pair. This partitions the vertices into
k
−
n/
(
k
−
1
)
!)
w
(
n/
(
k
−
1
)
!)
k−
1
−w
w
!(
k
−
−
w
)!
that
1
(
1, 1
)
(
1, 2
)
(
1, 3
)
(
1, 4
)
(
2, 1
)(
2, 2
)
(
2, 3
)
(
3, 1
)
(
3, 2
)
(
3, 3
)
v
3
v
7
v
1
v
2
v
9
v
5
v
10
v
6
v
4
v
8
v
2
v
1
v
3
v
7
v
5
v
10
v
9
v
4
v
8
v
6
Figure 9.13
Asetofpairs
P
indexing the elements of sets in a
(
k −
1
)
-balanced partition of
aset
V
of
n
vertices. In this example
n
=
10 and
k
=
4 and the partition has three sets,
V
1
,
V
2
,and
V
3
containing four, three, and three elements, respectively. Shown are two assignments of
variables to pairs in
P
that correspond to the same partition of
V
.
Search WWH ::
Custom Search