Homework 9Due Friday April 30

COURSE WEBSITE: www.cs.umd.edu/$\sim$gasarch/858/858.html

1. (0 points) Write your name clearly. Write which HW this is on top of your paper clearly. Staple the HW so its not loose pages. Where and when will the final be?

2. (20 points) Assume $P\ne NP$. Let
   
   $$MAXIND = \{ (G,k) \mid G\hbox{ has a maximum indepdent set of size $k$} \}.$$
   
   
   This problem is known to be NP-complete. Let

   $MAXINDFUN(G)$ be the function that, given $G$, returns the size of the maximum independent set of $G$.

   Show that there is no polynomially computable function $f$ such that, for all $G$,

   $0\le MAXINDFUN(G) - f(G) \le 100$.

3. (50 points) Assume $P\ne NP$. For all $i,j\ge 0$ let

   $A_{i,j} = \{ G \mid G\hbox{ is planar and $\chi(G)\le i$\ and every vertex has degree $\le j$} \}$

   For which $i,j$ is $A_{i,j}\in P$? For which $i,j$ is $A_{i,j}\notin P$? Every $(i,j)$ must be in one of the two categories. (You may assume that 3-col is NP-complete. You may use theorems from graph theory, but must provide a reference. You may use the web or other non-organic resources, but you must hand in a complete solution written in your own words.)

4. (30 points) Assume that $P\ne NP$. Assume that there is a polynomial time function $g$ such that

   if $G$ is $c$-colorable then $g(G)$ is $n^{c/10}$-colorable (where $n$ is the number of vertices in the original $G$).

   Find a $\delta$ such that the following is true:

   There is no $f\in P$ such that, for all graphs $G$, if $G$ has $n$ vertices

   $\chi(G) \le f(G) \le n^{\delta}\chi(G)$.

   Try to make your $\delta$ as small as possible. You need to prove your result.

5. (Extra Credit) $A\le_{2-tt} B$ was defined in class. Show that if there is a sparse set $S$ with $SAT\le_{2-tt} S$ then $P=NP$.