\documentstyle [11pt]{article} \begin {document} \def\square{{\setbox0=\hbox{X}\hbox to \ht0{\vrule\hss\vbox to \ht0{ \hrule width \ht0\vfil\hrule width \ht0}\vrule}}} % ===== environments for theorems and lemmas defined here ========= \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{fact}{Fact} \newtheorem{proposition}{Proposition} \newtheorem{property}{Property} \newtheorem{corollary}{Corollary} % ===== command for proofs \newenvironment{proof} {{\bf Proof:}}{\hspace*{\fill}$\square$\par\vspace{2mm}} \newcommand{\sketch}{\par\addvspace\topsep\noindent{\bf Sketch~of~Proof\/}: \ignorespaces } \newcommand{\qed}{~$\square$\ifmmode\else\par\addvspace\topsep\fi} \title{\bf An Exact Algorithm for the Maximum \\ Cardinality Stable Set Problem \footnote{Submitted to : {\em NETWORKS}, May 1992}} \author{Carlo Mannino (mannino@iasi.rm.cnr.it)\\ Dipartimento di Statistica, Probabilit\`a e Statistica Applicata,\\ Universit\`a di Roma La Sapienza, Piazzale Aldo Moro 5, 00185 Roma. \and Antonio Sassano \\ Dipartimento di Informatica e Sistemistica, \\ Universit\`a di Roma La Sapienza, Via Buonarroti 12, 00185 Roma } \date{April 1992, IASI-CNR Report n. 334} \maketitle \begin{abstract} \vspace{1cm} \noindent We describe a new branch-and-bound algorithm for the exact solution of the maximum cardinality stable set problem. The bounding phase is based on a variation of the standard greedy algorithm for finding a colouring of a graph. Two different node-fixing heuristics are also described. Computational tests on random and structured graphs and very large graphs corresponding to "real-life" problems show that the algorithm is competitive with the fastest algorithms known so far. \end{abstract} %%%%%%% INTRODUCTION %%%%%%% \section{Introduction} \label{Se-Introd} We denote by $G=(V,E)$ an undirected graph. $V$ is the set of nodes and $E$ the set of edges. A {\it stable set} is a subset of $V$ such that no two nodes of the subset are pairwise adjacent. The cardinality of a maximum stable set of $G$ will be denoted by $\alpha(G)$. A {\it clique} is a subset of $V$ with the property that all the nodes are pairwise adjacent. A {\it clique covering} is a set of disjoint cliques whose union is equal to $V$; the cardinality of a minimum clique covering is denoted by $\theta(G)$, and since at most one node of a clique can be contained in a stable set, the relation $\theta(G) \geq \alpha (G)$ holds. The {\it complement} of $G=(V,E)$ is a graph $\bar G = (\bar V,\bar E)$ such that $\bar V = V$ and $(u,v) \in \bar E$ iff $(u,v) \notin E$. The {\it neighbourhood} $N(v)$ of $v \in V$ is the set of all nodes adjacent to $v$ in $G$. Let $W \subseteq V$. The subgraph $G_W=(W,E_W)$ {\it induced} by $W$ in $G$ is the graph obtained from $G$ by eliminating all the nodes in $V-W$ and all the edges incident with them. The {\it Maximum Stable Set Problem} (MSS) consists in finding a stable set in $G$ of maximum cardinality $\alpha(G)$. Note that if $S$ is a stable set of $G$, then $S$ is a clique of $\bar G$. So, MSS is trivially equivalent to finding a maximum cardinality clique of $\bar G$. MSS is known to be NP-hard \cite{GaJo77} for arbitrary graphs, while is polynomially solvable for special classes of graphs. This is the case of perfect graphs and t-perfect graphs \cite{GrLoSc88}, circle graphs and their complements \cite{Ga73}, circular arc graphs and their complements \cite{Ga74,GuLeLe82}, claw-free graphs \cite{Mi80}, graphs without long odd cycles \cite{HsIkNe81}. Even though there is little hope to find a polynomial time algorithm for arbitrary graphs, many efforts have been done to implement efficient algorithms for MSS. The standard approach is to use branch-and-bound, trying to obtain the best compromise between the quality of the upper bound and the time spent to compute it in each subproblem. Carraghan and Pardalos \cite{CaPa90} describe a partially enumerative algorithm, where the time spent for computing an upper bound is negligible and hence the quality of the bound is poor. More time is spent to produce a better quality bound in the works of Balas and Yu \cite{BaYu86}, of Babel and Tinhofer \cite{Ba90} \cite{BaTi90} and of Friden, Hertz and de Werra \cite{FrHeWe90}. The last algorithm is based on Tabu Search. All these algorithms (excluded \cite{FrHeWe90}) are designed for computing a maximum cardinality clique; due to the aforementioned equivalence, we will refer to them as algorithms for solving a MSS. Except for \cite{CaPa90}, they all compute upper bounds for $\alpha(G)$ by finding a clique covering $\cal C$ of $G$ and applying the relation $|{\cal C}| \geq \theta(G) \geq \alpha(G)$. A different approach based on polyhedral theory is used by Nehmauser and Sigismondi in their cutting-plane algorithm \cite{NeSi89}. The algorithm we propose is a branch-and-bound algorithm, whose main features are the following: \begin{itemize} \item A tighter approximation for $\alpha(G)$ based on an extension of the definition of clique covering. \item Two different criteria for fixing nodes "out of" or "in" the stable set. \item Extensive testing. In addition to standard testing over a class of random graphs, the algorithm has been tested on graphs arising from istances of real problems and on graphs with special structure. \end{itemize} Computational testing has shown that the algorithm favourably compares with all the other algorithms described in the literature, and, in addition, has a robust behaviour on different classes of test problems. %%%%%%% UPPER BOUND HEURISTIC %%%%%%% \section{Bounding Heuristic} \label{Se-Bounding} A clique covering is a set of cliques of $G=(V,E)$ with the property that each node of $G$ is contained in exactly one clique. We extend the definition by relaxing the last property. A {\it generalized clique covering} is a set of cliques $\cal C$ of $G$ (not necessarily disinct) such that each node is contained in one or more cliques. In the following we denote by $c_i$ the number of cliques containing node $v_i \in V$, and by $\bar c$ the smallest $c_i$, for all $i$. Clearly a clique covering is a special case of generalized clique covering, where $c_i$ is equal to one for all $i$. \begin{theorem} \label{th-c_bound} Let $G=(V,E)$ and ${\cal C} = \{K_1,\dots,K_q\}$ be a generalized clique covering of $G$. Then $\lfloor {|\cal C|}/\bar c \rfloor \geq \alpha(G)$. \end {theorem} \begin {proof} Suppose there exists a stable set $S$ such that $|S| \geq \lfloor |{\cal C}|/\bar c \rfloor + 1$. Since each node of $S$ is contained in at least $\bar c$ cliques of $\cal C$ and $|K_i \cap S| \leq 1$ for each $K_i \in {\cal C}$, it follows that $|{\cal C}| \geq \bar c |S|$. Hence $|{\cal C}|\geq\bar c(\lfloor |{\cal C}| / \bar c \rfloor + 1) > \bar c( |{\cal C}| / \bar c) = |{\cal C}|$, a contradiction. \end {proof} Notice that if $\bar c = 1$ the bound corresponds to the one obtained by a clique covering. The bounding procedure HEUTHETA generates a sequence of generalized clique covering ${\cal C}^1,\dots, {\cal C}^\Delta$ with the property that each node of $V$ is contained in exactly $t$ cliques of ${\cal C}^t$, for $t=1,\dots,\Delta$. By Theorem \ref{th-c_bound} the value of the upper bound is given by $UB=\min \lfloor {\cal C}/t \rfloor$, $t=1,\dots,\Delta$. The problem of finding a generalized clique covering is made difficult by the fact that the graph $G$ has a huge number of cliques. It follows that the crucial phase of the bounding procedure is that of generating only a promising family of cliques. This is done by HEUTHETA in the following way. At the $t$-th iteration HEUTHETA finds a set of cliques ${\cal C}^t$ such that each node is contained in exactly $t$ cliques of ${\cal C}^t$. The cliques of ${\cal C}^1$ are obtained by generating a clique covering of $G$ and this can be done by any method (greedy or sofisticated as in \cite{BaTi90,BaYu86,FrHeWe90}). The cliques of ${\cal C}^t$, for $t=2,\dots,\Delta$, are obtained by exentending cliques of ${\cal C}^{t-1}$ and by generating new cliques. This is performed in a greedy fashion by selecting in sequence the nodes $v_1,\dots,v_n$. Let ${\cal C}^t_i$ be the set of cliques generated at the $t$-th iteration after having selected the nodes $v_1,\dots,v_i$ (${\cal C}^t_0 = {\cal C}^{t-1}$). When node $v_{i+1}$ is selected, HEUTHETA checks if there exists a clique $K \in {\cal C}^t_i$ such that $K' = K \cup \{v_{i+1}\}$ is a clique of $G$. If $K$ exists then $K$ is replaced by $K'$ producing ${\cal C}^t_{i+1} = {\cal C}^t_i - \{K\} \cup \{K'\}$. Otherwise the new clique $K' = \{v_{i+1}\}$ is generated and ${\cal C}^t_{i+1}$ is set to ${\cal C}^t_i \cup \{K'\}$. The generation of cliques in the $t$-th iteration terminates when all the nodes have been scanned and ${\cal C}^t = {\cal C}^t_n$. \setlength{\unitlength}{1.20mm} \begin{center} \begin{picture}(56,56) \thicklines \label{pi-C5} \put(1,30){\twlbf 1} \put(7,30){\circle*{3}} \put(7,30){\line (1,1){20}} \put(7,30){\line (1,-4){6}} \put(47,30){\line (-1,-4){6}} \put(47,30){\line (-1,1){20}} \put(52,30){\twlbf 3} \put(47,30){\circle*{3}} \put(27,54){\twlbf 2} \put(27,49){\circle*{3}} \put(13,6){\line (1,0){28}} \put(7,5){\twlbf 5} \put(13,6){\circle*{3}} \put(47,5){\twlbf 4} \put(41,6){\circle*{3}} \put(24,0){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlbf Fig. 1 }}} \end{picture} \end{center} \begin{description} \item{\bf HEUTHETA} \begin{description} \item {\it Generate} a clique covering ${\cal C}^1$. Set $UB = |{\cal C}^1|$ \item{\it for t = 2 to $\Delta$}: \begin{description} \item {\it for $j=1$ to $|V|$} \begin{description} \item {\it Select} node $v_j$ \item {\it If} $\exists K \in {\cal C}^t_{j-1}$ such that $K \cup \{v_j\}$ is a clique of $G$ \item {\it Then Set} $K'=K \cup \{v_j\}$ and ${\cal C}^t_j = {\cal C}^t_{j-1} \cup \{K'\} - \{K\}$ \item {\it Else} {\it Set} $K'=\{v_j\}$ and ${\cal C}^t_j = {\cal C}^t_{j-1} \cup \{K'\}$ \end{description} \item ({\it end of selection of node $v_j$}) \item {\it If} $UB > \lfloor |{\cal C}^t|/t \rfloor$ {\it Then} $UB = \lfloor |{\cal C}^t|/t \rfloor$ \end{description} \item ({\it end of $t$-th iteration}) \end{description} \end{description} Consider for example the simple graph of Fig.~\ref{pi-C5} (where $\alpha(G) = 2$), and suppose $\Delta = 2$. At the first iteration the algorithm produces a clique covering ${\cal C}^1 = \{(1,2) , (3,4) , (5) \}$. This gives $UB^1 = 3$, which is indeed the best possible value for an upper bound produced by any heuristic based on clique covering. When node $1$ is selected again we have ${\cal C}^2_1 = \{(1,2) , (3,4), (5,{\bf 1}) \}$, where the clique $K_3 = (5)$ of $C^2_0=C^1$ has been replaced by $K_3'=(5,1)$. When node 2 is selected we have ${\cal C}^2_2 = \{(1,2) , (3,4), (5,{\bf 1}) , ({\bf 2}) \}$ and at the end of the second iteration we obtain ${\cal C}^2 = \{(1,2) , (3,4), (5,{\bf 1}) , ({\bf 2,3}) , ({\bf 4,5}) \}$. Every node is contained in exactly two cliques of ${\cal C}^2$. The value of $UB^2$ is $\lfloor |{\cal C}^2|/2 \rfloor = 2$ and $UB = UB^2 < UB^1$. In table~\ref{ta-var} we show the variation of the upper bound UB($\Delta$) for increasing values of $\Delta$ (the number of iterations of HEUTHETA), when HEUTHETA is applied to a graph with $40$ nodes. When $\Delta$ is small, UB($\Delta$) decreases very quickly. UB($\Delta$) decreases more slowly for higher values of $\Delta$. The limit $\alpha(G)=17$ is reached when $\Delta=22$. \begin{table} \caption{Variation of UB($\Delta$)} \label{ta-var} \begin{center} \begin{tabular}{||c|c|} \hline $\Delta$ &UB($\Delta$) \\ \hline $1$ &23 \\ $2$ &21 \\ $3$ &20 \\ $4$ &19 \\ $7$ &18 \\ $22$ &17 \\ \hline \end{tabular} \end{center} \end{table} %%%%%%% BRANCHING %%%%%%% \def\balf{{\bar \alpha}} \section{Enumeration Scheme} \label{Se-Branch} In this section we describe the structure of the enumeration scheme and some simple rules which are useful in reducing the size of the branching tree. Let $G=(V,E)$ be a graph, $V = \{v_1, \dots, v_n\}$ and let $V_i = \{ v_1, \dots, v_{i-1} \} - N(v_i)$, $i=1,\dots,n$. $G_i=(V_i,E_i)$ will then be the subgraph of $G$ induced by $V_i$ and $S^*(G)$ will denote an optimum stable set of $G$. Obviously $|S^*(G)| = \alpha(G)$. The following simple observation motivates our enumeration scheme. \begin {fact} \label{fa-br1} For any stable set $S$ of $G$, $\exists i$ such that $S \subseteq V_i \cup \{v_i\}$ and $v_i \in S$. \end {fact} Hence, any stable set $S$ can be thought as the union of $\{v_i\}$ (the node in $S$ with largest index $i$) with a stable set of $G_i$. By Fact~\ref{fa-br1} the problem of finding an optimum stable set of $G$ can be reduced to the solution of $|V|$ optimum stable set problems in the subgraphs $G_1, \dots, G_n$ induced by $V_1, \dots, V_n$. Notice that with the $i$-th subproblem we can associate a set of nodes $ I_i = \{v_i\}$ fixed in the stable set and a set $O_i = \{v_{i+1},\dots,v_n\} \cup N(v_i)$ of nodes fixed out of the stable set. Moreover, each subproblem has a smaller size than the original problem and can be solved recursively in the same fashion. In this way it is possible to generate a search tree $\cal T$, where the {\it t-th} node $P^t \in {\cal T}$ is identified by: \begin{itemize} \item a set $I^t$ of nodes fixed in the current stable set \item a set $O^t$ of nodes fixed out of the current stable set \item a graph $G^t=(V^t,E^t)$ induced in $G$ by node set $V^t=V-I^t-O^t$. \end{itemize} The subproblems recursively generated by $P^t$ will be denoted by $P^t_1,\dots, P^t_{n^t}$, $n^t = |V^t|$, where $I^t_i = \{v^t_i\} \cup I^t$ and $O^t_i = O^t \cup N^t(v^t_i) \cup \{v^t_{i+1},\dots ,v^t_{n^t}\}$, $i=1,\dots,n^t$. Hence Fact~\ref{fa-br1} provides a systematic way to explore all possible stable sets of $G$. The resulting search tree $\cal T$ has a size which grows very fast with $|V|$, becoming soon intractable. In order to limit the growth of $\cal T$, we use the following fathoming rule. Let $\hat S$ be the best stable set found so far. Let $I^t$ and $G^t$ be, respectively, the set of nodes fixed in the current stable set and the subgraph relative to subproblem $P^t$. Then there exists a stable set $S$ such that $|S| > |\hat S|$ and $I^t \subseteq S$ if and only if $\alpha(G^t) \geq |\hat S| - |I^t| + 1 = \balf^t$. In other words, $\balf^t$ is the minimum cardinality of a stable set of $G^t$ which allows to improve the current best solution. If we are able to prove, by the upper bounding heuristic, that $\alpha(G^t)<\balf^t$ then $P^t$ can be fathomed, since every stable set $S$ of $G$ which contains $I_t$ satisfies $|S| \leq |\hat S|$. Another way to limit the growth of the search tree which makes use of some additional informations produced by the bounding heuristic HEUTHETA is described by the following theorem. \begin{theorem} Let $P^t = (I^t,O^t,\balf^t) \in {\cal T}$. Let ${\cal C}^1 = \{K_1,\dots,K_p\} $ be the clique covering generated by the first iteration of HEUTHETA, with $p \geq \balf^t$. Consider $\balf^t-1$ cliques of ${\cal C}^1$, say $K_1,\dots,K_{\balf^t-1}$, and let \begin{equation} \label {eq-Wset} W = K_1 \cup \dots \cup K_{\balf^t-1}. \end {equation} Let the nodes of $V^t$ be ordered in such way that the first $|W|$ nodes coincide with $W$. Then the first $|W|$ subproblems recursively generated from $P^t$, and denoted by $P^t_1,\dots,P^t_{|W|}$, can be fathomed. \end{theorem} \begin{proof} Let $G_W = (W,E_W)$ be the subgraph induced by $W$. By definition of $W$, ${\cal C}_W=\{K_1,\dots,K_{\balf^t-1}\}$ is a clique covering of $G_W$ and then $\alpha(G_W) < \balf^t$. In other words HEUTHETA provides an upper bound for $G_W$ and for all its induced subgraphs which is less than $\balf^t$. Let $S^*(G_i^t)$ be an optimum stable set of $G_i^t$, by the ordering of the nodes of $V^t$, we have that $|\{v_i^t\} \cup S^*(G_i^t)| \leq \alpha(G_W) < \balf^t$, $i=1,\dots,|W|$ and the subproblems $P^t_1,\dots,P^t_{|W|}$ can be fathomed. \end{proof} In the following we will indicate by $P^t=(I^t,O^t,\balf^t)$ the t-th subproblem, and by $S_I$ the incumbent best solution ($\alpha_I = |S_I|$). The search tree will be represented by a list of not yet solved problems ${\cal L}$. \paragraph{Main algorithm.} \begin{description} \item[{\it Initialization.}] Set $t=0$, $G^0=G$, $I^0=O^0= \emptyset$. Find a feasible solution $S_f$ (greedy heuristic) and set $S_I = S_f$. Set $\bar \alpha^0 = \alpha_I + 1$. Add $P^0=(I^0,O^0,\balf^0)$ to the list of unsolved problems ${\cal L}$. \item[1.] If ${\cal L}$ is empty {\bf STOP}. $S_I$ is an optimum stable set. \item[2.] Extract the first problem $P^t=(I^t,O^t,\balf^t)$ from ${\cal L}$. \item[3.] Compute an upper bound $UB^t$ (HEUTHETA). If $UB^t < \balf^t$ go to 1. \item[4.] Let $W$ as in Equation (\ref{eq-Wset}). Let $V^t- W = v^t_1,\dots,v^t_q$. \item[5.] For $j = 1$ to $q$ do \begin{description} \item[5.1] Set $I^t_j = I^t \cup \{v^t_j\}$. Set $O^t_j = O^t \cup N^t(v^t_j) \cup \{v^t_{j+1},\dots,v^t_q\}$. \item[5.2] If $|I^t_j| > |S_I|$ set $S_I = I^t_j$. \item[5.3] Set $\balf^t_j = \alpha_I - |I^t_j| + 1$, $V^t_j=V-|I^t_j|-|O^t_j|$. \item[5.4] If $|V^t_j| \geq \balf^t_j$ add $P^t_j=(I^t_j,O^t_j,\balf^t_j)$ to ${\cal L}$. \end{description} \item[6.] Go to 1. \end{description} In table~\ref{ta-branch} we show the number of problems of the search tree and the corresponding CPU running times, for increasing values of $\Delta$. The algorithm is applied to a graph with $100$ nodes and density $10\%$ (where the density is the number of edges of $E$ over the number of edges in the complete graph with $V$ nodes). For small values of $\Delta$, small increments produce big decrements in the number of problems, while for larger values of $\Delta$ the table shows an opposite behaviour. Since most of the time spent by the algorithm is used by the bounding heuristic, increasing values of $\Delta$ produce proportional increments in global time, which are opposed by the reduction of the number of subproblems in the search tree. \begin{table}[bth] \caption{A graph with $100$ nodes and density $10\%$} \label{ta-branch} \begin{center} \begin{tabular}{||r|r|c|} \hline $\Delta$ &Prob &time (sec)\\ \hline $1$ &1785 &5.92 \\ $2$ &1233 &4.79 \\ $3$ &972 &4.30 \\ $4$ &833 &4.11 \\ $5$ &767 &4.10 \\ $6$ &707 &4.15 \\ $7$ &684 &4.20 \\ $8$ &660 &4.31 \\ $9$ &635 &4.47 \\ \hline \end{tabular} \end{center} \end{table} %%%%%%% FIXING %%%%%%% \def\balf{{\bar \alpha}} \section{Node Fixing} \label{Se-Fix} Node fixing is a powerful tool to limit the number of solutions which need to be explored for improving the cardinality of the current best stable set. For a given subproblem of the search tree $\bar P = (\bar I,\bar O,\balf)$, let $G=(V,E)$ be the corresponding graph. Our goal is either to find an optimum stable set $S^*$ of $G$ such that $|S^*| \geq \balf$, or to prove that $\alpha(G)<\balf$. In the first case we can update the current best solution, in the second we can fathom $\bar P$. The purpose of this section is to describe two procedures which allow us to achieve the above goal by solving a MSS problem on a graph with fewer nodes than $G$. This is obtained by fixing "in" and "out" of $S^*$ suitable subsets of $V$. In particular, we will use the concept of "simplicial node" to fix nodes "in" $S^*$ and a slight extension of the procedure HEUTHETA to fix nodes "out" of $S^*$. \paragraph{Simplicial nodes.} Let $S^*$ be an optimum stable set of $G$, and $I \subseteq S^*$. Let $W=I\cup N(I)$ and $G_W$ the subgraph induced by $V-W$. Then the following holds: \begin{fact} \label{fa-fixin} $\alpha(G) = \alpha(G_W) + |I|$ and any optimum stable set $S^*_W$ of $G_W$ is such that $S^*_W \cup I$ is an optimum stable set of $G$. \end{fact} By Fact~\ref{fa-fixin}, the original goal can be restated as follows: find an optimum stable set $S^*_W$ of $G_W$ or prove that $\alpha(G_W)<\balf-|I|$. We now describe a way to identify a set $I \subseteq V$ such that there exists an optimum stable set $S^*$ of $G$ containing $I$. A node $v$ is called {\it simplicial} if $N(v)$ is a clique. The following is a straightforward property of simplicial nodes: \begin{fact} Let $v$ be a simplicial node of $G$. Then there exists an optimum stable set $S^*$ of $G$ such that $v \in S^*$. \end{fact} Obviously, if $v \in S^*$, then for all $u \in N(v)$, $u \notin S^*$. Now, let $v_1,\dots,v_q \in V$, let $V_i=V_{i-1}-\{v_i\}-N(v_i)$ and let $G_i=(V_i,E_i)$ be the subgraph induced by $V_i$, with $V_0=V$. \begin{fact} \label{fa-seqsimp} Suppose $v_i$ simplicial in $G_{i-1}$, for $i=1,\dots,q$. Then there exists an optimum stable set $S^*$ of $G$ such that $I=\{v_1,\dots,v_q\}\subseteq S^*$. \end{fact} The following algorithm finds the set $I$ as defined in Fact~\ref{fa-seqsimp}. By $N(I)$ we denote the neighbourhood of the set $I$, that is the union of all the neighbourhoods of the nodes belonging to $I$. \begin{description} \item{\bf FIND SIMPLICIAL NODES} \begin{description} \item {\it Set} $I = W = \emptyset$. \item {\it While} $\exists v \in V-W$ such that $v$ is simplicial: \begin{description} \item {\it Set} $I=I\cup\{v\}$, $W=I\cup N(I)$. \end{description} \end{description} \end{description} \paragraph {Extending HEUTHETA.} Let $O$ be a subset of $V$ such that $O\cap S=\emptyset$ for any stable set $S$ of $G$ such that $|S|\geq\balf$, and let $G_O$ be the subgraph of $G$ induced by the set $V-O$. Since the removal of the set $O$ does not "destroy" any stable set $S$ of $G$ such that $|S|\geq\balf$, we have the following property of the graph $G_O$: \begin{fact} \label{fa-fixout} If $\alpha(G)\geq\balf$ then $\alpha(G)=\alpha(G_O)$ . \end{fact} Since $G_O$ is a subgraph of $G$, if $\alpha(G)\geq\balf$ every optimum stable set of $G_O$ is also an optimum stable set of $G$. Moreover, $\alpha(G_O)<\balf$ if and only if $\alpha(G)<\balf$. By Fact~\ref{fa-fixout}, the original goal can be restated as follows: find an optimum stable set $S^*_O$ of $G_O$ or prove that $\alpha(G_O)<\balf$. In fact, if $|S^*_O|\geq\balf$ we can update the current optimum. If conversely $\alpha(G_O)<\balf$, we have that $\alpha(G)<\balf$ and the problem $\bar P$ can be fathomed. Next Theorem is the basis for a sligth extension of the algorithm HEUTHE-TA for computing a set $O \subseteq V$ satisfying the conditions of Fact~\ref{fa-fixout}. \begin{theorem} Let $S$ be a stable set of $G=(V,E)$ such that $|S| \geq \balf$. Let $\cal C$ be a generalized clique covering of $G$, with $\bar c = \min_i c_i$. Let $v_j \in V$ and let \begin{itemize} \item ${\cal J}' = \{K|K \in {\cal C}$ such that $v_j \notin K$ and $K \cup \{v_j\}$ clique of $G \}$, and \item ${\cal J}'' = \{K|K \in {\cal C}$ such that $v_j \in K\}$. \end{itemize} If $\lfloor|{\cal C}-{\cal J}'-{\cal J}''|/\bar c\rfloor\leq\balf-2$ then $v_j \notin S$. \end{theorem} \begin{proof} Suppose $v_j \in S$ and let $W = V - \{v_j\} - N(v_j)$. Then there exists a stable set $S_W \subseteq W$ such that $S = \{v_j\} \cup S_W$ and $|S_W|\geq\balf-1$. If we denote by $G_W$ the subgraph induced by $W$, then $\alpha(G_W)\geq\balf-1$. ${\cal C}-{\cal J'}-{\cal J''}$ is a generalized clique covering of $G_W$ such that each node belonging to $W$ is contained in at least $\bar c$ cliques. In fact, the cliques of ${\cal J'}$ and $\cal J''$ contain only nodes belonging to $\{v_j\} \cup N(v_j) = V - W$. By Theorem~\ref{th-c_bound} we obtain $\alpha(G_W) \leq \lfloor|{\cal C}-{\cal J'}-{\cal J''}|/\bar c \rfloor\leq\balf-2$, a contradiction. \end{proof} We now show how to extend the algorithm HEUTHETA in order to compute the set ${\cal J'}$. In the following $\cal C$ is the family of cliques generated by HEUTHETA, $\Delta$ the number of iteration ($\bar c = \Delta$) and the set $O$ will denote the nodes fixed out of the stable set. Note that since $|{\cal J''}| = \Delta = \bar c$, we can limit the search to the set ${\cal J'}$, such that $\lfloor|{\cal C}-{\cal J'}|/\Delta\rfloor\leq\balf-1$ \begin{description} \item{\bf EXTENSION of HEUTHETA} \begin{description} \item {\it Set} $O = \emptyset$. \item {\it for} $j=1$ to $|V|$ \begin{description} \item {\it Select} node $v_j$. Let ${\cal J}' = \{K|K \in {\cal C}$ such that $v_j \notin K$ and $K \cup \{v_j\}$ clique of $G \}$. \item {\it If} $\lfloor|{\cal C}-{\cal J'}|/\Delta\rfloor\leq\balf-1$ {\it Then Set} $O = O \cup \{v_j\}$. \end{description} \item ({\it end of selection of node $v_j$}) \end{description} \end{description} \paragraph{Example.} To illustrate the last fixing procedure, consider again the graph $C_5$ of Fig.~\ref{pi-C5} (which can be thought associated with a node $\bar P$ of the search tree) and suppose $\balf = 3$ and $\Delta = 1$. For $\Delta = 1$ HEUTHETA applied to $C_5$ produces a clique covering ${\cal C}^1 = \{K_1=(1,2) , K_2=(3,4) , K_3=(5) \}$, which gives $UB = 3$. Now, if we consider node $1$ , then ${\cal J}'=\{K_3\}$, and $\lfloor|{\cal C}-{\cal J}'|/\bar c\rfloor=2\leq 3-1$ and node $1$ can be fixed out. The same applies to node $4$, and then $O = \{1,4\}$. We are now able to give the complete description of the MSS algorithm partially introduced in section~\ref{Se-Branch}, extended by the fixing procedures. \paragraph{Main Algorithm.} \begin{description} \item[{\it Initialization.}] Set $t=0$, $G^0=G$, $I^0=O^0= \emptyset$. Find a feasible solution $S_f$ (greedy heuristic) and set $S_I = S_f$. Set $\bar \alpha^0 = \alpha_I + 1$. Add $P^0=(I^0,O^0,\balf^0)$ to the list of unsolved problems ${\cal L}$. \item[1.] If ${\cal L}$ is empty {\bf STOP}. $S_I$ is an optimum stable set. \item[2.] Extract the first problem $P^t=(I^t,O^t,\balf^t)$ from ${\cal L}$. \item[3.] Compute an upper bound $UB^t$ (HEUTHETA). If $UB^t < \balf^t$ go to 1. \item[4.] Use the algorithm EXTENSION of HEUTHETA to find a set $O$ of nodes fixed "out". Set $O^t = O^t \cup O$. Set $V^t=V-I^t-O^t$. \item[5] If $|V^t| < \balf^t$ go to 1. \item[6.] Let $W$ as in Equation (\ref{eq-Wset}). Let $V^t- W = v^t_1,\dots,v^t_q$. \item[7.] For $j = 1$ to $q$ do \begin{description} \item[7.1] Set $I^t_j = I^t \cup \{v^t_j\}$. Set $O^t_j = O^t \cup N^t(v^t_j) \cup \{v^t_{j+1},\dots,v^t_q\}$. \item[7.2] Use the algorithm FIND SIMPLICIAL NODES to find a set $I$ of nodes fixed "in". Set $I^t_j = I^t_j \cup I$ and $O^t_j = O^t_j \cup N(I)$. \item[7.3] If $|I^t_j| > |S_I|$ set $S_I = I^t_j$. \item[7.4] Set $\balf^t_j = \alpha_I - |I^t_j| + 1$, $V^t_j=V-|I^t_j|-|O^t_j|$. \item[7.5] If $|V^t_j| \geq \balf^t_j$ add $P^t_j=(I^t_j,O^t_j,\balf^t_j)$ to ${\cal L}$. \end{description} \item[8.] Go to 1. \end{description} Note that node fixing has two different effects. First, the number of nodes in the search tree decreases. Second, the average time spent to solve each subproblem decreases, as a consequence of the reduced sizes of the subproblems. %%%%%%% COMPUTATIONAL EXPERIENCE %%%%%%% \section{Computational experience} \label{se-comp} \def\DD{$\Delta = $} As mentioned in the introduction, the algorithm has been extensively tested on random graphs, graphs with special structure and graphs corresponding to instances of real problems. Random graphs are the usual test problems for MSS algorithms and have been used by \cite{Ba90,BaTi90,BaYu86,CaPa90,FrHeWe90}. Nevertheless, our computational experience showed that an algorithm with good performances on random graphs can have very poor performances on structured or "real life" problems. To assess the robustness of our algorithm with respect to the input data, we did a series of experiments with structured (and "real life") problems, which are easy to reproduce. The results are uniformly good. In particular, our algorithm was able to solve in few seconds the infamous covering problems $A_{27}$ and some very large "real life" problems arising from circuit testing. To allow a better comparison with other codes we include also the computing times for these new classes of problems. The algorithm has been coded in C, and executed on a computer IBM RISC 6000-320. Except for the case of graphs arising from code generation, the clique covering generated in the first iteration of the bounding heuristic HEUTHETA is found in a greedy fashion, by applying the same steps as in iteration $2,\dots,\Delta$. Except for the case of graphs arising from circuit testing, the nodes of the graph are ordered by increasing degree, that is if $j > i$, $deg(v_j) \geq deg(v_i)$, where $deg(v) = |N(v)|$. In all the tables the columns identified by {\em Nodes} will show the number of nodes of the graph, by $\Delta = x$ the number of problems of the search tree needed for solving an instance when the number of iterations of HEUTHETA ($\Delta$) is equal to $x$. The time, when given, is expressed in seconds. \paragraph{Random Graph.} For our random graphs we chose the model ${\cal G}\{n,$P(edge) $ = p \}$ (see~\cite{Bo85}) which consists of graphs with node set $V=1,\dots,n$ in which the edges are chosen indipendently with probability $p$. If we define the density of a graph $G$ as the number of edges of $G=(V,E)$ over the number of edges of the complete graph with $|V|$ nodes, then for this class of random graphs the density is very close to $p$. In Table~\ref{ta-random} we compare our algorithm with the fastest algorithm known so far, due to Babel \cite{Ba90}. The number of problems of the search tree is an average of computational results obtained over $25$ graphs. \begin{table} \caption{Random Graphs} \label{ta-random} \begin{center} \begin{tabular}{||c|r|r|r|r|r|} \hline Nodes & p &\DD~5 &\DD~10 &\DD~20 &Ba~~ \\ \hline 100 & .1 &1580 &1282 &1156 &1698 \\ 100 & .2 &1783 &1472 &1338 &2192 \\ 100 & .3 &827 &709 &662 &1018 \\ 100 & .4 &461 &426 &403 &542 \\ 100 & .5 &198 &155 &130 &252 \\ 100 & .6 &75 &63 &60 &116 \\ 100 & .7 &51 &50 &50 &81 \\ 100 & .8 &48 &47 &47 &60 \\ 100 & .9 &34 &31 &30 &31 \\ \hline 200 & .2 &584171 &467891 &361620 &893158 \\ 200 & .3 &73062 &69532 &62513 &79734 \\ 200 & .4 &15691 &13337 &11938 &15747 \\ 200 & .5 &3310 &3008 &2896 &3721 \\ 200 & .6 &1625 &1555 &1505 &1241 \\ 200 & .7 &356 &219 &172 &526 \\ 200 & .8 &128 &127 &126 &192 \\ 200 & .9 &98 &98 &98 &111 \\ \hline 300 & .3 &2055051 &1726808 &1568176 &1521542 \\ 300 & .4 &176816 &151627 &138078 &183454 \\ 300 & .5 &34680 &29161 &25993 &29256 \\ 300 & .6 &6199 &5822 &5644 &6307 \\ 300 & .7 &2645 &2486 &2391 &1953 \\ 300 & .8 &222 &209 &208 &535 \\ 300 & .9 &185 &185 &184 &196 \\ \hline 400 & .4 &1403653 &1180527 &1057331 &1333978 \\ 400 & .5 &159098 &147039 &138426 &141892 \\ 400 & .6 &19326 &15725 &14129 &24606 \\ 400 & .7 &6407 &6284 &6152 &5662 \\ 400 & .8 &1175 &766 &543 &1462 \\ 400 & .9 &267 &267 &267 &295 \\ \hline 500 & .5 &500155 &452937 &432533 &476392 \\ 500 & .6 &78239 &64775 &56601 &66494 \\ 500 & .7 &12772 &12696 &12523 &13015 \\ 500 & .8 &2804 &1923 &1451 &2740 \\ 500 & .9 &357 &354 &357 &415 \\ \hline \end{tabular} \end{center} \end{table} \paragraph{Code Generation.} Given two sequences $s_1,s_2$ of $q$ bits, the {\it Hamming Distance} $H(s_1,s_2)$ is defined as the number of coordinates in which $s_1$ and $s_2$ differ. For example, if $s_1=001001$ and $s_2=101010$, then the Hamming Distance $H(s_1,s_2)=3$ since $s_1$ and $s_2$ differ in the first, fifth and sixth coordinate. A fundamental problem in coding theory is to find the maximum number of sequences of $q$ bits such that any two sequences have Hamming Distance at least $d$, where $q$ and $d$ are given parameters. This problem can be easily stated as a MSS on a graph $G=(V,E)$. In fact, if ${\cal S}_q$ is the family of all sequences of length $q$, then $|V| = |{\cal S}_q|$, and $v_i,v_j \in V$ are connected by an edge iff $H(s_i,s_j) < d$, where $s_i,s_j \in {\cal S}_q$. Clearly, any two nodes in a stable set of $G$ correspond to sequences whose distance is greater than or equal to $d$. A third parameter $w$ is often given in applications, where $w$ denotes the number of $1$'s in a sequence $s$; in this case ${\cal S}_{q,w}$ is the family of all sequences of length $q$ with exactly $w$ $1$'s and $G$ is built again as described above. Besides representing instances of real problems, these graphs are standardly generated and can be used for comparisons among different algorithms. Moreover they are computationally difficult. Computational experience has shown how for this class of graphs it is convenient to use a more sofisticated heuristic for finding a clique covering in the first iteration of HEUTHETA. The one we chose is due to Brelaz \cite{Bre79} and is the base for the bounding in \cite{Ba90,BaTi90}. In table~\ref{ta-code}, the column identified by $d,q,w$ shows the corresponding values for the parameters, while {\em Dens.} is the density of the associated graph. The computing time is relative to the case $\Delta = 5$. Observe that we were not able to solve the problems $(q=8,d=3,w=0)$ (the corresponding graph has $216$ nodes and density equal to $14.12$), $(q=9,d=3,w=0)$ ($512$ nodes and density $8.81$) and $(q=9,d=4,w=0)$ ($512$ nodes and density $25.24$). \begin{table} \caption{Code Sequences} \label{ta-code} \begin{center} \begin{tabular}{||r|r|r|r|r|r|r|c|} \hline $d,q,w$ & Nodes &Dens. &\DD~1 &\DD~5 &\DD~10 &\DD~20 &time \\ \hline $9,4,4$ & 126 &16 &51001 &28397 &21422 &17258 &414.20\\ $9,4,5$ & 126 &16 &42822 &20930 &14185 &10837 &323.15\\ $9,5,0$ & 512 &49.9 &226064 &206651 &200446 &197219 &2831.12\\ \hline \end{tabular} \end{center} \end{table} \paragraph{Steiner Triple System.} A Steiner Triple System (see \cite{NeWo88}) is a set of elements $A= \{a_1,\dots,a_n\}$ and a family $T$ of subsets $t_i \subseteq A$ called {\it triples}, such that $|t_i| = 3$ for all $i$ and any couple of distint elements of $A$ is contained in exaclty one triple of $T$. From a Steiner Triple System we derive a graph $G_S=(V,E)$, with the following rules: \begin{itemize} \item $V = W \cup U$, where $W = \{w_i: a_i \in A\}$ and $U=u_{ij}:t_i\in T , a_j \in t_i$. \item $E=E_U \cup E_{WU}$, where $E_U = \{(u_{ij},u_{ik}) : u_{ij},u_{ik}\in U \}$ and $E_{WU} = \{(w_j,u_{ij}) : w_j\in W$ and $u_{ij} \in U\}$. \end{itemize} In other words, the nodes in $W$ represent the elements of $A$ while the nodes in $U$ represent the triples with $|W| = |A|$ and $|U|=3|T|$. Moreover to each triple $t_i$ corresponds a triangle $K_i$ with nodes in $U$ and each node $w_j \in W$ is connected to the corresponding nodes $u_{ij}$ whenever $a_j \in t_i$. It is well known that the problem of finding a subset $C$ (called {\it cover}) of $A$ of minimum cardinality such that $C \cap t_i \neq \emptyset$, for all $i$, is NP-hard. This problem can be stated as a Set Covering Problem; moreover computational experience has shown how the problem is hard to solve in practice (for $A$ sufficiently large) and in~\cite{FuNeTr74} the authors suggest to use it for testing the quality of algorithms for Set Covering. Now, let $G_S$ be the graph above described: it is possible to show that the cardinality of a minimum cover for a Steiner Triple System defined on $A$ is equal to $|V| - 2|T| - \alpha(G_S)$. The size of the problem depends from the size of the set $A$, and will be indicated by a subscript ($|A_x| = x$). As for the previous class of graphs, these graphs are very easy to generate and can be used for comparisons among algorithms. In table~\ref{ta-steiner}, the column identified by $A$ shows the Steiner System from which the instance arises. \begin{table} \caption{Steiner Triples} \label{ta-steiner} \begin{center} \begin{tabular}{||r|r|r|r|r|r|r|} \hline $A$ &Nodes &Dens. &\DD~5 &\DD~10 &\DD~20 &time \\ \hline $A_{9}$ &40 &7.69 &12 &9 &9 &0.01 \\ $A_{27}$ &350 &1.02 &1933 &1779 &1710 &6.25 \\ $A_{45}$ &1012 &0.37 &293852 &221464 &180406 &5238\\ \hline \end{tabular} \end{center} \end{table} \paragraph{Test Generation for Combinatorial Circuit.} Finally we show computational results over six graphs which arise from a formulation as MSS of a problem of testing combinatorial and sequential circuits for faults~\cite{BrFu85}. Details about this model can be found in~\cite{CaLi91}. These graphs can have a huge number of nodes and are very dense. To our knowledge these are the largest "real life" instances of MSS problems solved to optimality. In this case the value of the parameter $\Delta$ has been set equal to one for all the experiments. The results are shown in table~\ref{ta-circuit}. \begin{table} \caption{Combinatorial Circuits Testing} \label{ta-circuit} \begin{center} \begin{tabular}{||l|r|r|r|r|} \hline Circuit & Nodes & Den. &\DD~1 &time \\ \hline C942.ig9 & 64 &97.32 &4 & $<$0.01 \\ C942.ig3 & 142 &96.42 &60 & 0.02 \\ C942.ig0 & 942 &98.24 &499 & 0.35 \\ C1355 & 1470 &99.8 &749 & 0.7 \\ C1908 & 1864 &99.04 &1230 & 1.16 \\ C7552 & 7542 &99.8 &3721 & 9.50 \\ \hline \end{tabular} \end{center} \end{table} \bibliography{stable} \bibliographystyle{plain} \end{document}