\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{29 November 2014}{24}

\begin{center}
\Large{\bf Problem of the Week -- 22}
\end{center}

\newcommand{\is}{{\sc IndependentSet}}

{\bf Hardness of independent set} 

Recall that an {\em independent set}\/ of an undirected graph $G$ is a
subset $V'$ of vertices such that no two vertices in $V'$ have an edge
in $G$.  The \is\ problem is to find a maximum-size independent set in
$G$.  We know that \is\ is NP-complete.  In this problem, we
investigate the approximability of \is.

Define the {\em product}\/ of two graphs $G_1 = (V_1, E_1)$ and $G_2 =
(V_2, E_2)$ as $G = (V, E)$, where
\[V = \{\langle
v_1, v_2 \rangle: v_1 \in V_1, v_2 \in V_2\},
\] 
and there is an edge between vertices $\langle u_1, u_2 \rangle$ and
$\langle v_1, v_2 \rangle$ in $G$ if either $u_1 = v_1$ and $(u_2,
v_2) \in E_2$ or $(u_1, v_1) \in E_1$.  For a positive integer $n$,
let $G^n$ be defined by the recurrence relation $G^{i+1} = G^i \times
G$ and $G^1 = G$.
\begin{itemize}
\item[{\bf (a)}]  Prove that $G$ has an independent set of size $k$ if
  and only if $G^t$ has an independent set of size $k^t$.
  
\item[{\bf (b)}] Give a polynomial-time algorithm to construct an
  independent set of $G$ of size $\lceil k^{1/t} \rceil$ from any
  independent set of $G^t$ of size $k$.
  
\item[{\bf (c)}] Using parts~(a) and~(b), argue that if there exists a
  constant $c$ such that there is a polynomial-time $c$-approximation
  algorithm for \is, then one can obtain an arbitrarily good
  approximation -- $(1 + \eps)$-factor for $\eps > 0$ arbitrarily
  small -- for \is\ in polynomial time.
\end{itemize}

\end{document}