
\ifx\bookMode\undefined%
\documentclass[11pt]{article}%
\usepackage{caption}%
\usepackage{473} %
\usepackage{473extra} %
\begin{document}
\newcommand{\StandAloneMode}[1]{#1}%
\newcommand{\BookMode}[1]{}%
\fi

\providecommand{\MinCut}{\Algorithm{MinCut}\xspace}%
\providecommand{\polylog}{\mathop{\mathrm{polylog}}}%

\noindent\textbf{\LARGE H{}W 7 (due Wednesday, at noon, October 24, \Year)}\\
\noindent{\textbf{\Course: \CourseName, \Semester}}
\hfill\Version{1.3}%
\\[-0.12cm]
\Hr

   
   \noindent%
   
   Submission guidelines and policies as in homework 1.
   
   \Hr
   

\begin{questions}

    \item \HWProblem{100}{More about coloring.}%
    {%
    }{}{}{}
    \begin{questions}
        \item \points{20} Prove that a graph $\Graph$ with a chromatic
        number $k$ (i.e., $k$ is the minimal number of colors needed
        to color $G$), must have $\Omega(k^2)$ edges.
    
           

           \item \points{20} Consider a graph $\Graph$ with $n$
           vertices and $m$ edges. Consider the greedy algorithm,
           which orders the vertices in arbitrary order
           $v_1,\ldots, v_n$. Assume the algorithm colored the first
           $i-1$ vertices. In the $i$\th iteration, the algorithm
           assign $v_i$ the lowest color that is not assigned to any
           of its neighbors that are already colored (assume the
           colors used are the numbers $1,2,3,\ldots$). Provide an
           upper bound, as low as possible, on the number of colors
           used by your algorithm as a function of $m$. You can assume
           $m \geq n \geq 100$.

           \item \points{20} Prove that if a graph $\Graph$ is
           $k$-colorable, then for any vertex $v$, the graph
           $\GraphA = \Graph_{N(v)}$ is $k-1$-colorable, where $N(v)$
           is the set of vertices in $\Graph$ adjacent to $v$, and
           $\Graph_{N(v)}$ is the \emphi{induced subgraph} on
           $N(v)$. Formally, we have
           \begin{equation*}
               \Graph_{N(v)} = \pth{N(v), \Set{ uv\in \EdgesX{\Graph}
                  }{ u,v \in N(v)}}.
           \end{equation*}

           
           \item \points{20} Describe a polynomial time algorithm that
           given a graph $\Graph$, which is $3$-colorable, it computes
           a coloring of $\Graph$ using, say, at most $O( \sqrt{n})$
           colors, where $n$ is the number of vertices in $\Graph$.

           Hint: First color the low degree vertices in the graph. If
           a vertex has a high degree, then use (C).
           

           \item \points{20} (Harder.) Describe a polynomial time
           algorithm that given a graph $\Graph$, which is
           $k$-colorable, it computes a coloring of $\Graph$ using,
           say, at most $O( n^{1-2^{-(k-2)}})$ colors. Here $k$ is a
           small \textbf{constant}. What is roughly the running time
           of your algorithm.

           
       \end{questions}          
              

    

    \item \HWProblem{100}{Greedy algorithm does not work for TSP with
       the triangle inequality.}{
    
       In the greedy Traveling Salesman algorithm, the algorithm
       starts from a starting vertex $v_1 = s$, and in $i$\th stage,
       it goes to the closest vertex to $v_i$ that was not visited
       yet.

    \begin{questions}
        \item \points{20} Show an example that prove that the
        greedy traveling salesman does not provide any
        constant factor approximation to the TSP.
        
        Formally, for any constant $c >0$, provide a
        complete graph $G$ and positive weights on its
        edges, such that the length of the greedy TSP
        is by a factor of (at least) $c$ longer than the
        length of the shortest TSP of $G$. 

        \item \points{80} Show an example, that prove that the greedy
        traveling salesman does not provide any constant factor
        approximation to the TSP with \emph{triangle inequality}.
                
        Formally, for any constant $c >0$, provide a complete graph
        $G$, and positive weights on its edges, such that the weights
        obey the triangle inequality, and the length of the greedy TSP
        is by a factor of (at least) $c$ longer than the length of the
        shortest TSP of $G$.  (In particular, \emph{prove} that the
        triangle inequality holds for the weights you assign to the
        edges of $G$.)
    \end{questions}%
 }{}

 \item \HWProblem{100}{Maximum Clique}%
 {%
    The max-clique problem has the property that given a low quality
    approximation algorithm, one can get a better quality
    approximation algorithm -- this question describe this
    amplification behavior.
    
    Let $\Graph=(V,E)$ be an undirected graph. For any $k \geq 1$, define
    $\Graph^{(k)}$ to be the undirected graph $(V^{(k)},E^{(k)})$, where
    $V^{(k)}$ is the set of all ordered $k$-tuples of vertices from
    $V$ and $E^{(k)}$ is defined so that $(v_1,v_2,...,v_k)$ is
    adjacent to $(w_1,w_2,...,w_k)$ if and only if for each $i$
    ($1 \leq i \leq k$) either vertex $v_i$ is adjacent to $w_i$ in
    $\Graph$, or else $v_i=w_i$.
    
    \begin{questions}
        \item \points{50} Prove that the size of the maximum clique in
        $G^{(k)}$ is equal to the $k$\th power of the size of the
        maximum clique in $G$.
    
        \item \points{50} Argue that if there is a $c$-approximation
        algorithm for finding a maximum-size clique in a graph, for
        some constant $c>1$, then there is a polynomial time
        $\alpha$-approximation algorithm for max-clique, where
        $\alpha = (c+1)/2$.

        (Hint: Use the first part.)
    \end{questions}
}{}

\end{questions}

\end{document}

