# Homework 2

- Show that Clique (Does a graph \(G\) contain a
clique of size \(k\)?) and IndependentSet (Does a
graph \(G\) contain an independent set of size \(k\)?) are FPT on
\(r\)-regular graphs with parameter \(k+r\). (A graph is \(r\)-regular if
every vertex has the same degree \(r\).)
- In class, we showed that VariableDeletionAlmost2SAT for
an input \((\phi,k)\) of size \(n\) can be solved in time \(4^k n^{O(1)}\)
by a sequence of reductions. Describe, in pseudocode, the resulting
complete algorithm step by step. Use the polynomial-time LP-solver
as a black box.
- Book problem 3.17 (hint on page 74).
- Book problem 3.21 (hint on page 75).
- Book problem 3.22 (hint on page 75).

Deadline: April 12, beginning of class.