Recitation 13

Recitation notes for the week of April 23, 2025.

Homework 8, Question 1

The problem

Given a graph $G$ and a number $k$, does $G$ contain a clique of size at least $k$? I.e. does there exists a subset $S\subseteq V$ such that $|S|=k$ and there are all possible $\binom{k}{2}$ edges present among the vertices in $S$?

Sample Input/Output pairs

For the sample inputs, let us consider the following graph, which we will call $G_0$:

G_0
  • Input: $G_0, 3$
  • Output: true (Consider the three blue nodes)
  • Input: $G_0, 4$
  • Output: false (Every subset of 4 nodes has at least 2 out of the 6 edges missing)

Question 1, Part (a)

The problem

Argue that the Clique problem is in $\mathcal{NP}$.

What do we need to do to show a problem is in $\mathcal{NP}$?

To show that a problem $X$ is in $\mathcal{NP}$, you need to show that there is a witness for an input being in $X$: i.e. if $X$ on input $I$ would output true, then there would be a witness $w$ such that in polynomial time, given $I$ and $w$, one can indeed verify that $X$ on input $I$ should indeed output true. To be more precise, there exists a polynomial time function $\mathbb{V}$ (for "verifier") such that for every input $I$, there exists a polynomial-sized witness $w$ such that $\mathbb{V}(I,w)=$true if and only if $X$ on input $I$ outputs true.

Note the asymmetry above

Note the inherent asymmetry in the above condition. In particular:

  • If $X$ on input $I$ outputs true, then you just need one witness $w$ such that $\mathbb V(I,w)$=true.
  • If $X$ on input $I$ outputs false, then for all witnesses $w'$, we have $\mathbb V(I,w')$=false.

Proof Idea

Recall for the problem, we are given as input a graph $G$ and an integer $k$ and we need to check if $G$ has a clique of size at least $k$ or not.

It turns out that in this case the witness for an input instance $I=(G=(V,E),k)$ is just a subset $S\subseteq V$ of size exactly $k$. We now claim that there exists a polynomial time verifier with this witness. In particular, you need to argue the following:

Exercise

Show that there exists a polynomial time verifier (i.e. an algorithm) $\mathbb V$ such that on input $G$ and a subset $S$ (as above), it outputs true if $S$ is a clique in $G$ and false otherwise.

Assuming the above is true, here is the quick argument that we want. Suppose on input $(G,k)$ the Clique problem should output true, then there has to be a subset $S^*\subseteq V$ with $|S^*|=k$ such that $S^*$ is a clique and hence we will have $\mathbb V(G,S^*)$=true, as desired. On the other hand, if the clique problem should output false for input $(G,k)$, then it has to be the case that for every $S\subseteq V$ of size $k$, $S$ is not a clique. Hence for all such $S$, we have $\mathbb V(G,S)$=false, as desired.

Question 1, part (b)

The problem

Argue that the Clique problem is $\mathcal{NP}$-complete.

What do we need to do to prove a problem is $\mathcal{NP}$-complete?

To show that a problem $X$ is $\mathcal{NP}$-complete, you need to argue two things:

  1. Argue that $X$ is in $\mathcal{NP}$.
  2. Argue that $Y\le_P X$, where $Y$ is $\mathcal{NP}$-complete.

Note that part (a) above does step 1 above for the Clique problem. So for part (b) the main work is to (1) figure out an appropriate $\mathcal{NP}$-complete problem $Y$ and (ii) provide a polynomial time reduction to prove that $Y\le_P \text{Clique}$. For both, we repeat the following hint from the problem statement:

Hint

It might be useful to consider the complement graph of $G$ and figure out what a clique in $G$ looks like in its complement. (The complement of $G=(V,E)$ is the graph $H=(V,E')$, where $(u,u)\in E'$ if and only if $(u,v)\not\in E$: i.e. if an edge is present in $G$, then it not present in $H$ and if an edge is not present in $G$, then it is present in $H$.)

Homework 8, Question 2

The problem

Given a graph $G$, output a largest clique of $G$, i.e., the output $S$ should be a clique and it must be the case that $G$ does not have a clique of size $|S|+1$.

Sample Input/Output pairs

  • Input: $G_0$ (from Question 1)
  • Output: The set of blue vertices.

Solving MaxClique solves the Clique problem

We note that there is a simple polynomial-time reduction from the Clique problem to the max clique problem:

  1. Given input $(G,k)$ for the Clique problem, run the algorithm for the MaxClique problem on $G$ to get output $S$.
  2. Output true (for the Clique problem) if and only if $|S|\ge k$.

What Question 2 does is to show that there is also a polynomial time reduction in the other direction: i.e. there is a polynomial time reduction from the MaxClique problem to the Clique problem.

Question 2, part (a)

The main algorithmic ideas needed to solve both sub-parts is already there in the book: see the description at the bottom on Page 454 for how to solve similar problem for the independent set problem.

Sub-part (1)

Even though it is not needed, we provide the algorithm details of the reduction (we use A to denote the algorithm that solves the Clique problem in $T(n)$ time.

Algorithm Details

                            k = 1

                            for k in 2 .. n:
                                if not A(G,k): # This is the first value for which there is no clique of size k
                                    return k-1 # Note that by definition there is a clique of size k-1

                            return n

Sub-part (2)

You need to use binary search to figure out the size of the largest clique in $G$. However yo get full credit for this sub-part, you need to specify the following:

Exercise

For what values of $k$ do you call A(G,k)? In particular, in binary search you rule out half of the possibilities-- how do you do that in this case?

Question 2, part (b)

The problem

Assume that the Clique problem from Question 1 is in $\mathcal{P}$. Show that then the MaxClique problem is also in $\mathcal{P}$ (i.e. there exists a polynomial time algorithm to solve the MaxClique problem).

We re-state the hint from the problem statement:

Hint

Note that since Clique is in $\mathcal{P}$, there exists a polynomial time algorithm $\mathcal{A}$ to solve that problem. Think of how you can call $\mathcal{A}$ multiple times to solve the MaxClique problem.

The only thing we would add to the above is that the multiple calls to $\mathcal{A}$ need not be independent. In particular, you can use the output of earlier calls to $\mathcal{A}$ to determine on what input to call the later invocations of $\mathcal{A}$ on.

Satisfiability and SAT solvers

For Homework 8, Question 3, you will need to work with SAT solvers. In the remainder of the recitation, we will do the following:

Support page for SAT solvers

Review the support page on Satisfiability and SAT solvers.