Thoery of Computation: P vs NP Let G be a graph. A clique in G is a subgraph in

Question

Thoery of Computation: P vs NP

Let G be a graph. A clique in G is a subgraph in which every two nodes are connected by an edge.

The CLIQUE problem takes k, the size of the clique, as one of the arguments. As we know, this problem is in NP, and no polynomial-time solution is known.

Show that, if CLIQUE was in P (that is, if NP = P), then there would be a polynomial-time algorithm FIND-LARGEST-CLIQUE that, given a graph (and nothing else), finds the largest clique in it (or one of them, if there are multiple). Note that FIND-CLIQUE is not a YES/NO algorithm, since it returns the actual clique.

Hint: use CLIQUE as a boolean subroutine for FIND-CLIQUE.

Explanation / Answer

FIND-LARGEST-CLIQUE(G):

let there are V nodes in G

for i = V to 1

if clique(G, i) (i..e, check if there is a clique in G)

find the largets clique of size i and return

As cliqueu is in P and as we are running clique V times this is also polytime algorithm

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.