Homework 2

1. 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\).)
2. 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.
3. Book problem 3.17 (hint on page 74).
4. Book problem 3.21 (hint on page 75).
5. Book problem 3.22 (hint on page 75).

Deadline: April 12, beginning of class.