Information Technology Reference
In-Depth Information
then
P
=
NP
. We show that
HALF
-
CLIQUE CENTRAL SLICE
is
NP
-complete by reducing
HALF
-
CLIQUE
(see Problem
8.25
)toit.
DEFINITION
9.6.7
A
central slice
of a function
f
:
B
n
on
n
variables,
f
[
n/
2
]
,isthe
→B
n/
2
th slice.
A central slice of a function
f
on
n
variables is the function that has value 0 if the weight
of the input tuple is less than
n/
2
, value 1 if the weight exceeds this value, and is equal to
the value of
f
otherwise.
Given the function
f
:
,
f
(
n
)
denotes the function restricted to strings of length
n
. The family of central slice functions
B
∗
→B
(
f
(
n
)
)
[
n/
2
]
{
|
n
≥
}
2
identifies the language
n
(
f
(
n
)
)
[
n/
2
]
(
x
)=
1,
n
L
central
(
f
)=
{
x
∈B
|
≥
}
2
.
The central clique function
f
(
n
)
clique
,
has value 1 if the input graph contains a clique
n/
2
vertices. The central slice of the central clique function
f
(
n
)
clique
,
on
n/
2
is called the
n/
2
half-clique central slice function
and denoted
f
(
n
)
clique slice
. It has value 1 if the input graph
n/
2
either contains a clique on
vertices or contains more edges than are in a clique of this
size.
The language
HALF
-
CLIQUE
is defined in Problem
8.25
as strings describing a graph and
an integer
k
such that a graph on
n
vertices contains an
n/
2-clique or has more than
k
edges.
The language
HALF
-
CLIQUE CENTRAL SLICE
associated with the central slice of a central
clique function is defined below. It simplifies the following discussion to define
e
(
k
)
as the
number of edges between a set of
k
vertices. Clearly,
e
(
k
)=
2
.
HALF
-
CLIQUE CENTRAL SLICE
Instance:
The description of an undirected graph
G
=(
V
,
E
)
in which
|
V
|
is even.
Answer:
“Yes” if
G
contains a clique on
|
V
|
/
2 vertices or at least
e
(
|
V
|
/
2
)
/
2edges.
THEOREM
9.6.10
The language
HALF
-
CLIQUE CENTRAL SLICE
is
NP
-complete. Further-
more, for all
2
≤
k
≤
n
f
(
n
)
clique
,
[
k
]
C
Ω
mon
f
(
n
)
clique slice
C
Ω
mon
≤
n/
2
For
k<e
(
n/
2
)
,
f
(
n
)
clique
,
[
k
]
=
τ
e
(
n
)
k
+
1
.
n/
2
Proof
We show tha t
HALF
-
CLIQUE CENTRAL SLICE
is
NP
-complete by reducing
HALF
-
CLIQUE
to it. Given a graph
G
=(
V
,
E
)
in
HALF
-
CLIQUE
that has
n
vertices,
n
even, we
construct a graph
G
=(
V
,
E
)
on 5
n
vertices such that
G
either contains an
n/
2-clique
or has more than
k
edges if and only if
G
contains a (central) clique on 5
n/
2verticesor
has at least
edges. The construction, which can be done in polynomial time,
transforms a graph on
n
vertices to one on 5
n
vertices such that the former is an instance of
HALF
-
CLIQUE
if and only if the latter is an instance of
HALF
-
CLIQUE CENTRAL SLICE
.
Let
V
=
e
(
5
n/
2
)
/
2
.Con ruct
G
{
v
1
,
v
2
,
...
,
v
n
}
from
G
by adding the 4
n
vertices
R
=
. Represent edges in
E
of
G
with the edge
{
r
1
,
r
2
,
...
,
r
2
n
}
and
S
=
{
s
1
,
s
2
,
...
,
s
2
n
}
variables
. Each edge between vertices of
G
is an edge between
vertices
V
of
G
. Let every edge between vertices in
R
be in
G
as well as all edges between
vertices in
V
and
R
. Set the edge variables so that the edges between
r
i
and
s
i
,1
{
y
i
,
j
|
1
≤
i<j
≤
5
n
}
≤
i
≤
2
n
,
Search WWH ::
Custom Search