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:

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.

Recap of a polynomial time reduction

We review the definition of a polynomial time reduction. How this can be useful to solve part (b) is something that y'all will need to figure out on your own.

We say a problem $A$ is polynomial time reducible to a problem $B$ (denoted by $A\le_P B$) if there exists a algorithm/reduction $\mathcal{R}$ (with polynomial runtime $r(n)$) such that

1. (Pre-processing step) On any input $\mathbf{x}$ for problem $A$, it computes a valid input $\mathbf{y}$ for problem $B$.
2. Assuming there is a blackbox algorithm $\mathcal{B}$ for problem $B$, it then runs $\mathcal{B}(\mathbf{y})$. ¹
3. (Post-processing step) Based on the answer from $\mathcal{B}(\mathbf{y})$, it does some computation and outputs the answer for input $\mathbf{x}$ (for problem $A$).

The runtime of the reduction is the time take in steps 1 and 3 above and is denoted by $r(n)$ for inputs $\mathbf{x}$ of size $n$.

Now if we were to use the reduction $\mathcal{R}$ to solve the problem $A$ on input $\mathbf{x}$, what would be its total time? To answer this let $m$ be the size of $\mathbf{y}$ that is computed in step 1 above and let $T(m)$ be the runtime of the blackbox algorithm $\mathcal{B}$. Then using the above, we can solve the problem $A$ on input $\mathbf{x}$ in time \[r(n)+T(m).\]

Now let's simplify the above when both $r(\cdot)$ and $T(\cdot)$ are some polynomial functions. Then since Step 1 takes at most $r(n)$ time and it computes $\mathbf{y}$, we must have that the size of $\mathbf{y}$ satisfies \[ m\le r(n).\] The the overall runtime is at most \[r(n)+T(r(n)).\] Note that under our assumption that $r(\cdot)$ and $T(\cdot)$ are some polynomial functions, the above runtime is $\text{poly}(n)$.

In other words, if $B$ can be solved in polynomial time, then the reduction $\mathcal{R}$ shows that $A$ can also be solved in polynomial time, i.e $A\le_P B$.

Note that in class, we have used the "contra-positive" implication: i.e. if $A\le_P B$ and $A$ is not solvable in polynomial time, then $B$ cannot be solved in polynomial time either.

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
                        

Support page for SAT solvers

Review the support page on Satisfiability and SAT solvers.