%% This LaTeX-file was created by <jl> Wed Apr  8 11:54:14 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 23 4/8/98


\section{Luby Algorithm for Maximal Independent Set}


\subsection{definitions}

\begin{enumerate}
\item \( G=(V,E) \) an undirected graph
\item \( I\subseteq V \) is an independent set if no pairs of elements in I share an edge
\item \( I \) is a maximal independent set if \( \forall w\in V-I \), \( \{w\}\cup I \) is not independent
\item \( I \) is a maximum independent set if \( \forall I' \), \( |I|\geq |I'| \). This problem is NP-hard or complete
depending on how you phrase the problem.
\end{enumerate}

\subsection{algorithms}


\subsubsection{greedy lexicographic MIS}

A maximal independent set algorithm is simple: grab the first vertex and run
through the other vertices adding them to \( I \) if possible. This algorithm is \( O(m+n) \).

This algorithm is P-complete, which means if this algorithm can be parallelized,
every other parallel algorithm can be parallelized. 


\subsubsection{randomized parallel MIS}

\( MIS(G) \)

\begin{enumerate}
\item Each vertex calculates it's own degree \( d(v) \) and tries to join \( S \) with probability
\( \frac{1}{2d(v)} \)
\item if \( v,w\in S \) and share an edge, discard the one with a smaller degree. Break ties randomly,
producing set \( I \).
\item let \( V=V-I-N(I) \) where \( N(I) \) = the neighbor vertices in \( I \) and \( E \) = \( E \) minus all edges into \( I \).
\item return \( I\cup MIS(G) \)
\end{enumerate}

\subsubsection{Yet another MIS}

\( MIS2(G) \)

\begin{enumerate}
\item Each vertex picks a random value, \( v\in [0,1] \)
\item \( v \) joins if it's value is less than the \( v's \) of it's neighbors, \( N(v) \)
\item let \( V=V-I-N(I) \) where \( N(I) \) = the neighbor vertices in \( I \) and \( E \) = \( E \) minus all edges into \( I \).
\item return \( I\cup MIS2(G) \)
\end{enumerate}
The probability of joining is \( \frac{1}{d+1} \) which is a bit more aggresive than the previous
algorithm.


\subsubsection{Analysis}

On a CRCW (concurrent read/concurrent write) architecture, steps 1 and 2 take
constant time.

Unfortunately, it isn't true that a constant proportion of the vertices are
lost each round. Instead, we can prove:


\paragraph{The expected number of edges decreases by a constant fraction each round.}


\paragraph{proof:}

\begin{itemize}
\item \( v \) is 'good' if \( \sum _{u\in N(v)}\frac{1}{2d(u)}\geq \frac{1}{6} \)
\end{itemize}
For the graph with \( n \) nodes completely connected to \( \sqrt{n} \) nodes, \( K_{n,\sqrt{n}} \), each of the \( n \)
nodes is 'bad' and the \( \sqrt{n} \) nodes are 'good'.

\begin{itemize}
\item \( e=(v,w) \) is 'good' if \( v \) or \( w \) is 'good'.
\end{itemize}

\paragraph{lemma: \protect\( P(v\in I)\geq \frac{1}{4d(v)}\protect \)}

\begin{itemize}
\item \( L(v)=\{u\in N(v)|d(u)\geq d(v)\} \)
\end{itemize}

\[
P(v\notin I|v\in S)\]



\[
\leq p(\exists u\in L(v)\bigcap S|v\in S)\]



\[
\leq \sum _{u\in L(v)}P(u\in S|v\in S)\]



\[
=\sum _{u\in L(v)}P(u\in S)\]

\[
=\sum _{u\in L(v)}\frac{1}{2*d(u)}\]

\[
\leq \sum _{u\in L(v)}\frac{1}{2*d(v)}\]

\[
\leq \frac{1}{2}\]


The lemma follows pretty imediately.


\paragraph{Lemma: \protect\( v\protect \) is good \protect\( \Rightarrow P(v\in N(I))\geq \frac{1}{36}\protect \)}


\paragraph{Lemma: at least \protect\( \frac{1}{2}\protect \) the edges are good}

In \( G \) direct all edges from low to high degree, then 


\paragraph{if \protect\( v\protect \) is 'bad' then \protect\( \leq \frac{1}{3}\protect \) of \protect\( v\protect \)'s edges are directed towards \protect\( v\protect \).}

proof by contradicition:

\( \sum _{u\in N(v)}\frac{1}{2d(u)}\geq \sum _{u\in In(v)}\frac{1}{2d(u)}\geq \frac{\frac{1}{3}d(v)}{2d(v)}\geq \frac{1}{6} \)


\paragraph{pulling it together:}

Now, we can construct a binomial tree in the graph where every leaf is 'good'.
This implies the number of good edges satisfies: \( \#bad+1\leq \#good \).


\paragraph{Lemma: expected \# of edges deleted \protect\( \geq \frac{|E|}{72}\protect \)}

\end{document}