\newenvironment{Pf}{\par\noindent{\bf Proof.}}{\mbox{}\hfill$\Box$}
\documentstyle[12pt,doublespace]{article}
\renewcommand{\baselinestretch}{1.1}
\topmargin= -20pt
\oddsidemargin= -12pt
\evensidemargin= -12pt
\textwidth=6.5in
\textheight=9in
\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}       
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\renewcommand{\thetheorem}{\thesection.\arabic{theorem}}
\renewcommand{\theproof}{\thesection.\arabic{proof}}
%\renewcommand{\thelemma}{\thesection.\arabic{lemma}}
%\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\newcommand{\mysection}[1]{\section{#1}\setcounter{equation}{0}
 \setcounter{theorem}{0}\setcounter{lemma}{0}
\begin{document}
%\bibliographystyle{unsrt}      %%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{abbrv}      %%%%%%%%%%%%%%%%%%%%%%%
\input{epic.sty} \input{eepic.sty}

\title{ A Linear Time 2-Approximation Algorithm\\
for the Min Clique-Complement Problem
%\footnote{ 
%This research was supported by the fund
% for the promotion of research at the Technion.}
}
 \author{Reuven Bar-Yehuda\\
 Computer Science Department\\
 Technion - IIT, Haifa  32000 Israel\\
\\
 e-mail: reuven@cs.technion.ac.il\\
 http://www.cs.technion.ac.il/$\sim$reuven}
 %http://www.cs.technion.ac.il/\~\ reuven}
\begin{spacing}{1}
 \maketitle

 \begin{abstract}

Using the Local Ratio technique, we present a linear time 2-approximation algorithm
for the Min Clique-Complement problem. The previous best result was a 
4-approximation algorithm due to Hochbaum.
 \end{abstract}

\noindent{\bf Keywords:}
Approximation Algorithm, Local Ratio, Covering
Problems, Vertex Cover, Min Clique-Complement problem.

\end{spacing}

\renewcommand{\baselinestretch}{1.1}
\section{Introduction}
 \setcounter{theorem}{0}\setcounter{lemma}{0}
 \setcounter{equation}{0}

We are given a simple graph $G$ = $(V,E)$, for each edge $e\in E$
a weight $\omega(e) \geq 0$. Define:

$\omega   (E')= \sum_{v \in V'} \omega (e)$ for $E' \subseteq E$.

A set $C \subseteq E$ is called a
{\em clique-complement cover} (or just a {\em cover}) if the set of 
edges
$E-C$ induces a complete graph. The Min Clique-Complement problem is:
given $G=(V,E)$, and for every edge $e \in E$ a weight 
$\omega(e) \geq 0$,
find a cover with a minimum total weight.
A cover $C^*$ is optimal
if $\omega(C^*) \leq \omega(C)$ for all covers $C$.
A cover $C$ is called an {\em $r$-approximate cover}, if
$\omega(C) \leq r \cdot \omega(C^*)$.

An algorithm $A$ is called an $r$-approximation algorithm if for all
instances $G,\omega$, $A$ returns an $r$-approximate cover.

While the Maximum Clique problem is known to be hard to approximate, 
as shown by Hastad \cite{Has96}, Hochboum \cite{Hoc97} has
developed a 4-approximation for the Min Clique-Complement problem. In 
this paper we further improve Hochboum's result. We observe that
2-approximation is easy to get be reduction to the Vertex Cover
Problem. Our main conribution is mainly in the time complexity.
Using the 
local-ratio technique see e.g. \cite{BarEve83}, \cite{Bar98a},
we obtain a linear time 2-approximation. In the
second section, we give the general 2-approximation algorithm. In the
third section, we show a linear time implementation.

\subsection{A 2-Approximation Algorithm}

The main idea: let $e_1$ and $e_2$ be two edges having at least two
non-neighbor endpoints, hence $e_1$ and $e_2$ cannot participate in 
the same complete subgraph. This implies that either $e_1$ or $e_2$ 
has to be eliminated, i.e., for every cover $C \subseteq E$,
$ C \cap \{e_1,e_2\} \not = \phi $.

At this point, one may suggest, to make a reduction to the Vertex
Cover Problem to get the 2-approximation desired. However, such
a reduction is time and space expansive.
%Subtracting $\epsilon$ from both 
%weights costs $\leq 2 \epsilon$, while the optimum reduction is 
%$\geq \epsilon$.

Consider the following subroutine:

\newcommand{\TABLINE}[1]{\hspace*{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\= 
\kill}

%\begin{figure}[htb]
\begin{center}
\fbox{
\begin{minipage}{8cm}
\begin{tabbing}
\TABLINE{0.5cm}
{\bf
Algorithm XXXXXXXXXXXXXXXXXXXX
}\\
YYYYYYYYYYYYYYYYYYYYYY
\noindent{\bf Subroutine Edge-Local-Ratio$(e_1,e_2,\omega)$}

001\= 002\= 003 \kill
\>Let $\epsilon = min\{\omega(e_1),\omega(e_2)\}$\\
\>$\omega(e_1) = \omega(e_1) - \epsilon$\\
\>$\omega(e_2) = \omega(e_2) - \epsilon$\\
\end{tabbing}
\end{minipage}
}
\end{center}
%\caption{\label{fig:cover-algorithm}
%\small
%Algorithm {\bf Cover}}
%\end{figure}

Two edges $e_1,e_2$ are called {\em conflicting} if $\omega(e_1)>0$
and $\omega(e_2)>0$ and they have non-neighbor endpoints. Consider the 
following general algorithm CCC1 (Clique-Complement-Cover-1):

\vspace*{0.2cm}
\noindent{\bf Algorithm CCC1$(G=(V,E),\omega)$}

\begin{tabbing}
001\= 002\= 003\= 004\= 005\= 006\= 007\= \kill
\>While $\exists$ conflicting edges $ e_1,e_2$\\
\>\>Edge-Local-Ratio$(e_1,e_2,\omega)$\\
\>{\em Clique} $= \{v|\exists_{e \in E} \ v \in e$ and $\omega(e)>0\}$\\
\>Return $C = \{e \in E | e \not \subseteq$ {\em Clique}$\}$\\
\end{tabbing}

\begin{theorem} \label{th:ccp1}
Algorithm CCC1 is a 2-approximation.
\end{theorem}

\begin{Pf}
We need to prove
\begin{description}
\item[(i)]
$C$ is a cover.
\item[(ii)]
$C$ is a 2-approximation.
\end{description}

\begin{description}
\item[(i)]
To prove that $C$ is a cover, it is sufficient to show that 
{\em Clique} induces a complete graph. Let $x,y \in $ {\em Clique}. 
Let $e_x, e_y$ be incident edges to x and y respectively, s.t. 
$\omega(x)>0$ and
$\omega(y)>0$. By the termination condition of the algorithm, we know
that $e_x$ and $e_y$ are not conflicting. This implies that $x$ and 
$y$ are neighbors. Hence every pair of vertices in {\em Clique} are 
connected. 

\item[(ii)]
----------------
The proof proceeds by induction on the number of
iterations (This number is obviously finit).
\\
{\bf Base:} 0 iterations means $\omega(C)=0$.
\\
{\bf Step:}
Define $\omega_1(e_1)=\epsilon$ $\omega_1(e_2)=\epsilon$, and
$\forall{e \notin \{e_1,e_2\}} \omega(e)=0$. Also define
$\omega_2(\cdot)=\omega(\cdot)-\omega_1(\cdot)$ .
Let $C^*$, $C_1^*$, and $C_2^*$
be optimal covers with respect to $\omega$, $\omega_1$, and $\omega_2$.

\vspace*{0.2cm}
\begin{tabular}{lll}
$\omega(C)$ & $= \omega_1(C)+\omega_2(C)$ & [by definition]\\
        &$\leq 2\cdot\omega_1(C_1^*)+2\omega_2(C_2^*)$
         & [$e_1,e_2$ conflicting pair and induction hyp.]\\
        &$\leq 2\cdot\omega_1(C^*)+2\omega_2(C^*)$
         & [$C_1^*$, and $C_2^*$ are covers of $\omega_1$ and $\omega_2$]\\
        &$\leq 2\cdot\omega(C^*)$ & [$\omega=\omega_1+\omega_2$]
\end{tabular}
\end{description}
\end{Pf}

One can easily see how to implement this in $O(|E|^2)$ time or even
in $O(|E|+|V|^2)$ time. The next section gives a linear time implementation.

\subsection{A Linear Time 2-Approximation}

In order to implement Algorithm CCC1 in linear time, consider the 
following subroutine, which receives non-adjacent vertices $x,y$, and 
applies the Edge-Local-Ratio subroutine until one of the vertices is 
attached only to zero-weight edges. The following subroutine assumes 
an incidence-list data structure for $G$.


\vspace*{0.2cm}
\noindent{\bf Subroutine Vertex-Local-Ratio$(x,y,\omega,G)$}


\begin{tabbing}
001\= 002\= 003\= 004\= 005\= 006\= 007\= \kill
\>$E_x = $ the set of non-zero-weight incident edges of $x$\\
\>$E_y = $ the set of non-zero-weight incident edges of $y$\\
\>$e_x = POP(E_x)$ ; $e_y = POP(E_y)$ ; Edge-Local-Ratio$(e_x,e_y,\omega)$\\
\>While $E_x \not = \phi$ and $E_y \not = \phi$\\
\>\>If $\omega(e_x)=0$\\
\>\>\>$e_x=POP(E_x)$\\
\>\>Else\\ 
\>\>\>$e_y=POP(E_y)$\\
\>\>Edge-Local-Ratio$(e_x,e_y,\omega)$
\end{tabbing}

We use this subroutine in the following algorithm:

\vspace*{0.2cm}
\vspace*{0.2cm}
\noindent{\bf Algorithm CCC2$(G=(V,E),\omega)$}


\begin{tabbing}
001\= 002\= 003\= 004\= 005\= 006\= 007\= \kill
\>$U = V$\\
\>While $U \not = \phi$\\
\>\>$x = POP(U)$\\
\>\>Move all neighbors of $x$ from $U$ to $U^{\prime}$\\
\>\>While $U \not = \phi$ and $\omega(E(x))>0$\\
\>\>\>$y = POP(U)$\\
\>\>\>Vertex-Local-Ratio$(x,y,\omega,G)$\\
\>\>\>If $\omega(E(x))>0$ delete $y$ from $U$\\
\>\>Move $U^{\prime}$ back to $U$\\
\end{tabbing}

\begin{theorem} \label{th:ccp2}
Algorithm CCC2 is a linear time 2-approximation algorithm.
\end{theorem}

\begin{Pf}
It is obvious that CCC2 is an implementation of CCC1, since it only reduces weights according to Subroutine Edge-Local-Ratio$(e_1,e_2,\omega)$, where $e_1,e_2$ are conflicting edges. Also, when the algorithm terminates, there are no two conflicting edges. This implies that the algorithm is a 2-approximation, by Theorem \ref{th:ccp1}. 

To see that the time complexity is $O(|E|)$, observe that all edge weight subtractions done by Edge-Local-Ratio can be charged to the edge $e$ that is ``deleted'', i.e., $\omega(e)=0$. This implies that all calls to Vertex-Local-Ratio are also ``for free''. Moving neighbors of $x$ from $U$ to $U^{\prime}$ and back costs a total of
$\sum_{v \in V}d(v) = O(|E|)$, and the rest is trivial.
\end{Pf}


\noindent{\bf Acknowledgment}\\
We would like to thank
%??? ??? for helpful discussions,
Avigail Orni and Dror Rawitz for their
careful reading and suggestions.

\renewcommand{\baselinestretch}{1.0}
\bibliography{paper}
\end{document}