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