Question

The 4-CLIQUE problem is defined as follows: Given a graph G, does it have a clique of size 4? Is this problem in P? Yes, no, unknown? Justify your answer (if your answer is “yes”, briefly describe a polynomial-time algorithm).

Answer 1

The Clique Problem: Given a graph G and an integer k, does G contain a k-clique?

“Problem Instance” – the specific cases

Ex: Does contain a 4-clique? (no)

Ex: Does contain a 3-clique? (yes)

Problems as Sets of “Yes” Instances

Ex: CLIQUE = { (G,k) | G contains a k-clique }

E.g., ( , 4) ∉ CLIQUE

E.g., ( , 3) ∈ CLIQUE

POLYNOMIAL-TIME ALGORITHM --

A polynomial-time algorithm is an algorithm whose execution time is either given by a polynomial on the size of the input, or can be bounded by such a polynomial.

Problems that can be solved by a polynomial-time algorithm are called tractable problems.

For example, most algorithms on arrays can use the array size, n, as the input size. To find the largest element in an array requires a single pass through the array, so the algorithm for doing this is O(n).

Sorting algorithms usually require either O(n log n) or O(n²) time. Heapsort takes O(n log n) time in all cases. Quicksort takes O(n log n) time on average, but O(n²) time in the worst case.

Regarding O(n log n) time, note that

• The base of the logarithms is irrelevant, since the difference is a constant factor, which we ignore; and
• Although n log n is not, strictly speaking, a polynomial, the size of n log n is bounded by n², which is a polynomial.

PLEASE GIVE A THUMBSUP IF IT WAS HELPFUL AND LEAVE A COMMENT FOR ANY QUERY.

THANKS.