Example 14.8
The Clique Problem Let G be an undirected graph with vertices υ 1 ,υ 2 ,…,υ n . A
k-clique is a subset V k ⊆ 2 V , such that there is an edge between every pair of
vertices υ i , υ j ∈ V k . The clique problem (CLIQ) is to decide if, for a given k, G
has a k-clique.
A deterministic search can examine all the elements of 2 V . This is
straightforward, but has exponential time-complexity. A nondeterministic
algorithm just guesses the correct subset. The representation of the graph and the
checking are similar to the previous example, so we claim without further
elaboration that the clique problem can be solved in O(n 4 ) time and that
CLIQ ∈ NP.
There are many other such problems: some similar to our examples, others
quite different, but all sharing the same characteristics.
1. All problems are in NP and have simple nondeterministic solutions.
2. All problems have deterministic solutions with exponential time-complexity,
but it is not known if they are tractable.
To get further insight into the connection between these various problems,
we need to find some commonality for all these seemingly different cases.
EXERCISES
1. In Example 14.6, show how a trial solution can be generated in O(n) time.
This means that all 2 n possibilities must be generated in a decision tree with
height O(n).
2. Show how in Example 14.6 the checking of the trial solution can be done in
O(n 2 logn) time.
3. Discuss how in HAMPATH a permutation can be generated
nondeterministically in O(n 3 ) time.
The Clique Problem Let G be an undirected graph with vertices υ 1 ,υ 2 ,…,υ n . A
k-clique is a subset V k ⊆ 2 V , such that there is an edge between every pair of
vertices υ i , υ j ∈ V k . The clique problem (CLIQ) is to decide if, for a given k, G
has a k-clique.
A deterministic search can examine all the elements of 2 V . This is
straightforward, but has exponential time-complexity. A nondeterministic
algorithm just guesses the correct subset. The representation of the graph and the
checking are similar to the previous example, so we claim without further
elaboration that the clique problem can be solved in O(n 4 ) time and that
CLIQ ∈ NP.
There are many other such problems: some similar to our examples, others
quite different, but all sharing the same characteristics.
1. All problems are in NP and have simple nondeterministic solutions.
2. All problems have deterministic solutions with exponential time-complexity,
but it is not known if they are tractable.
To get further insight into the connection between these various problems,
we need to find some commonality for all these seemingly different cases.
EXERCISES
1. In Example 14.6, show how a trial solution can be generated in O(n) time.
This means that all 2 n possibilities must be generated in a decision tree with
height O(n).
2. Show how in Example 14.6 the checking of the trial solution can be done in
O(n 2 logn) time.
3. Discuss how in HAMPATH a permutation can be generated
nondeterministically in O(n 3 ) time.