## Notes of Ryan O’Donnell’s lecture nr 2

1. Hardness of MAX ${k}$-COVER

1.1. The Theorem

Today, I explain the proof of Feige’s theorem, hardness of approximation of MAX ${k}$-COVER. It relies on NP-hardness of ${(1,\delta)}$-approximating MAX PROJECTION${(L,R)}$ (also known as LABEL COVER) for all ${\delta}$, a result due to Ran Raz and following from PCP and parallel repetition.

Recall that this problem has

• input : a regular bipartite graph, and for each edge, a projection constraint : ${\pi_{uv}:[L]\rightarrow[R]}$.
• output: an assigment of labels in ${[L]}$ and ${[R]}$ to vertices.
• objective: fraction of constraints satisfied.

Feige’s precise theorem is

Theorem 1 There is a Karp reduction of ${(1,\delta^3 /1000)}$-approximating MAX PROJECTION${(L,R)}$ to ${(1,1-e^{-1}+\delta)}$-approximating MAX ${k}$-COVER.

1.2. The proof

The reduction uses the following gadget. Let ${\Omega=\{ 0,1 \}^{R}}$, ${k=2}$, sets

$\displaystyle \begin{array}{rcl} S_{j}^{b}=\{x\in\{ 0,1 \}^R \,;\,x_j =b\}. \end{array}$

The ${OPT}$ of this instance is ${1}$. Indeed, two sets suffice to cover ${\Omega}$. But only the obvious pairs achieve this. Every other pair has value ${\leq 3/4}$.

Also, even a cheating solution taking a bounded number of sets does poorly if it is inconsistent. Consistent here means that covering includes a pair ${\{S_{j}^{0},S_{j}^{1}\}}$. Inconsistent solutions achieve at most ${1-2^{-?}}$.

Proof: Start with a MAX PROJECTION instance ${U}$, ${V}$, ${\pi_{uv}}$. We put a copy of the gadget on top of each edge. For ${e\in E}$, there is a ground set ${\Omega_e}$, a copy of ${\{ 0,1 \}^R}$. Overall ${\Omega=\bigcup_{e}\Omega_{e}}$. For each vertex ${v\in V}$, define sets ${S_{1}^{v},\ldots,S_{R}^{v}}$ to be the ${S_{j}^{1}}$‘s. For ${u'\sim v}$, the sets ${S_{j}^{v}}$ cover ${\Omega_{u'v}}$. For ${v'\sim u}$, the ${S_{i}^{u}}$‘s cover ${\{x\in\Omega_{uv'}\,;\,x_{\pi_{uv}(i)}=0}$.

Note that ${\Omega_{uv}}$ can be covered only by pairs ${\{S_{j}^{v},S_{j}^{u}\}}$.

Let ${k=|U|+|V|}$. Let us prove completeness: if there is an assignment ${\alpha}$ satisfying ${1}$-fraction of MAX PROJECTION constraints, then there exist ${k}$ sets covering ${\Omega}$. Indeed, consider all the ${S_{\alpha(w)}^{w}}$ for ${w\in U\cup V}$. It covers ${\Omega_{uv}}$ since it contains ${S_{j}^{1}}$ and covers ${S_{j}^{0}}$ with ${j=\pi_{uv}(\alpha(u))=\alpha(v)}$.

Soundness means that if best assignment ${\alpha}$ satisfies ${<\delta^3 /1000}$ of constraints, then any ${k}$ sets cover at most ${\frac{3}{4}+\delta}$ fraction of ${\Omega}$. By contrapositive. Assume ${OPT}$ of covering is ${>\frac{3}{4}+\delta}$, i.e. there is a collection ${\mathcal{S}}$ of ${k}$ sets with coverage ${>\frac{3}{4}+\delta}$. We shall decode ${\mathcal{S}}$ into an assignement ${\alpha:U\rightarrow[L]}$, ${V\rightarrow[R]}$ satsfying ${\geq \delta^3 /1000}$ of ${\pi_{uv}}$ constraints.

We do not need to be clever to achieve ${3/4}$. Here is some terminology.

Definition 2 For ${v\in V}$, let ${suggest(v)=\{j\in[R]\,;\, S_{j}^{v}\in\mathcal{S}\}}$ and for ${u\in U}$, ${suggest(u)=\{i\in[L]\,;\, S_{i}^{u}\in\mathcal{S}\}}$. Then define

$\displaystyle \begin{array}{rcl} Sets(u,v)=\textrm{ list of all } S_{i}^{u},\, S_{j}^{v}\in\mathcal{S}. \end{array}$

${Sets(u,v)}$ is consistent in above sens iff ${\exists i\in suggest(u)}$, ${\exists j\in suggest(v)}$ such that ${j=\pi_{uv}(i)}$. Since ${|Sets(u,v)|=|suggest(u)|+|suggest(v)|=k}$, we have ${|suggest(v)|=1}$ in average. ${|U|=|V|}$ and regularity implies that ${|Sets(u,v)|=2}$ on average over edges. Now we are ready to decode, i.e. make an assignment ${\alpha}$ by picking for ${\alpha(w)}$ a random element of ${suggest(w)}$, unless it is empty, in which case pick it arbitrarily. There remains to estimate the score of ${\alpha}$, which do not do here. Note that ${\delta^3 /1000}$ is not greedy. $\Box$

1.3. What should we remember from this proof

To prove ${(c,s+\delta)}$-inapproximability for MAX BLAH, it suffices to reduce from MAX PROJECTION using a gadget (instance of MAX BLAH) with special properties.

1. Sets involved are cubes ${\{ 0,1 \}^R}$.
2. ${OPT}$ of gadget is ${c}$. Further, there exist exactly ${R}$ optimal solutions corresponding to hald-cubes ${\{x_i =1\}}$.
3. Every solution of the gadget should suggest at most a constant number of optimal solutions.
4. Solution which suggest no optimal solutions should have value ${\leq s + O_{\delta}(1)}$.

Theorem 3 This methodology of gadgets is a theorem, but only if you reduce from MAX BIJECTION.

Definition 4 MAX BIJECTION is MAX PROJECTION where ${\pi_{uv}}$‘s are bijections.

Unfortunately, MAX BIJECTION is not a hard problem. Indeed, ${(1,1)}$-approximating MAX BIJECTION${(R)}$ is in P.

Subhash Khot’s Unique Games Conjecture states that ${\forall \delta>0}$, ${\exists R}$ such that MAX BIJECTION${(R)}$ is ${(1-\delta,\delta)}$-inapproximable.

Then, above technology implies

Theorem 5 Assuming UGC, inapproximability results can be obtained for many problems in a routine manner.

The point is wether the method allows to get tight inapproximability bounds. Answer is yes for certain problems, but it requires sometimes a highly non trivial and mathematical analysis of the various gadget properties above, especially the last one.

References