\documentclass{ctwart}

\usepackage{amssymb,amsmath}
\usepackage{algpseudocode}
\usepackage[boxed]{algorithm}

\newcommand{\E}[1]{\operatorname{E}[#1]}
\newcommand{\bigE}[1]{\operatorname{E}\bigl[#1\bigr]}
\newcommand{\BigE}[1]{\operatorname{E}\left[#1\right]}

\newcommand{\nat}{\mathbb{N}}
\newcommand{\real}{\mathbb{R}}

\newcommand{\C}[1]{\mathcal{#1}}

\newcommand{\tr}{^{\mathrm{T}}}
\newcommand{\rntn}{\real^{n \times n}}
\DeclareMathOperator{\trace}{tr}
\newcommand{\trc}[1]{\trace(#1)}

\DeclareMathOperator{\gis}{gis}
\newcommand{\NP}{\textsf{NP}}
\newcommand{\DP}{\textsf{P}}

\newcommand{\greedy}{\texttt{GreedyIS}}
\newcommand{\indapx}{\texttt{ApproxIS}}

\newcommand{\indset}{\textsf{IS}}
\newcommand{\color}{\textsf{COL}}
\newcommand{\eps}{\varepsilon}

\begin{document}
\setcounter{page}{119}
\begin{frontmatter}

\title{Approximating Independent Set in Semi-Random Graphs} 

\author[B]{Bodo Manthey}
\ead{b.manthey@utwente.nl}
\author[K]{Kai Plociennik}
\ead{kai.plociennik@informatik.tu-chemnitz.de}

\address[B]{University of Twente, Department of Applied Mathematics
   P.~O.~Box~217,~7500~AE~Enschede, The Netherlands}
\address[K]{TU Chemnitz, Fakult\"at f\"ur Informatik Stra{\ss}e~der~Nationen~62,~09107~Chemnitz,~Germany}



\begin{abstract}
We present an algorithm for the independent set problem on semi-random graphs,
which are generated as follows: An adversary
chooses an $n$-vertex graph, and then each edge is flipped independently with a
probability of $\eps > 0$.
Our algorithm runs in expected polynomial time 
and guarantees an approximation ratio of roughly $O(\sqrt{n\eps})$,
which beats the inapproximability bounds.
\end{abstract}

\end{frontmatter}


\section{Introduction and Our Results}

Given an undirected graph $G=(V,E)$, the goal of the maximum
independent set problem (\indset) is to find
an \emph{independent set}
$I \subseteq V$ (i.e., no edge of $E$ connects two vertices of $I$) of
maximum cardinality. The size of the largest such set is $G$'s
\emph{independence number} $\alpha(G)$.
\indset\ is \NP-hard and even hard to approximate
with a ratio of $O(n^{1-\delta})$ for every
$\delta > 0$, where $n$ is the number
of vertices~\cite{Zuckerman}. The best worst-case polynomial-time approximation algorithm for \indset\ achieves
an approximation ratio of $O(n \frac{(\log \log n)^2}{(\log n)^3})$~\cite{Feige}.
Often, however, approximation algorithms show a better performance
than their worst-case guarantees promise. To explain the gap between
worst-case and observed approximability, the average-case
approximability of \indset\ with respect to random graphs in the $G(n,p)$ model has been analyzed by
Krivelevich and Vu~\cite{KrivelevichVu}. They achieve an approximation
ratio of $O(\sqrt{np} / \log n)$ in expected polynomial time.
A drawback of such an average-case analysis is that it often says little about
typical performance: random instances have
very special properties with high probability and often do not reflect real
instances. To circumvent this,
graph problems have been analyzed with
semi-random inputs~\cite{CojaOghlan:Finding,FeigeKilian:Semirandom:2001}.

In this paper, we analyze the approximability of
\indset\ for a semi-random input model:
An adversary specifies a graph $G=(V,E)$. Then, a random graph $\C{G}=(V,\C{E})$ is produced by
flipping each potential edge in $G$ independently with a probability of $\eps>0$. More
precisely, for every $e \in E$, we have $e \in \C E$ with a probability of $p_e = 1-\eps$, while for every $e \notin E$,
we have $e \in \C E$ with a probability of $p_e = \eps$.
We call this distribution $\C{G}(G, \eps)$.
In the extreme case $\eps = 0$, the adversary has full power and
we have $\C G = G$. For larger values of $\eps$,
the adversary loses power.
We adapt the algorithm of Krivelevich and Vu~\cite{KrivelevichVu}
to our semi-random model and show that it guarantees an approximation
ratio of roughly $O(\sqrt{n\eps})$ in expected polynomial time.



\section{Approximating Independent Set}






For simplicity, we always assume $V=\{1,\ldots ,n\}$ from now on.
\greedy\ (Algorithm~\ref{fig:alggreedy})
is a simple greedy algorithm, which outputs
an independent set.
\greedy\ is later used as a subroutine of
\indapx.

\begin{algorithm}[t]
\begin{algorithmic}[1]
\item[] $\greedy(G)$
%
\State Set $C_1 := \{1\}$ and $\chi := 1$.
%
\State For $v=2,\ldots ,n$: If there is an $i$ such that $C_i \cup \{v\}$ is an
independent set of $G$,
then $C_i := C_i \cup \{v\}$ for the smallest such $i$. Otherwise, create a new class
by setting $\chi := \chi + 1$ and $C_{\chi} := \{v\}$.
%
\State Choose $i$ that maximizes $|C_i|$. Output $I = C_i$.
\end{algorithmic}
\caption{A simple greedy algorithm for independent set.}
\label{fig:alggreedy}
\end{algorithm}

%--- Lemma |big(C)| ------------------------

\begin{lem}
\label{lem:greedycolsize2}
%
Let $G=(V,E)$ be a graph, and let $\eps$ be arbitrary
with $n^{-1/2} \leq \eps \leq 1/2$. Let
$\gis(G,\eps) = \frac{1}{32} \cdot \min \{\frac{\ln n}\eps, \frac{n^2 \ln n}{|E| \ln (1/\eps)}\}$.
Let $I$ be the independent set of $\C G$ computed by \greedy, where $\C G$ is drawn from
$\C G(G, \eps)$.
Then $\Pr[|I| < \gis(G,\eps)] \leq e^{-n \ln n}$.
\end{lem}



We also need an upper bound on the independence number of a graph
drawn from $\C{G}(G, \eps)$.
The proof is an adaption of Krivelevich and Vu's technique~\cite{KrivelevichVu} to our
semi-random model. For a graph $G$ and a random graph $\C{G}=(V,\C{E})$ drawn from $\C{G}(G,\eps)$, let
$A=A(\C{G},G,\eps) = (a_{ij})_{1 \leq i,j \leq n}$
be the $n \times n$-matrix given by
$a_{ij} = 1$ if $e=\{i,j\} \not \in \C{E}$ and
$a_{ij} = -(1-p_e)/p_e$ if $e=\{i,j\} \in \C{E}$,
%
where $p_e = \eps$ if $e \notin E$ and
$p_e = 1-\eps$ if $e \in E$.
Note that $A$ depends on $G$ since $G$ defines the values $p_e$.
>From the results of Krivelevich and Vu~\cite[Lemma 2.4]{KrivelevichVu},
we easily get 
$\alpha(\C{G}) \leq \lambda_1(A(\C{G},G,\eps))$
for any $G$, $\eps$, and $\C G$, where $\lambda_1$ denotes the largest eigenvalue of a matrix.
We have to show that $\lambda_1(A(\C G, G, \eps)) = O((\log n)\cdot \sqrt{n/\eps})$
with high probability.
Krivelevich and Vu's proof~\cite{KrivelevichVu} of the corresponding result for
$G(n,p)$ graphs is based on a concentration result for the largest eigenvalue of a matrix.
To apply their techniques, we first have to determine the expected value $\E{\lambda_1(A)}$
of the largest eigenvalue (Lemma~\ref{lem:exp_lambda1}).
Using this, we can derive a tail bound for $\lambda_1(A)$ (Lemma~\ref{lem:tailbound_lambda1}).
Together with $\alpha(\C{G}) \leq \lambda_1(A)$,
we then get a concentration result for the size of the largest
independent set in $\C{G}(G, \eps)$ graphs (Theorem~\ref{thm:concentration}).


\begin{lem}\label{lem:exp_lambda1}
%
Fix a graph $G=(V,E)$, and let $\eps = \Omega((\log n)^2/n)$, $\eps \leq 1/2$.
Let $A=A(\C{G},G,\eps)$ for
$\C{G}$ drawn from $\C{G}(G,\eps)$. Then
$\E{\lambda_1(A)} \leq 2^7 (\log n) \sqrt{n/\eps}$.
%
\end{lem}


\begin{lem}\label{lem:tailbound_lambda1}
%
Under the same assumptions as in Lemma~\ref{lem:exp_lambda1}, we have
$\Pr[\lambda_1(A) \geq 2^8 (\log n)  \sqrt{n/\eps}]
\leq 4 \exp(-2^9 n\eps (\log n)^2)$.
%
\end{lem}



\begin{thm}
\label{thm:concentration}
%
Fix a graph $G=(V,E)$, and let $\eps = \Omega((\log n)^2/n)$, $\eps \leq 1/2$.
Let $\C{G}$ be a random graph drawn from $\C{G}(G,\eps)$. Then
$\E{\alpha(\C{G})} \leq 2^7\cdot (\log n)\cdot \sqrt{n/\eps}$ and
$\Pr[\alpha(\C{G}) \geq 2^8\cdot (\log n)\cdot \sqrt{n/\eps}] \leq 4\exp(-2^9\cdot n\eps \cdot (\log n)^2)$. 
%
\end{thm}


Our algorithm \indapx\ (Algorithm~\ref{alg:approx})
gets the adversarial graph $G$, the
flip probability $\eps$, and the random graph
$\C{G}$ from $\C{G}(G,\eps)$ as input.
It runs \greedy\ and tries to certify that
this yields a good approximation. If this fails, \indapx\
turns to brute-force search.
Let us briefly discuss the influence of $G$.
With decreasing $\eps$ and increasing
$|E|$, the graph $G$ gains influence.
This is reflected in the approximation ratio below. In Step~3, the following definition is used:
For a graph $G=(V,E)$ and $S \subseteq V$, the \emph{non-neighborhood} $\overline N(S)$ of $S$ is
the set of vertices not adjacent to $S$.


\begin{algorithm}[t]
\begin{algorithmic}[1]
\item[] $\indapx(\C{G}=(V,\C{E}),G,\eps)$
%
\State $I := \greedy(\C{G})$. If $|I| < \gis(G,\eps)$, go to Step~5.
%
\State Compute $\lambda_1(A(\C{G},G,\eps))$. If $\lambda_1 < 2^8\cdot (\log n)\cdot \sqrt{n/\eps}$, then
output $I$.
%
\State Compute $|\overline{N}(S')|$ for all sets $S' \subseteq V$ with
$|S'|=(8 \log n)/\eps$. If $|\overline{N}(S')| \leq (2 \log n) \cdot \sqrt{n/\eps}$ for all such
subsets $S'$, output $I$.
%
\State Check all subsets $S'' \subseteq V$ with $|S''|=(8 \log n) \cdot \sqrt{n/\eps}$.
If none of them is independent, output $I$.
%
\State Try all subsets of $V$ and output a largest independent set found.
%
\end{algorithmic}
\caption{Approximation algorithm for independent set with guaranteed approximation ratio
and expected polynomial running-time.}
\label{alg:approx}
\end{algorithm}

\begin{thm}\label{the:indepset}
%
Fix a graph $G=(V,E)$ and a flip probability $n^{-1/2} \leq \eps \leq 1/2$.
Let $\C{G}$ be drawn from
$\C{G}(G,\eps)$. Then $\indapx(\C{G},G,\eps)$
has polynomial expected running time. If $\eps$ is sufficiently large,
i.e., $\frac{\ln(1/\eps)}{\eps} \leq \frac{n^2}{|E|}$, it
guarantees an approximation ratio of $O(\sqrt{n\eps})$. Otherwise, it guarantees
an approximation ratio of
$O\bigl( \frac{|E|\log(1/\eps)}{n^{3/2} \sqrt{\eps}} \bigr)$.
%
\end{thm}


\greedy\ alone is an algorithm with worst-case polynomial running-time, but the
approximation ratio then holds only in expectation and with high
probability. This complements the performance of \indapx.
The analysis follows from Lemma~\ref{lem:greedycolsize2} and Theorem~\ref{thm:concentration}.

\begin{cor}
\label{cor:greedyratio}
Let $G=(V,E)$ be a graph, and let
$n^{-1/2} \leq \eps \leq 1/2$. Then
\greedy\ achieves an expected approximation ratio of
$O\bigl(\frac{\sqrt{n/\eps}}{\min \{1/\eps, n^2/(|E| \ln (1/\eps))
\}}\bigr)$
on graphs drawn from $\C G(G,\eps)$.
If $\frac{\ln(1/\eps)}{\eps} \leq \frac{n^2}{|E|}$, i.e., $\eps$ is large enough,
this simplifies to $O(\sqrt{n\eps})$.
The approximation ratio is not only achieved in expectation, but also with
a probability of at least $1 - \exp(-\Omega(n\eps (\log n)^2))$.
%
\end{cor}


\section{Discussion}
\label{sec:conclusions}

We have analyzed the approximability of \indset\ in a semi-random input
model.
We have presented an approximation algorithm that guarantees
an approximation ratio of roughly $O(\sqrt{n\eps})$ in expected polynomial time.
A simple greedy algorithm (Algorithm~\ref{fig:alggreedy})
alone achieves an expected
approximation ratio of $O(\sqrt{n\eps})$ in worst-case polynomial time.
A subtlety of our Algorithm~\ref{alg:approx}
is that it needs the original graph
as an additional input.
We believe that avoiding this requires new techniques
if it can be avoided at all. The reason is that our goal was a
\emph{guaranteed approximation ratio}. To achieve this, the algorithm has to know
when to switch to brute-force search in order to maintain
also an expected polynomial running-time.
\greedy\ alone, which needs
neither the original graph nor $\eps$,
has complementary
properties: worst-case polynomial running-time but the
approximation ratio is only achieved in expectation.


\begin{thebibliography}{1}

\bibitem{CojaOghlan:Finding}
Amin Coja-Oghlan.
\newblock Finding large independent sets in polynomial expected time.
\newblock {\em Combin. Probab. Comput.}, 15(5):731--751, 2006.

\bibitem{Feige}
Uriel Feige.
\newblock Approximating maximum clique by removing subgraphs.
\newblock {\em SIAM J. Discrete Math.}, 18(2):219--225, 2004.

\bibitem{FeigeKilian:Semirandom:2001}
Uriel Feige and Joe Kilian.
\newblock Heuristics for semirandom graph problems.
\newblock {\em J. Comput. System Sci.}, 63(4):639--671, 2001.

\bibitem{KrivelevichVu}
Michael Krivelevich and Van~H. Vu.
\newblock Approximating the independence number and the chromatic number in
  expected polynomial time.
\newblock {\em J. Comb. Optim.}, 6(2):143--155, 2002.

\bibitem{Zuckerman}
David Zuckerman.
\newblock Linear degree extractors and the inapproximability of max clique and
  chromatic number.
\newblock {\em Theory of Computing}, 3(6):103--128, 2007.

\end{thebibliography}
%\bibliographystyle{plain}
%\bibliography{iscol}

\end{document}

