% Contact email: me@next.clarku.edu
\documentstyle{article}

\setlength{\textheight}{20cm}
\setlength{\textwidth}{14.5cm}

\setlength{\oddsidemargin}{1cm}
\setlength{\evensidemargin}{0cm}
\setlength{\topmargin}{1cm}
\setlength{\marginparwidth}{0cm}
\setlength{\marginparsep}{0cm}

\setlength{\headheight}{0cm}
\setlength{\headsep}{0cm}
\setlength{\topskip}{0cm}
\setlength{\footheight}{1cm}
\setlength{\footskip}{2cm}

\newcommand{\drawline}{\rule{4.5in}{.4mm}}
\newcommand{\vsa}{\vspace{\baselineskip}}

\newcommand{\wfch}{{\bf WFCH}}
\newcommand{\wich}{{\bf WICH}}
\newcommand{\ich}{{\bf ICH }}

\newcommand{\mwc}{{\bf MWC}}

\newtheorem{lem}{Lemma}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{defi}{Definition}[section]

\begin{document}
\title{A Weighted Fractional Coloring Heuristic
with Application to the Maximum Weight Clique
Problem\thanks{This is based on an on going joint work with Egon  
Balas}}

\author{Jue Xue\thanks{Graduate School of Management, Clark  
University, Worcester, MA 01610}}
\date{Jan. 15, 1993}
\maketitle

\begin{center}
{\bf Extended Abstract}
\end{center}
\begin{small}
\begin{quote}

In this work we present a heuristic for the weighted fractional  
coloring problems on arbitrary graphs. This heuristic extends our  
previous work (reported in \cite{ORSAs90}, \cite{ARIDAM90},  
\cite{Xue91}) for the unweighted case. We use this heuristic as an  
upper bounding procedure for the maximum weight clique problem.  
Computational results from our previous work for the maximum clique  
problem indicated that the bounds found by our heuristic were  
stronger than the bounds found by other relatively efficient  
heuristics in the literature. Computational comparison of: (1) the  
upper bounds from our fractional coloring heuristic with those from  
other heuristics in the literature; (2) the performance of the  
resulting branch and bound algorithm for the maximum weight clique  
problem with other such algorithms; will be presented.
\end{quote}
\end{small}


\section {Introduction}
Let $G = (V,E)$ be an arbitrary, undirected graph. The {\em  
complement graph} $\overline{G} = (V,\overline{E})$ of $G$ is the  
graph with vertex set $V$ and edge set $\overline{E} = \{(i,j) \, |  
\, (i,j) \notin E \}. \; G$ is {\em weighted} if a nonnegative  
integer $w(v)$ is associated with every $v \in V$. For a subset $S  
\subseteq V, \; G(S) = (S,E \cap (S \times S))$ is called the {\em  
subgraph induced by $S$}, and the {\em weight of $S$} is defined by  
$w(S) = \sum_{v \in S} w(v)$.

A {\em clique} (complete subgraph) of $G$ is a set of pairwise  
adjacent vertices, and a {\em stable set} (vertex packing,  
independent set) of $G$ is a set of pairwise nonadjacent vertices.  
$S$ is a clique of $G$ if and only if $S$ is a stable set of  
$\overline{G}$. The {\em maximum weight clique/stable set problem}  
asks for a clique/stable set of maximum weight. A recent survey on  
the above problem can be found in \cite{PaXu93}.

A {\em weighted coloring} $(y, {\cal S})$ of $G$ is a collection:  
${\cal S} = \{S_1,\ldots,S_p\}$ of stable sets (also called {\em  
color classes}) together with their nonnegative integer weights  
$y_{S_i}$, such that
\begin{equation}
\sum_{S_i \ni v, \, S_i \in {\cal S}} y_{S_i} \geq w(v), \; \forall v  
\in V.
      \label{wclr}
\end{equation}
The {\em weight of} $(y, {\cal S})$ is defined by $w(y,{\cal S})  
=\sum_{S_i \in {\cal S}} y_{S_i}$ (also denoted by $w(\cal S)$). In a  
weighted coloring, a vertex can belong to more than one
color class.

A {\em weighted fractional coloring} is a weighted coloring $(y,{\cal  
S})$ where the weights $y_{S_i}$ can be any nonnegative reals. A {\em  
weighted (fractional) clique covering} $(y, {\cal C})$ of $G$ is a  
weighted (fractional) coloring of $\overline{G}$ (and vise versa).  
The {\em minimum weighted (fractional) coloring/clique covering  
problem} asks for a weighted (fractional) coloring/clique covering  
that has the minimum weight.

In the special case when all weights $w(v) = 1, \; \forall v \in V$,  
we have the {\em unweighted} version of the above problems. They are  
called the {\em maximum clique/stable set problem}, and the {\em  
minimum (fractional) coloring/clique covering problem}, respectively.  
All above problems, weighted or unweighted, are NP-complete on  
arbitrary graphs (\cite{GaJo79}, \cite{GrLoSc89}).

In this work, we present a heuristic for the weighted fractional  
coloring problem on arbitrary graphs. It extends our previous work  
(reported in \cite{ORSAs90}, \cite{ARIDAM90}, \cite{Xue91}) for the  
unweighted case. The heuristic can be used as an upper bounding  
procedure for the maximum weight clique problem. Our previous  
computational results on graphs of $100$ to $1000$ vertices were  
reported along with the method used, at the May 7-9, 1990 TIMS/ORSA  
Joint National Meeting in Las Vegas (\cite{ORSAs90}) and at the  
May-June, 1990 ARIDAM V meeting at RUTCOR (\cite{ARIDAM90}), as well  
as in \cite{Xue91}. They show that: (1) the bound found by our  
heuristic is stronger than the bounds found by some relatively  
efficient heuristics in the literature; (2) the  maximum clique  
algorithm that uses this heuristic as its upper bounding procedure  
generates a much smaller search tree, and is more efficient for hard  
cases of the maximum clique problem. Computational comparison for the  
weighted case will be provided at the conclusion of this project.

This work is organized as follows. In Section 2, we review the  
formulations of the maximum weight clique, minimum weighted coloring  
and fractional coloring problems. We discuss the relationships of  
these problems and the advantages of our approach. In Section 3, we  
present our weighted fractional coloring heuristic and its  
complexity. In Section 4, we present a branch and bound algorithm  
that uses this heuristic as its upper bounding procedure. Section 5  
contains our computational experience with the proposed methods. All  
proofs are omitted here.

\section {Formulation of the Problems}

Let ${\cal S}$ denote the set of all stable sets of graph $G$. Let  
$A_{\cal S}$ denote the stable set-vertex incidence matrix of $G$.  
The maximum weight clique, minimum weighted coloring and fractional  
coloring problems can be formulated as follows.

\noindent {\em The maximum weight clique problem} (\mwc):
\begin{equation}
z_1 = 
\mbox{max} \{ w x \, | \, A_{\cal S} x \leq 1, \, x_j \in \{0,1\}\}.
	\label{mclq}
\end{equation}

\noindent {\em The minimum weighted coloring problem:}
\begin{equation}
z_2 = \mbox{min} \{ y1 \, | \, y A_{\cal S} \geq w, \, y_S \;
      \mbox{integer}, \forall S \in {\cal S}\}.
    \label{micp}
\end{equation}

\noindent {\em The minimum weighted fractional coloring problem:}
\begin{equation}
z_3 = min\{y1 \, | \, y A_{\cal S} \geq w, \, y_S \geq 0, \,
         \forall S \in {\cal S}\}.
      \label{mfcp}
\end{equation}

The LP relaxation of (\ref{micp}) is (\ref{mfcp})and $z_1 \leq z_2  
\leq z_3$ holds for any graph $G$. Therefore, any feasible solution  
of (\ref{micp}) or (\ref{mfcp}) gives an upper bound to \mwc.

In the literature, there are many heuristics for the minimum coloring  
problem (\cite{Bre79},\cite{Dun75}, \cite{Lei79}, \cite{MaMaIs72},  
\cite{WePo67}). Several relatively efficient branch and bound  
algorithms for the maximum clique problem have used these heuristics  
as their upper bounding procedures to reduce the size of the search  
tree (\cite{BaYu86},\cite{BaTi90}). Intuitively, the upper bound from  
a heuristic for problem (\ref{mfcp}) will be tighter than the upper  
bound from heuristics for problem (\ref{micp}).

\section {Weighted Fractional Coloring Heuristic}

Our weighted fractional coloring heuristic (\wfch) applies a weighted  
integer coloring heuristic (\wich) repeatedly to a sequence of  
subgraphs $G_j \subseteq G, \, j = 1,2,\ldots,K$ ($G_1 = G$). Each  
subgraph $G_j$ is defined according to the results from all previous  
\wich. Here $K$ is the last iteration before \wfch \, stops.

Let $(y^{*}, {\cal S}^{*})$ be our \wfch \, solution to (\ref{mfcp})  
with weight $z^{*} = w({\cal S}^{*})$. Initially, we set
 ${\cal S}^{*} = \emptyset, \, z^{*} = \infty, \; y^{*}_S = 0, \;
	\forall S \in {\cal S}$.
During \wfch, color classes are generated (or expanded) together  
their weights so that condition

\begin{equation}
\sum_{S \ni v, \, S \in {\cal S}^{*}} y^{*}_S \geq k * w(v), \;
	\forall v \in V
     \label{wkcol}
\end{equation}

\noindent holds at the end of all iteration $k < K$. Then, at the end  
of iteration $K$, we modify $(y^{*}, {\cal S}^{*})$ to obtain a  
feasible solution to (\ref{mfcp}).

\begin{defi}
(for an iteration $k$):

The residue weights of $v \in V$ is
\[ resw(v) = k*w(v) - \sum_{S \ni v, \, S \in {\cal S}^{*}} y^{*}_S,  
\; \forall v \in V. \]

A vertex $v \in V$ is colored if $resw(v) \leq 0$. Else, $v$ is not  
colored.

A color class $S \in {\cal S}^{*}$ is maximal if $\forall$ uncolored  
vertex $v \notin S$, $S \cup \{v\}$ is not a stable set. Else, $S$ is  
not maximal.
	\label{def31}
\end{defi}

For any iteration, (\ref{wkcol}) holds if and only if all vertices  
are colored. In \wfch, ${\cal S}^{*}$ is allowed to have multiple  
copies of a color class $S$, and each copy may have a different  
weight $y^{*}_S$.

\vsa
\noindent {\bf Weighted Fractional Coloring Heuristic} (\wfch)

\noindent {\bf Step 0}. ({\em Initialization})

Set $z^{*} = \infty, \; y^{*} = 0$, and ${\cal S}^{*} = \emptyset$,

iteration counter $k = 1$, and $resw(v) = 0, \; \forall v \in V$.

\noindent {\bf Step 1}. ({\em at iterative $k$})

\noindent {\bf Step 1.1}. Set $resw(v) = resw(v) + w(v), \;
	\forall v \in V$.

\noindent {\bf Step 1.2}. Let $U_k = \{v \, | \, resw(v) > 0\}$.
Scan each uncolored vertex $v \in U_k$:

If $\exists S \in {\cal S}^{*}$, such that $v \notin S$, and
$S \cup \{v\}$ is a stable.

\hspace{0.2in} Set $resw(v) = resw(v) - y^{*}_S$, and
$S = S \cup \{v\}$.

\hspace{0.2in} Go back to  1.2.

\noindent {\bf Step 1.3}. Apply \wich \, to $G(U_k)$ (with vertex
weight $resw(v)$).

Let $(y^{k}, {\cal S}_k)$ be the solution from \wich.

\vsa
If   $\frac{w({\cal S}^{*})+w({\cal S}_k)}{k} \leq z^{*},$ set:
\[ z^{*} = \frac{w({\cal S}^{*}) + w({\cal S}_k)}{k}; \]
\[ y^{*}_S = \left \{ \begin{array}{ll}
	y^{*}_S, & \mbox{if $S \in {\cal S}^{*}$} \\
	y^{k}_S, & \mbox{if $S \in {\cal S}_k$}   \\
	0,        & \mbox{else}
                     \end{array}
             \right.;\]
\[ {\cal S}^{*} = {\cal S}^{*} \cup {\cal S}_k; \]
\[ resw(v) = resw(v) - \sum_{S \ni v, \, S \in {\cal S}_k} y^{k}_S,
	\; \forall v \in V; \]
\[ k = k + 1, \; \mbox{and go to Step 1.1.} \]

Else, set
\[ y^{*}_S = \frac{y^{*}_S}{k-1}, \; \forall S \in {\cal S}^{*}.\]

\hspace{0.2in} Stop. $(y^{*}, {\cal S}^{*})$ is our solution with
objective value $z^{*} = w({\cal S}^{*})$.

\vsa
\begin{prop}
\wfch \, finds a feasible solution $(y^{*}, {\cal S}^{*})$ to problem  
$(\ref{mfcp})$.
       \label{prop1}
\end{prop}

If our interest is to get an upper bound, we can round down $z^{*}$,  
i.e. $\lfloor z^{*} \rfloor$.

\begin{thm}
The total complexity for checking the maximality of a color class $S$  
is bounded by $O(min \{|E|, n \alpha(G) \})$.
\label{thm1}
\end{thm}

>From theorem \ref{thm1}, the total complexity of Step 1.2 is $O(|E| *  
|{\cal S}|)$. Let $O(h)$ be the complexity of \wich. The total  
complexity for Step 1.3 is $O(h * K)$. Thus, the total complexity is  
$O(|E| * |{\cal S}^{*}| + h*K)$. In our implementation we set a limit  
$O(|V|)$ on both $|{\cal S}^{*}|$ and $K$. Therefore, the complexity  
of \wfch \, is $O(|E| * (h + |V|)$. Our computational results will  
illustrate how $|{\cal S}^{*}|, \; K$ typically will be.

When graph $G$ is unweighted, heuristic for integer coloring with  
complexity $O(|E|)$ is available (\cite{BaYu86}). Thus, the   
complexity of \wfch \, for the unweighted case can be $O(|E|*|V|)$.

\section{Algorithm for the Maximum Clique Problem}

In this section, we propose a branch and bound algorithm for the  
maximum weight clique problem that uses \wfch \, as its upper  
bounding procedure.

The proposed algorithm has the same structure as that of Balas and  
Xue \cite{BaXu91}. Let $LB$ denote the current best lower bound we  
have (initially, $LB = 0$). At the root of the search tree ($G  
=(V,E)$), we find an edge-maximal triangulated subgraph  
(\cite{Bal86}, \cite{Xue91}) $F \subseteq G$, and a maximum weight  
clique $C^{*}$ of $F$. $w(C^{*})$ provides a lower bound on the  
maximum weight clique of $G$. Then we apply \wfch \, to $G$ to find  
an upper bound $UB_G$ on the maximum weight clique of $G$. If $UB_G  
\leq LB$, we are done.

Otherwise, we use the \wich \, solution from the first iteration of  
\wfch \, to start branching. Namely, at the end of the first  
iteration of \wfch, find a maximal subset ${\cal S}' \subseteq {\cal  
S}_1$ such that $w({\cal S}') \leq LB$. Let $V_1$ be the set of  
vertices {\em fully colored by} ${\cal S}'$, i.e.
\begin{equation}
V_1 = \{ v \, |\, \sum_{S \ni v, \, S \in {\cal S}'} y_S \geq w(v)\}.
	\label{beqn}
\end{equation}
\noindent Let $V_2 = V \setminus V_1$ be the rest vertices. Then we
have:
\begin{thm}
$LB$ is an upper bound on the maximum weight clique of $G(V_1)$.
       \label{thm41}
\end{thm}

\vsa
>From theorem \ref{thm41}, every clique of $G$ larger than $LB$  
contains at least one vertex  from $V_2$. So for every $v \in V_2$,  
we create a descendent and put it into the list {\em L} of {\em  
active subproblems}. Each subproblem $P' \in L$ is denoted by a  
triple $P' = (G',I',UB_{G'})$, where $I'$ is the set of vertices  
included in every maximal clique from $P'$, $G' = G(V')$ where $V'$  
is defined in the algorithm, and $UB_{G'}$ is an upper bound on the  
maximum weight clique of $G'$. In particular, let  $V_2 =  
(v_1,\ldots,v_k)$, the descendants from the root node are $(G(N(v_i)  
\setminus \{v_1,\ldots,v_{i-1} \}),\{v_i\},UB_G - w(v_i)), \; \forall  
v_i \in V_2$.

Let $C^{*}$ and $LB$ denote the current best clique and its weight  
$w(C^{*})$. Let $UB_G$ be an upper bound on the maximum weight clique  
of $G$. Our branch and bound algorithm is as follows.

\vsa
\noindent {\bf Maximum Weight Clique Algorithm}

\noindent 0. Find an edge-maximal triangulated subgraph $F \subseteq  
G$ (see \cite{Bal86}, \cite{Xue91}).

Find a maximum weight clique $C^{*}$ of $F$.

Set $LB = w(C^{*}), \; L = \{(G,\emptyset,+ \infty)\}$ and go to 1.

\noindent 1. If $L = \emptyset$, stop. $C^{*}$ is a maximum weight  
clique of $G$ with $w(C^{*}) = LB$.

Else, remove problem $P' = (G',I',UB_{G'})$ from $L$. Set $L = L  
\setminus P'$.

\hspace{0.2in} If $UB_{G'} + w(I') \leq LB$, go to 1.

\noindent 2. Use a heuristic to find a maximal clique $C' \subseteq  
G'$.

If $w(C') + w(I') > LB$, set $C^{*} = C' \cup I', \; LB = w(C^{*})$.

\noindent 3. Apply \wfch \, to $G'$ to update upper bound $UB_{G'}$.

If $UB_{G'} + w(I') \leq LB, \; \mbox{go back to } 1.$

Else, find a maximal subset ${\cal S}' \subseteq {\cal S}_1, \;
	w({\cal S}') \leq LB - w(I')$.

\hspace{0.2in} Let $V_1' = \{v \in V' \, | \, v \; fully \; colored  
\;
	by \; {\cal S}' \}$, and $V_2' = V' \setminus V_1' =  
(v_1,\ldots,v_k)$.

\hspace{0.2in} $\forall v_i \in V_2'$, if $w(N(v_i) \setminus  
\{v_1,\ldots,v_{i-1} \}) > LB - w(I') - w(v_i)$,

\hspace{0.4in}add $(G'(N(v_i) \setminus \{v_1,\ldots,v_{i-1} \}),I'  
\cup
	\{v_i\},UB_{G'}-w(v_i)) \mbox{ into } L.$

\hspace{0.2in} Go back to 1.

\vsa
The main difference between our branch and bound algorithm and that  
of \cite{BaXu91} and \cite{BaYu86} are their upper bounding  
procedures. Our upper bounding procedure is more sophisticated and  
generates a tighter upper bound for the maximum weight clique problem  
(\cite{ORSAs90}, \cite{ARIDAM90}, \cite{Xue91}). Therefore, we would  
expect a smaller search tree. On the other hand, since our upper  
bounding procedure is more complicated, we spend more time at each  
node of the search tree. The interesting question is whether the  
decreasing of the search tree justifies the increasing complexity at  
each node.

\section{Computational Results}
This section provides the computational results of the above methods  
on various kinds of graphs as well as their comparison with some  
existing algorithms.

\begin{thebibliography}{10}
\bibitem{BaTi90}
L.~Babel and G.~Tinhofer,
\newblock A Branch and Bound Algorithm for the Maximum Clique
Problem,
\newblock {\em ZOR-Methods and Models of Operations Research}, 34: 

207-217, 1990.
\bibitem{Bal86}
E.~Balas,
\newblock A Fast Algorithm for Finding an Edge-maximal Subgraph with
a TR-formative Coloring,
\newblock {\em Discrete Applied Mathematics}, 15:123-134, 1986.

\bibitem{ORSAs90}
E.~Balas and J.~Xue,
\newblock Fast Maximum Clique Algoirthms,
\newblock {\em TIMS/ORSA Joint National Meeting}, Las Vegas, May 7-9,  
1990.

\bibitem{BaXu91}
E.~Balas and J.~Xue,
\newblock Minimum Weighted Coloring of Triangulated Graphs, with 

Application to Maximum Weight Vertex Packing and Clique Finding in 

Arbitrary Graphs,
\newblock {\em SIAM J. Comput.} Vol. 20, No. 2: 209-221, 1991.

\bibitem{BaYu86}
E.~Balas and C.S.~Yu,
\newblock Finding a Maximum Clique in an Arbitrary Graph,
\newblock {\em SIAM J. Computing}, 14, No. 4: 1054-1068, 1986.

\bibitem{Bre79}
D.~Brelaz,
\newblock New Methods to Color the Vertices of a Graph,
\newblock {\em Comm. of ACM}, 22, No. 4: 251-256, 1979.

\bibitem{CaPa90}
R.~Carraghan and P.M.~Pardalos,
\newblock A Parallel Algorithm for the Maximum Weight Clique Problem,
\newblock {\em Technical Report CS-90-40}, Dept. of Computer Science,
Penn. State Univ., 1990.

\bibitem{Dun75}
F.D.J.~Dunstan,
\newblock Sequential Colorings of Graphs,
\newblock in {\em Proceedings of the 5th British Combinatorial
Conference}, 19: 456-463, 1975.

\bibitem{GaJo79}
M.~Garey, D.~Johnson
\newblock {\em Computers and Intractability},
\newblock FREEMAN, San Francisco, 1979

\bibitem{GrLoSc89}
M.~Gr\"{o}tschel, L.~Lov\'{a}sz and A.~Schrijver, 

\newblock Polynomial Algorithms for Perfect Graphs,
\newblock {\em Annals of Discrete Mathematics}, 21: 325-356, 1989.

\bibitem{Lei79}
F.T.~Leighton,
\newblock A  Graph  Coloring  Algorithm  for  Large  Scheduling
Problems,
\newblock {\em J. Res. Nat. Bur. Standards}, 84: 489-506, 1979.

\bibitem{MaMaIs72}
D.W.~Matula, G.~Marble and J.D.~Isaacson,
\newblock Graph Coloring Algorithms,
\newblock in R.C. Read (ed.) {\em Graph Theory and Computing},
Academic Press, London, 109-122, 1972.

\bibitem{PaXu93}
P.M.~Pardalos and J.~Xue,
\newblock The maximum clique problem,
\newblock To appear in the {\it Journal of Global Optimization},  
1993.

\bibitem{WePo67}
D.J.A.~Welsh and M.B.~Powell,
\newblock An Upper Bound for the Chromatic Number  of a Graph and
its Application to Timetabling Problem,
\newblock {\em Comput. J.}, 10: 85-86, 1967.

\bibitem{ARIDAM90}
J.~Xue,
\newblock Fractional Coloring Heuristic Algorithm with Application to
the Maximum Clique Problem,
\newblock {\bf ARIDAM V}, May-June, 1990,
{\em Abstracts of Talks and List of Participants}, RUTCOR,
{\em RR \# 2-90}, page 67, Rutgers University, New Jersey, May-June,  
1990.

\bibitem{Xue91}
J.~Xue,
\newblock Fast Algorithms for Vertex Packing and Related Problems,
\newblock {\em Ph.D Thesis}, GSIA, {\em Chapter 4: Heuristic for the  
Fractional
Coloring Problem with Application to the Maximum Clique Problem}, pp.  
73-98,
Carnegie Mellon University, Pittsburgh, PA 15213, 1991.

\end{thebibliography}
%
\end{document}

