# 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.