⟸ Go Back ⟸
Exercise 2 (Homework 7).
(polynomial time, exponential time, NP-completeness)

Searching for cliques

A k-clique in a graph G = (V,E) is a complete subgraph of order k of G, that is, a subgraph on k vertices having all possible edges between them. We say that G' is a clique in G if G' is a k-clique in G for some k. Recall the following well-known NP-complete problem. \mathtt{Clique}\text{: Given an undirected graph $G$ and a positive integer $k$, determine whether $G$ contains a $k$-clique}.

Some problems related to \mathtt{Clique} are the following.

  1. Maximal clique. A clique is maximal if it cannot be enlarged, that is, if there is no larger clique containing it. Describe an algorithm as efficient as possible that, given an undirected graph G, finds a maximal clique of G. What’s the cost of your algorithm?

  2. Maximum clique. A clique is maximum if there is no other clique having more vertices (a maximum clique is always maximal but the reverse inclusion is not always true). Describe an algorithm as efficient as possible that, given an undirected graph G, finds a maximum clique of G. What’s the cost of your algorithm?

  3. Planar clique. Recall that a graph is planar if it can be drawn on the plane without edge crossings. Let \mathtt{Planar Clique} be the following problem: given a planar undirected graph G and a positive integer k, does G have a k-clique? Show that \mathtt{Planar Clique} has a polynomial-time algorithm.

    Note

    Planarity testing can be done in linear time (on the number of vertices). You can assume the existence of these algorithms for the exercise.

  4. Half clique. Let \mathtt{Half Clique} be the following problem: given an undirected graph G, does G have a clique with at least \big\lceil \frac{|V(G)|}{2} \big\rceil vertices? Prove that \mathtt{Half Clique} is NP-complete.