algorithmnp-completeclique-problem

Finding vertices of a maximum clique in polynomial time


Say you were given a black box that solves a clique problem in constant time.

You give the black box an undirected graph G with a bound k and it outputs either "Yes" or "No" that the graph G has a clique with at least k vertices.

How would you use this black box to find the vertices of a maximum clique in polynomial time?


Solution

  • As a hint, think about what happens if you choose a node from the graph, delete it, and then check whether there's still a k-clique. The black box will either say that there is or that there isn't. What do you learn if there still is a k-clique? What do you learn if there isn't?

    Hope this helps!