% 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}