\documentstyle[rutcor,twoside,12pt]{article}
%If you prefer rutcor.cls, use the following
%command instead of the one above
%\documentclass{rutcor} 

%Please fill in the fields below with your information in 
%the order shown. 
\title{
Struction Revisited
}

\author{
Gabriela Alexe\affiliation{RUTCOR, Rutgers University, 640 Bartholomew Road,
Piscataway NJ 08854-8003 USA}
%If there is more than one author use the following commands for 
%each additional name
\and
Peter L. Hammer\affiliation{ RUTCOR, Rutgers University, 640 Bartholomew Road,
Piscataway NJ 08854-8003 USA}
\and
Vadim V. Lozin\affiliation{RUTCOR, Rutgers University, 640 Bartholomew Road,
Piscataway NJ 08854-8003 USA}
\and
Dominique de Werra\affiliation{ ROSE, IMA FSB, EPFL CH 1015 Lausanne, Switzerland}
}

%Repeat the names of the authors here
\authornames{
Gabriela Alexe
\and
Peter L. Hammer
\and
Vadim V. Lozin
\and
Dominique de Werra
}

%Use the following command only if you need to make acknowledgement
\acknowledgement{The partial support provided by ONR grant N00014-92-J-1375 is gratefully acknowledged.\\*[\parskip]
\hspace*{1.5em}
}

\abstract{
The struction method
is a general approach to compute the stability number of a graph
based on step-by-step transformations each of which reduces the
stability number by exactly one. This approach has been
originally derived from Boolean arguments and has been applied by
different authors to compute in polynomial time the stability
number in special classes of graphs. In the present paper we
review basic results on this topic and propose a generalization of the
struction. We also discuss its relationship with some other
graph transformations, such as the cycle shrinking of Edmonds or
the clique reduction of Lov\'asz-Plummer, and the possibility to
use stability preserving transformations to increase the
efficiency of this approach.
\it Keywords: Stable set; Stability number; Graph transformation
}

%Leave the following empty
\rrr{}
\date{}

%Use \maketitle conmmand right after \begin{document}
\begin{document}
\maketitle

\section{Introduction} In a simple graph $G=(V,E)$, a subset of
pairwise non-adjacent vertices is called {\it stable}, and the
number of vertices in a stable set of maximum cardinality the
{\it stability number}. We call $G$ a {\it weighted} graph if
there is mapping $V\to {\bf R}^+$ which associates a positive
weight $w$ to each node $i$.

It has been shown in \cite{EHW84} that the problem of finding in
a weighted graph a stable set of maximum weight is equivalent to
maximizing a pseudo-Boolean function, i.e. a real-valued function
with Boolean variables. Exploiting the relationship between the
two problems, the authors of \cite{EHW84} derived from a Boolean
identity a graph transformation that decreases the stability
number of an arbitrary graph by exactly one.  This transformation
has been called {\it struction} (for STability number RedUCTION).
We describe the idea of the Struction in Section~\ref{sec:fund}
of the present paper.

By applying the struction repeatedly, one can compute the
stability number of any $n$-vertex graph in at most $n$ steps.
However, the number of vertices may increase exponentially during
the computation.  In order to avoid an undesirable growth of the
number of vertices, several specialized versions of the struction
have been designed by combining the general reduction with some
particular transformations that preserve the stability number.
More ideas on this topic along with computational experiments are
presented in Section~\ref{sec:new}.

Section~\ref{sec:gen} introduces a more powerful reduction that
may decrease the stability number by any positive constant. We
exhibit a relationship between the new reduction and some other
graph transformations decreasing the stability number, and
discuss in Section~\ref{sec:app} the possibility of using the
reduction to detect new polynomially solvable cases for the
stable set problem.

All graphs in the paper are undirected, without loops nor
multiple edges. The vertex set and the edge set of a graph $G$
are denoted by $V(G)$ and $E(G)$, respectively. For a subset of
vertices $U\subseteq V(G)$, we let $G[U]$ denote the subgraph of
$G$ induced by $U$, and $N(U)$ the neighborhood of $U$, i.e. the
set of those vertices in $V(G)-U$ that are adjacent to at least
one vertex in $U$. Also, $N[U]:=N(U)\cup U$. When $U=\{a\}$, we
shall write $N(a)$ and $N[a]$ instead of $N(\{a\})$ and
$N[\{a\}]$, respectively. The stability number of $G$ is denoted
by $\alpha(G)$, and the maximum weight of a stable set in $G$ by
$\alpha_w(G)$. A clique in a graph is a subset of pairwise
adjacent vertices. As usual, $P_k$ denotes the chordless path on
$k$ vertices, and $K_{n,m}$ for the complete bipartite graph with
parts of size $n$ and $m$. A graph $G$ is said to be $H$-free if
$G$ does not contain $H$ as an induced subgraph.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basic ideas of Struction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:fund}


It is known that every pseudo-Boolean function $f$ can be written
in a polynomial form $$ f(x_1,\ldots,x_n)=\sum\limits_{i=1}^p
w_iT_i+K, $$ where $K$ is a constant and $T_i=\prod\limits_{j\in
A_i}x_j \prod\limits_{k\in B_i}\overline{x}_k$ with $A_i,
B_i\subseteq \{1,\ldots,n\}$ and $A_i\cap B_i=\emptyset$.
Moreover, using the equality $\overline{x}_j=1-x_j$, one can
always represent the function as a polynomial with positive
coefficients $w_i$ ($i=1,\ldots,p$). If in addition $K=0$, we
call such a representation a {\it posiform}. From this discussion
it follows that the problem of maximizing a pseudo-Boolean
function is polynomially equivalent to the maximization of a
posiform.

Now we reduce the problem of maximizing a posiform to the stable
set problem as follows. To a posiform $f=\sum\limits_{i=1}^p
w_iT_i $ we associate a graph $G_f=(V,E)$ with the set of
vertices $V=\{1,\ldots,p\}$ and the set of edges $E=\{(i,j)\ :\
(A_i\cap B_j)\cup (A_j\cap B_i)\ne \emptyset\}$. In other words,
an edge between two vertices $i$ and $j$ in $G_f$ reflects the
fact that the corresponding terms $T_i$ and $T_j$ are in conflict
in the posiform. Therefore we call $G_f$ the {\it conflict graph}
of $f$. To complete the construction, we associate to each vertex
$i$ of $G_f$ the weight $w_i$. It is clear form the definition of
$G_f$ that $\max f=\alpha_{\omega}(G_f)$.

For the inverse reduction, consider an arbitrary graph $G=(V,E)$
with a positive weight $w_i$ associated with each vertex $i\in
V$. Let $G_j=(V_{1,j},V_{2,j},E_j)$, $j=1,\ldots,q$, be a set of
complete bipartite subgraphs of $G$ (not necessarily induced)
covering all the edges of $G$. Define a posiform
$f_G=\sum\limits_{i\in V}w_iT_i$ by setting
$T_i=\prod\limits_{j\in A_i}x_j \prod\limits_{k\in
B_i}\overline{x}_k$, where $A_i=\{j\ :\ i\in V_{1,j}\}$ and
$B_i=\{j\ :\ i\in V_{2,j}\}$. It is not difficult to prove that
$G$ is the conflict graph of $f_G$. An important remark is that
for a graph $G$, there might exist different coverings of the
edges by complete bipartite subgraphs, which means there are
different posiforms whose conflict graph is $G$.

The relationship between pseudo-Boolean maximization and the
stable set problem made possible the use of Boolean identities to
derive useful graph transformations preserving the stability
number or changing it by a constant (see, for example,
\cite{HH91,Her97,Her00}). In the present paper we will
concentrate on the most powerful tool derived in \cite{EHW84} and
named in \cite{HMW85b} the struction.

Before we describe the idea of struction, let us first consider
two particular graph transformations that represent special cases
of the general reduction. These transformations have been
discovered independently of the general case and might be of
interest on their own. Besides this, they provide a good insight
into the general method.

Assume a vertex $x$ in a graph $G$ has exactly two neighbors $y$
and $z$ non-adjacent to each other. Let $G'$ denote the graph
obtained from $G$ by deleting the vertices $x,y,z$ and
introducing a new vertex $v$ adjacent to each neighbor of $y$ or
$z$ in the graph $G$ (see Figure~\ref{fig:Q} that illustrates the
transformation).

\begin{figure}[ht] \begin{center} \begin{picture}(200,140)
\put(20,30){\circle{15}}
%\put(60,30){\circle{15}}
\put(80,30){\oval(20,15)} \put(140,30){\circle{15}}
\put(40,70){\circle{3}} \put(80,90){\circle{3}}
\put(120,70){\circle{3}} \put(40,70){\line(-1,-2){16}}
%\put(40,70){\line(1,-2){16}}
\put(40,70){\line(1,-1){33}} \put(40,70){\line(2,1){40}}
\put(120,70){\line(1,-2){16}} \put(120,70){\line(-1,-1){33}}
%\put(120,70){\line(-3,-2){53}}
\put(120,70){\line(-2,1){40}}
%\put(80,90){\line(0,-1){53}}
\put(16,26){$Y$}
%\put(56,26){C}
\put(71,26){$YZ$} \put(136,26){$Z$} \put(78,95){$x$}
\put(36,75){$y$}

\put(120,75){$z$} \put(73,0){$G$} \put(170,50){\vector(1,0){30}}
\end{picture} \begin{picture}(180,140) \put(20,30){\circle{15}}
\put(80,30){\oval(20,15)} \put(140,30){\circle{15}}
\put(80,90){\circle{3}} \put(80,90){\line(1,-1){55}}
\put(80,90){\line(-1,-1){55}} \put(80,90){\line(0,-1){53}}
\put(16,26){$Y$} \put(71,26){$YZ$} \put(136,26){$Z$}
\put(78,95){$v$} \put(73,0){$G'$} \end{picture} \end{center}
\caption{Vertex folding} \label{fig:Q} \end{figure}


It is not difficult to verify that

\begin{pro}\label{pro:1} $\alpha(G')=\alpha(G)-1$. \end{pro}

This simple transformation has been called in \cite{CKJ99} the
{\it vertex folding} and has been used to reduce the worst case
time complexity for the vertex cover and stable set problems in
graphs with low degrees.

Now let us take a look at the inverse transformation, which can
be described as follows. Given an arbitrary vertex $v$ in a graph,

\begin{itemize} \item[--] decompose the neighborhood of $v$ into
two (not necessarily disjoint) subsets $Y$ and $Z$; \item[--]
delete $v$ from the graph and introduce instead three new
vertices $x,y,z$; \item[--] connect $y$ to $x$ and to each vertex
in $Y$; connect $z$ to $x$ and to each vertex in $Z$.
\end{itemize}

This transformation has been called in \cite{Ale83} the {\it
vertex splitting} and has been used to obtain the following
remarkable result on the complexity of the stable set problem in
special classes of graphs.

\begin{thm}\label{thm:Aleks} Let $X$ be a class of graphs defined
by a finite set $F$ of forbidden induced subgraphs. If $F$ does
not contain a graph every connected component of which is a tree
with at most 3 leaves, then the stable set problem is NP-hard in
the class $X$. \end{thm}


\medskip A vertex in a graph is called {\it simplicial} if its
neighborhood is a clique. It is an easy exercise to verify that
deletion of any neighbor of a simplicial vertex does not change
the stability number. In other words, one can say that deletion
of a simplicial vertex along with its neighborhood decreases the
stability number by one. It is worth noticing that the simplicial
vertex reduction leads to efficient algorithms for the stable set
problem in some special classes of graphs. A well known example
is given by the chordal (triangulated) graphs (see e.g.
\cite{Gol80}). In some cases, the reduction permits to simplify
the problem substantially. For instance, it has been proven in
\cite{BH99} that the stability number of a $(P_5,K_{1,4},$ fork,
banner)-free graph without simplicial vertices is at most 2.

\medskip Now let us proceed to the general case. As it was
initially we start with a  Boolean-flavoured motivation. Let
$G=(V,E)$ be a graph and $a_0$ a vertex in $V$. Assume
$N(a_0)=\{a_1,\ldots,a_p\}$ and denote
$R:=V-N[a_0]=\{a_{p+1}\ldots,a_{|V|-1}\}$. The struction is based
on the following covering of $E$ by $|V|-1$ stars:

\begin{itemize} \item[--] For each $i=1,\ldots,p$, we consider
the star with the vertex set $\{a_i,a_0\}\cup \{a_j\in N(a_i)\cap
N(a_0) \ :\  j>i\}\cup (N(a_i)\cap R)$ and $a_i$ as the center.
\item[--] For each $i=p+1,\ldots,|V|-1$, we consider the star
with the vertex set $\{a_i\}\cup \{a_j\in N(a_i)\cap R \ :\
j>i\}$ and $a_i$ as the center. \end{itemize} This covering
defines the following terms of the associated posiform
$f=\sum\limits_{i=0}^{|V|-1}w_{a_i}T_{a_i}$:

$$ \begin{array}{rl}
T_{a_0}=&\prod\limits_{i=1}^p\overline{x}_i,\\
\\
T_{a_i}=&\left\{ \begin{array}{lc}
x_i \prod\limits_{\begin{array}{c}_{a_j\in N(a_i)}\\_{1\le j<i\le p}\end{array}}\overline{x}_j&(1\le i\le p),\\
\\
x_i\prod\limits_{a_j\in N(a_i)\cap N(a_0)}\overline{x}_j
\prod\limits_{\begin{array}{c}_{a_j\in N(a_i)\cap R}\\_{p< j<i<
|V|}\end{array}}\overline{x}_j&(p< i< |V|). \end{array} \right.
\end{array} $$

It has been proven in \cite{EHW84} that $$ \sum\limits_{i=0}^p
T_{a_i}=1+\sum\limits_{\begin{array}{c}_{a_q\not\in
N(a_r)}\\_{1\le q<r\le p}\end{array}}x_qx_r\prod\limits_{1\le
s<q}\overline{x}_s\prod\limits_{\begin{array}{c}_{a_t\in
N(a_r)}\\_{q< t<r}\end{array}}\overline{x}_t. $$

Hence, in the case when all weights are equal to 1 (unweighted
case), $f$ can be rewritten as $1+g$, where $g$ also is a
posiform. The conflict graph $G_{a_0}$ associated with $g$
satisfies $\alpha(G_{a_0})=\alpha(G)-1$, and, as was shown in
\cite{EHW84}, $G_{a_0}$ can be obtained directly from $G$ by the
following transformation:


\begin{itemize} \item[--] remove the vertices
$a_0,a_1,\ldots,a_p$ from $G$, \item[--] add to the rest of the
graph a set of new vertices $$W=\{v_{i,j} : 1\le i<j\le p\mbox{
and }(v_i,v_j)\not\in E\};$$ \item[--] join two new vertices
$v_{i,j}$ and $v_{k,l}$ by an edge whenever $i\ne k$ or
$(v_j,v_l)\in E$; join a new vertex $v_{i,j}\in W$ to a vertex
$u\in R$ by an edge whenever $(v_i,u)\in E$ or $(v_j,u)\in E$.
\end{itemize}

It is not hard to see that if $p=2$ and $(a_1,a_2)\not\in E$,
then the struction is nothing but the vertex folding. Also, if
$a_0$ is a simplicial vertex, then the struction coincides with
the simplicial vertex reduction. Both the vertex folding and the
simplicial vertex reduction decrease not only the stability
number but also the number of vertices of the graph. In general,
the number of vertices may increase when struction applies.
Moreover, repeated applications of struction may lead to an
exponential growth of the number of vertices. However, combining
the general reduction with some transformations preserving the
stability number may increase the efficiency of the method and
even lead to polynomial time algorithms for special classes of
graphs. We discuss this topic in Section~\ref{sec:new}. To
conclude, let us mention that the Struction algorithm has been
shown in \cite{HT94} to be a special case of the Basic Algorithm
for pseudo-Boolean optimization \cite{CHJ90}. Moreover, the
authors of \cite{HT94} proposed a new version of the struction
suggested by the Basic Algorithm, which deals with weighted
graphs. Unfortunately, this version has an interpretation in
terms of graphs only in the case of claw-free graphs.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Generalization of Struction and Related Reductions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:gen}

In this section, we suppose that the vertices of a graph $G$ are
numbered with integers $1,2,\ldots,n$, where $n=|V(G)|$. The
vertex with maximum number in a subset $A$ is denoted $m(A)$, and
$A^-$ is defined to be $A-\{m(A)\}$.

Given a graph $G=(V,E)$, an induced subgraph $H$ of $G$, and a
positive integer $p\le\alpha(H)$,  we define $R:=V-N[V(H)]$ and
associate with the triple $(G,H,p)$ a graph $S(G,H,p)$ as follows:
\begin{itemize} \item the vertex set of $S(G,H,p)$ is $R\cup W$,
where $W$ is the family of all stable sets of cardinality $p+1$
in the subgraph of $G$ induced by the vertices of $N[V(H)]$;
\item the edge set of $S(G,H,p)$ consists of \begin{itemize}
\item the edges of the subgraph $G[R]$, \item the edges linking
vertices $A\in W$ and $B\in W$ whenever $A^-\ne B^-$ or
$(m(A),m(B))\in E(G)$, \item the edges linking a vertex $A\in W$
to a vertex $v\in R$ whenever $v$ has a neighbor in the subset
$A$ in the graph $G$. \end{itemize} \end{itemize}

We shall say that two new vertices $A$ and $B$ belong to the same
layer if and only if $A^-=B^-$. The transformation of $G$ into
$S(G,H,p)$ will be referred to as the {\it total struction}. An
example of the total struction is given in Figure~\ref{fig:TS}.

\begin{figure}[ht] \begin{center} \begin{picture}(400,120)
\put(80,20){\circle{20}} \put(120,20){\circle{20}}
\put(160,20){\circle{20}} \put(40,60){\circle{20}}
\put(160,60){\circle{20}} \put(120,60){\circle{20}}
\put(80,60){\circle{20}} \put(80,100){\circle{20}}
\put(80,30){\line(-2,1){40}} \put(80,30){\line(0,1){20}}
\put(80,30){\line(2,1){40}} \put(90,20){\line(1,0){20}}
\put(120,30){\line(0,1){20}} \put(130,20){\line(1,0){20}}
\put(160,30){\line(0,1){20}} \put(80,90){\line(2,-1){40}}
\put(80,90){\line(0,-1){20}} \put(80,90){\line(-2,-1){40}}
\put(80,90){\line(3,-1){72}} \put(80,20){6} \put(120,20){7}
\put(160,20){8} \put(40,60){2} \put(160,60){5} \put(120,60){4}
\put(80,60){3} \put(80,100){1} \put(240,100){\circle{26}}
\put(300,100){\circle{26}} \put(360,100){\circle{26}}
\put(300,60){\circle{26}} \put(240,20){\circle{20}}
\put(360,20){\circle{20}} \put(253,100){\line(1,0){34}}
\put(313,100){\line(1,0){34}} \put(250,20){\line(1,0){100}}
\put(286,100){\line(-1,-2){37}} \put(314,100){\line(1,-2){37}}
\put(300,73){\line(0,1){14}} \put(300,74){\line(-2,1){47}}
\put(300,74){\line(2,1){47}} \put(300,46){\line(-2,-1){50}}
\put(300,46){\line(2,-1){50}} \put(360,87){\line(0,-1){57}}
\put(240,87){\line(0,-1){57}} \put(228,96){2,3,4}
\put(288,96){2,4,5} \put(348,96){2,3,5} \put(288,56){3,4,5}
\put(237,20){7} \put(357,20){8} \put(70,-10){Graph $G$}
\put(260,-10){Graph $S(G,H,p)$} \end{picture} \end{center}
\caption{Total struction of $G$ with $H=G[1,2,3]$ and $p=2$}
\label{fig:TS} \end{figure}


\begin{thm}\label{thm:main} $\alpha(S(G,H,p))=\alpha(G)-p$.
\end{thm}

\begin{proof} Let $M$ be a maximum stable set in $G$, $M_H:=M\cap
N[V(H)]$, $M_R:=M\cap R$. Assume $M_H=\{a_1,\ldots,a_t\}$, where
vertices are indexed in ascending order. It is easy to see that
$t\ge\alpha(H)$, otherwise $M$ is not maximum. For every
$i=1,\ldots,t-p$, define $A_i:=\{a_1,\ldots,a_p,a_{p+i}\}$. Due
to the construction of $S(G,H,p)$, $\{A_1,\ldots,A_{t-p}\}\cup
M_R$ is a stable set of cardinality $|M|-p$ in $S(G,H,p)$. Hence
$\alpha(S(G,H,p))\ge \alpha(G)-p$.

Conversely, let M be a maximum stable set in $S(G,H,p)$,
$M_W:=M\cap W$, $M_R:=M\cap R$. Assume first that
$M_W=\emptyset$, and let $S$ be a stable set of cardinality $p$
in $H$. Then $M_R\cup S$ is a stable set of cardinality $|M|+p$
in $G$. Now let $M_W=\{A_1,\ldots,A_k\}$. In that case
$A^-_1=\ldots=A^-_k$, and the vertices $m(A_1),\ldots,m(A_k)$ are
pairwise nonadjacent in $G$. Thus, $M_R\cup A^-_1\cup
\{m(A_1),\ldots,m(A_k)\}$ is a stable set of cardinality $|M|+p$
in $G$, i.e.  $\alpha(G)\ge\alpha(S(G,H,p))+p$. \end{proof}


\medskip {\bf Remark.} Notice that if $H$ is a singleton, then
$p=1$ and the transformation of $G$ into $S(G,H,p)$ coincides
with the struction.

\medskip Many other graph transformations that reduce the
stability number have been studied in the literature such as the
clique reduction \cite{LP86} or the conic reduction
\cite{Loz00b}. In what follows our purpose is to show that some
of them can be obtained as a combination of the total struction
with stability-preserving transformations. To this end, let us
first introduce a general operation called \underline{subgraph
reduction} that covers many known transformations.

For an induced subgraph $H$ of a graph $G$ and a vertex $v\in
V(G)-V(H)$, let $H+v$ denote the subgraph of $G$ induced by the
set $V(H)\cup\{v\}$. We call the subgraph $H$ $\alpha$-maximal in
$G$ if $\alpha(H+v)=\alpha(H)+1$ for every vertex $v\in
V(G)-V(H)$.

\begin{dfn} Let $G$ be a graph and $H$ an $\alpha$-maximal
induced subgraph of $G$. The graph transformation consisting in
\begin{itemize} \item[(1)] removing $H$ from $G$, \item[(2)]
linking two vertices $x$ and $y$ in $N(V(H))$ whenever
$\alpha(H+x+y)=\alpha(H)+1$ \end{itemize} will be called the
$H$-reduction of $G$. The graph produced by the $H$-reduction of
$G$ will be denoted $T(G,H)$. We shall say that the $H$-reduction
is $\alpha$-{\it perfect} if $\alpha(T(G,H))=\alpha(G)-\alpha(H)$.
\end{dfn}


Let us consider several examples of subgraph reductions. The
first one is the so-called cycle shrinking introduced by Edmonds
for solving the maximum matching problem \cite{Edm65}. The
following lemma, quoted from \cite{LP86}, describes the reduction.

\begin{lem}\label{lem:match} Let $G$ be a graph, $M$ a matching
in $G$ and let $Z$ be a cycle of length $2k+1$ which contains $k$
edges of $M$ and is vertex-disjoint from the rest of $M$.
Construct a new graph $G'$ from $G$ by shrinking $Z$ to a single
vertex. Then $M'=M-E(Z)$ is a maximum matching in $G'$ if and
only if $M$ is a maximum matching in $G$. \end{lem}

It is well known that finding a maximum matching in a graph $G$
is equivalent to finding a maximum stable set in the line graph
of $G$, denoted $L(G)$ and defined as follows: the vertices of
$L(G)$ are the edges of $G$, and two vertices are adjacent in
$L(G)$ if and only if the corresponding edges of $G$ have a
vertex in common. The subsequent proposition shows that the cycle
shrinking, translated from matchings to stable sets, is an
$\alpha$-perfect subgraph reduction.

\begin{thm}\label{thm:shrink} Let $G$, $G'$, $M$, $Z$ and $k$
satisfy the conditions of Lemma~\ref{lem:match}. Then
$L(G')=T(L(G),H)$ and $\alpha(L(G'))=\alpha(L(G))-\alpha(H)$ for
some induced subgraph $H$ of the graph $L(G)$. \end{thm}

\begin{proof} Let $C$ be the set of edges of the cycle $Z$, and
$A$ the set of chords of $Z$, and $B$ the set of edges with
exactly one endpoint belonging to $Z$ in the graph $G$. Denote by
$H$ the subgraph of $L(G)$ induced by the set $C\cup A$.

First, observe that $\alpha(H)=k$. Indeed, the set $C$ contains a
matching on $k$ edges, and therefore $\alpha(H)\ge k$. On the
other hand, $C\cup A$ covers $2k+1$ vertices in $G$ and hence
cannot contain a matching of size $k+1$. Also, it is not hard to
see that for any edge $x\in B$, the set $C\cup \{x\}$ contains a
matching of size $k+1$, which means that $H$ is $\alpha$-maximal
in $L(G)$. Hence we may apply the $H$-reduction to $L(G)$.
Removal of $H$ in step (1) of the reduction corresponds to
deletion of the edges of the set $C\cup A$ from the graph $G$. To
analyze step (2), consider two vertices $x$ and $y$ in
$B=N(V(H))$. Under the $H$-reduction, these vertices are linked
by an edge, since in the graph $G$ the set of edges $C\cup
A\cup\{x,y\}$ covers at most $2k+3$ vertices, and hence
$\alpha(H+x+y)=k+1$. On the other hand, shrinking the cycle $Z$
to a single vertex $z$ in the graph $G$ makes the edges $x$ and
$y$ adjacent, since $z$ is their common neighbor.

Thus, we have shown that the cycle shrinking in $G$ is equivalent
to the $H$-reduction in $L(G)$, i.e. $L(G')=T(L(G),H)$. The fact
that $\alpha(L(G'))=\alpha(L(G))-\alpha(H)$ is a direct
consequence of Lemma~\ref{lem:match} and the above discussion.
\end{proof}

\medskip Our next example is the clique reduction, i.e. an
$H$-reduction with a clique $H$. This reduction has been
originally introduced in \cite{LP86} by Lov\'asz and Plummer.
They showed that the clique reduction is $\alpha$-perfect in
claw-free graphs if \begin{equation}\label{eq:1} \alpha(N(H))\le
2. \end{equation} Moreover, Lov\'asz and Plummer introduced one
more subgraph reduction and characterized sufficient conditions
under which the reduction is $\alpha$-perfect. Both reductions
have been used in order to reduce the stable set problem from
claw-free graphs to line graphs.

Many other useful subgraph reductions can be mentioned. An
obvious advantage of these reductions is that they decrease the
number of vertices. A disadvantage is that they are not
$\alpha$-perfect in general. On the other hand the struction does
generally increase the number of vertices, while the decrease of
the stability number is guaranteed. Thus, the subgraph reductions
and the total struction seem to be two extreme types of graph
transformations with respect to the stable set problem. However,
there is some relation between any $H$-reduction and the total
struction centered at $H$. To exhibit this relation, let us
define $S(G,H):=S(G,H,\alpha(H))$. Recall that the construction
of $S(G,H)$ depends on the ordering of vertices in $G$.  We shall
assume throughout the section that \begin{equation}\label{eq:2}
\mbox{the vertices of $H$ precede the vertices outside $H$ in the
ordering of $V(G)$.} \end{equation}

\begin{thm}\label{thm:sub} If $H$ is an $\alpha$-maximal subgraph of
$G$, then the graph $T(G,H)$ is a subgraph (not necessarily
induced) of $S(G,H)$. \end{thm}

\begin{proof} We shall define an injection $f$ from the vertex
set of $T(G,H)$ to the vertex set of $S(G,H)$ such that adjacency
of vertices $u,v$ in the  graph $T(G,H)$ will imply adjacency of
the corresponding vertices $f(u), f(v)$ in the graph $S(G,H)$.

The graphs $T(G,H)$ and $S(G,H)$ have a common part
$R:=V(G)-N[V(H)]$ which is not affected by these transformations.
So, we define $f(v):=v$ for each vertex $v\in R$.

Every vertex $u$ of $T(G,H)$, which is not in $R$, has a neighbor
in $H$ in the graph $G$, i.e. $u\in N(V(H))$. Since $H$ is
$\alpha$-maximal, it contains a stable set $S$ of size
$\alpha(H)$ such that the set $S_u:=S\cup \{u\}$ is stable as
well. This means that $S_u$ forms a new vertex in the graph
$S(G,H)$. So we define $f(u):=S_u$ for each vertex $u\in
N(V(H))$. Notice that $N(u)\cap R=N(S_u)\cap R$ due to the
construction of the graph $S(G,H)$.

Now in order to prove that $T(G,H)$ is a subgraph of $S(G,H)$ it
remains to show that for any two vertices $u,v\in N(V(H))$,
$(u,v)\in E(T(G,H))$ implies $(f(u),f(v))\in E(S(G,H))$. Assume
by contradiction that $f(u)$ is not adjacent to $f(v)$ in
$S(G,H)$. This means that $S^-_u=S^-_v$, and $m(S_u)$ is not
adjacent to $m(S_v)$ in $G$. From the assumption~\ref{eq:2} we
know that $m(S_u)=u$ and $m(S_v)=v$, which means that
$S^-_u\cup\{u,v\}$ is a stable set in $G$. However, this fact
contradicts the assumption that $u$ is adjacent to $v$ in
$T(G,H)$. \end{proof}

\medskip Theorem~\ref{thm:sub} suggests the idea that
$\alpha$-perfect subgraph reductions can be obtained by combining
the total struction with some stability-preserving
transformations. To support this idea we prove in the next
theorem that under condition~(\ref{eq:1}) any subgraph reduction
is $\alpha$-perfect, and furthermore, it can be obtained by
combining the total struction with magnet simplification, the
reduction introduced in \cite{HH91}. For definition of the
reduction, we refer the reader to Section~\ref{sec:new} of the
present paper. \begin{thm}\label{thm:sr} Let $G$ be a graph, and
$H$ an $\alpha$-maximal induced subgraph of $G$. If the
condition~(\ref{eq:1}) holds, then
$\alpha(T(G,H))=\alpha(G)-\alpha(H)$. Moreover, the graph
$T(G,H)$ can be obtained from $S(G,H)$ by repeatedly applying the
magnet simplification. \end{thm}

\begin{proof} Let $A$ be a new vertex in the graph $S(G,H)$, i.e.
$A$ is a stable set in the subgraph of $G$ induced by $N[V(H)]$.
Since the cardinality of $A$ is $\alpha(H)+1$, it has a non-empty
intersection with $N(V(H))$. Because of (1), either $|A\cap
N(V(H))|=1$, in which case we call $A$ a vertex of type 1, or
$|A\cap N(V(H))|=2$, in which case we call $A$ a vertex of type 2.

Assume first that $A$ is a vertex of type 2. Then there must
exist a vertex $B$ of type 1 such that $m(A)=m(B)$ (since $H$ is
$\alpha$-maximal). Moreover,  $A$ must be adjacent to any other
new vertex of $S(G,H)$ (since $\alpha(N(H))\le 2$). Therefore, in
$S(G,H)$ the vertices $A$ and $B$ are adjacent, and every
neighbor of $B$ is also a neighbor of $A$, which means that the
neighborhood reduction (a special case of the magnet
simplification) is applicable to the pair of vertices $A$ and $B$
in $S(G,H)$. Thus, we can delete all new vertices of type 2 from
$S(G,H)$ without changing its stability number.

Now let $A$ and $B$ be two new vertices of type 1 such that
$m(A)=m(B)$. By definition, such vertices must be adjacent in
$S(G,H)$, since they belong to distinct layers. Moreover, any two
new vertices $C\in N(A)-N(B)$ and $D\in N(B)-N(A)$ also belong to
distinct layers. Therefore, we can apply the magnet
simplification with respect to $A$ and $B$. Without loss of
generality we delete the vertex $A$ and the edges of the form
$(B,D)$ with $D\in N(B)-N(A)$. We apply this transformation as
long as possible. As a result, the graph $S(G,H)$ is transformed
into a graph $G"$ in which for every vertex $a\in N(V(H))$, there
is a unique new vertex $A$ with $m(A)=a$. To complete the proof,
it remains to show that two new vertices $A$ and $B$ are adjacent
in $G"$ if and only if $\alpha(H+a+b)=\alpha(H)+1$, where
$a:=m(A)$ and $b:=m(B)$.

\medskip

Let first $A$ be non-adjacent to $B$ in $G"$. Two cases are
possible.

{\it Case 1}: $A$ and $B$ belong to the same layer of the graph
$S(G,H)$. In this case $A^-\cup\{a,b\}$ is a stable set in $G$,
i.e. $\alpha(H+a+b)=\alpha(H)+2$.

{\it Case 2}: $A$ and $B$ belong to distinct layers of the graph
$S(G,H)$. In that case, the edge $(A,B)$ has been deleted under
the magnet simplification. Let $C$ be the vertex deleted together
with this edge. Without loss of generality, assume $m(C)=a$. Then
$C$ and $B$ belong to the same layer, and $C$ is not adjacent to
$B$. Now we are in the conditions of Case 1.

\medskip

Now let $A$ and $B$ be adjacent in $G"$. Assume, to the contrary,
that $\alpha(H+a+b)=\alpha(H)+2$, i.e. the graph $H$  contains a
stable set $S$ of cardinality $\alpha(H)$ such that
$S\cup\{a,b\}$ is a stable set in $G$.

If $A^- =B^- =S$, then $A$ must be non-adjacent to $B$ by the
construction of $S(G,H)$. If $A^- \ne S, B^- =S$, then $A$ and
$B$ are non-adjacent in $G"$, because the edge $(A,B)$ must be
deleted by the magnet simplification along with the vertex
$S\cup \{a\}$.


Finally, let  $A^- \ne S$ and $B^- \ne S$, and assume without
loss of generality that the vertex $S\cup \{a\}$ has been deleted
from $S(G,H)$ together with the edge $(A,S\cup\{b\})$ before
deletion of the vertex $S\cup\{b\}$. But then the edge $(A,B)$
should be deleted together with the vertex $S\cup\{b\}$.
\end{proof}

\medskip
%clique reduction
A consequence of this theorem is that the clique reduction of
Lov\'asz and Plummer is a conjunction of the total struction with
the magnet simplification. We conclude the section with some
additional remarks regarding the clique reduction. It is not hard
to verify that the special version of struction used in
\cite{HMW85b} can be viewed as a combination of the struction
with the magnet simplification. It is also worth mentioning that
this version is nothing but the clique reduction applied
implicitly. After the clique reduction has been introduced in
\cite{LP86} in an explicit form, it has been applied several
times to compute the stability number of graphs in special
classes in polynomial time \cite{SS93,HW93,Her95}. Also, the edge
projection, which is a specialization of the clique reduction
when restricted to edges, has been used in \cite{MS96,MS99} to
develop some heuristics for the stable set problem.



%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%
\section{Struction in Special Classes of Graphs}
%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%
\label{sec:app}

As mentioned above the struction and some related reductions have
been applied to develop polynomial time algorithms for the stable
set problem in special classes of graphs
\cite{HMW85a,HMW85b,Her86}. In this section we discuss the
possibility of obtaining new polynomially solvable cases by the
total struction. Let us first distinguish promising directions
for this research.

It is known that the stable set problem is polynomially solvable
in the class of $mK_2$-free graphs, where $mK_2$ is the disjoint
union of $m$ copies of $K_2$. This conclusion can be made by
combining two results: a polynomial upper bound on the number of
maximal stable sets in $mK_2$-free graphs \cite{FHT93}, and the
algorithm in \cite{TIAS97} generating all maximal stable sets.
Recently, polynomial time solvability of the stable set problem
has been proven for the class of fork-free graphs \cite{Ale99},
where a fork (called also a chair) is the graph obtained from a
claw $K_{1,3}$ by a single subdivision of an edge. Therefore,
according to Theorem~\ref{thm:Aleks}, there are exactly two
minimal hereditary classes of graphs defined by a single
forbidden induced subgraph for which the complexity status of the
stable set problem is an open question. These are $P_5$-free
graphs and $(P_3+P_2)$-free graphs, where $P_3+P_2$ is the
disjoint union of a $P_3$ and $P_2$. Polynomial algorithms have
been developed for many particular subclasses of $P_5$-free
graphs (see, for example, \cite{BH99,Loz00,Mos97}, and also
\cite{GL02} for a survey on the topic). However, the complexity
of the problem in the class of $P_5$-free graphs is still
unknown. For $(P_3+P_2)$-free graphs the question is open too. As
a partial answer to this question we prove in this section that
both classes are closed under the total struction. A similar
result has been proven in \cite{DeW84} by de Werra, who showed
that $(C_k, P_k)$-free graphs ($k\geq 4$) are closed under struction. We
extend this result in two ways. First, our result holds for more
general classes of graphs. Second, we prove that those classes
are closed with respect to the total struction.


\begin{thm} Let $D$ be a graph every connected component of which
is a chordless path. If $G$ is a $D$-free graph and $H$ is a
connected induced subgraph of $G$, then $S(G,H,p)$ is $D$-free.
\end{thm}

\begin{proof} It is not hard to see that if $H$ is connected,
then for any two vertices $a,b$ in $N[V(H)]$, there is a
chordless $(a,b)$-path every internal vertex of which (i.e. a
vertex different form the endpoints of the path) belongs to $H$.
We shall denote this path $P(a,b)$.

Suppose by contradiction that a set $Y$ induces a graph $D$ in
$S(G,H,p)$.  Define $Y_R:=Y\cap R,\ Y_W:=Y\cap W$. Let
$Y_W=\{A_1,\ldots,A_k\}$. Obviously, the vertices of $Y_W$ belong
to at most two different layers of $S(G,H,p)$, since otherwise a
triangle arises. We distinguish two cases.

{\it Case 1}. The vertices of $Y_W$ belong to exactly two layers.
In this case the number of vertices in $Y_W$ is at most three,
since otherwise either a cycle or a vertex of degree more than
two appears in $D$. Moreover, all the vertices of $Y_W$ belong to
the same component of $D$. We denote this component by $P_m$ and
let $Y_P:=Y_R\cap V(P_m)$. Consider two subcases.

1.1. $k=3$, and $A_3^-\ne A_1^-,A_2^-$, and $A_1$ is not adjacent
to $A_2$ in $S(G,H,p)$.  Each one of the vertices $A_1$ and $A_2$
has at most one neighbor in $Y_R$. So we can choose a vertex
$a_1\in A_1$ and a vertex $a_2\in A_2$ in such a way that
$N(a_i)\cap Y_R=N(A_i)\cap Y_R$ $(i=1,2)$. Clearly, $a_1$ is not
adjacent to $a_2$, and hence the path $P(a_1,a_2)$ has at least
three vertices. Consequently, the vertices of $P(a_1,a_2)$
together with $m-3$ vertices of $Y_P$ induce in $G$ a chordless
path with at least $m$ vertices, which means that $G$ contains
$D$ as an induced subgraph, a contradiction.

1.2. $k=2$. Then $A_1^-\ne A_2^-$, and $A_1$ is adjacent to $A_2$
in $S(G,H,p)$.  We choose two vertices $a_1\in A_1$ and $a_2\in
A_2$ by analogy with case 1.1, and make a similar conclusion: the
path $P(a_1,a_2)$ together with $m-2$ vertices in $Y_P$ induce in
$G$ a chordless  path with at least $m$ vertices, i.e. $G$
contains $D$ as an induced subgraph, again a contradiction.

{\it Case 2}. All the vertices of $Y_W$ are in the same layer,
i.e. $A_1^-=A_2^-=\ldots=A_k^-=A$. If no vertex in $Y_R$ has a
neighbor in $A$ in the graph $G$, then the set
$\{m(A_1),\ldots,m(A_k)\}\cup Y_R$ induces $D$ in $G$, a
contradiction.  If there is a vertex $y\in Y_R$ adjacent in $G$
to some vertex of $A$, then $k\le 2$ (otherwise $y$ has degree
$k>2$ in $D$). We consider two subcases.

2.1. $k=2$. Then $A_1$ and $A_2$ are non-adjacent (otherwise,
$y,A_1,A_2$ form a triangle), and  the vertex $y$ is the unique
vertex in $Y_R$ adjacent both to $A_1$ and to $A_2$ (otherwise a
cycle arises in $D$).

Denote by $Y_R^{'}$ the set obtained from $Y_R$ by deleting the
vertex $y$. Each one of the vertices $A_1$ and $A_2$ has at most
one neighbour in $Y_R^{'}$. Choosing two vertices $a_1\in A_1$
and $a_2\in A_2$ by analogy with case 1.1, we conclude that the
vertices  of $P(a_1,a_2)$ together with  $Y_R^{'}$ induce in $G$
a graph containing $D$ as an induced subgraph,  a contradiction.

2.2. $k=1$. If $A_1$ contains a vertex $a$ whose neighborhood in
$Y_R$ is the same as the neighborhood of $A_1$ in $Y_R$, then
$G[\{a\}\cup Y_R]=D$. Otherwise, there are vertices $a_1, a_2\in
A_1$ each of which has a single neighbor in $Y_R$. So, the
vertices of $P(a_1,a_2)$ together with $Y_R$ induce in $G$ a
graph containing $D$ as induced subgraph, a contradiction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Combining Struction and Stability-Preserving
Transformations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:new}

As pointed out before, the main problem which can appear in the
repeated application of the struction algorithm is that the number
of vertices of the graphs appearing in this sequence may increase
exponentially. As an attempt to counterbalance this problem,
we propose to apply at every
stage of this process some simple stability preserving graph
transformations. We shall first describe a few of these
transformations, the essential role of which is to make it
possible to apply the struction without excessive increases of the
number of vertices.

(i) \textit{Neighborhood reduction}. Assume that a graph has a
pair of adjacent vertices $a$ and $b$ such that every vertex
adjacent to $b$ is also adjacent to $a$. Then the deletion of the
vertex $a$ from the graph does not change its stability number.
This simple transformation has been described
in the literature under different names, and shall be called here \textit{%
neighborhood reduction}.

In \cite{GH88}, this transformation has been used in order to
bring any circular arc graph to a canonical form for which the
stability number can be determined in a straightforward way. The
alternative application of struction and of neighborhood
reduction was shown in \cite{HMW85a} to produce a polynomial time
algorithm for finding the stability number of a subclass of
claw-free graphs.

(ii) \textit{Magnet} \textit{simplification}. A generalization of
neighborhood reduction was proposed in \cite{HH91} for graphs
$G=(V,E)$ containing a magnet. A \textit{magnet} is defined as a
pair $(a,b)$ of adjacent vertices such that every vertex in
$N(a)\backslash N(b)$ is adjacent to every vertex in
$N(b)\backslash N(a)$. Under these conditions, the edges incident
to $a$ or $b$ can be covered by the following
two complete bipartite subgraphs $G_{1}=(N(b)-N(a),N(a)-N(b),E_{1})$ and $%
G_{2}=(\{a,b\},N(a)\cap N(b),E_{2})$ of $G$. Let us consider now
an arbitrary covering of the edges in $E-(E_{1}\cup E_{2})$ with
complete
bipartite partial subgraphs $G_{3},\ldots ,G_{q}$ of $G$. The graphs $%
G_{1},\ldots ,G_{q}$ cover all the edges of $E,$ and the
associated posiform
$f=\sum_{v\in V}w_{v}T_{v}$ is such that $T_{a}=x_{1}x_{2}$ and $T_{b}=%
\overline{x}_{1}x_{2}$, and therefore, $T_{a}+T_{b}=(x_{1}+\overline{x}%
_{1})x_{2}=x_{2}$. It follows that $f$ has the same maximum value
as the posiform $g=\sum\limits_{v\in
V-\{a,b\}}w_{v}T_{v}+w_{a}x_{2},$ i.e. the conflict graph
$G^{\prime }=(V^{\prime },E^{\prime })$ associated with $G$
satisfies $|V^{\prime }|=|V|-1,$ and $\alpha (G^{\prime })=\alpha
(G)$. In graph theoretical terms, this means that the graph
$G^{\prime }$ can be obtained directly from $G$ by deleting the
vertex $a$ together with all the edges $(v,b)$ with $v\in
N(b)\backslash N(a)$.

Notice that neighborhood reduction is the special case of magnet
simplification in which $N(b)\backslash N[a]=\emptyset .$

It was shown in \cite{HMW85b} that the alternating application of
struction and of magnet simplification provides a polynomial time
algorithm for finding the stability number of a special class of
claw-free graphs, which strictly includes the class examined in
\cite{HMW85a}.

(iii) \textit{Edge insertion/removal.} An ordered triple of vertices $%
(a,b,c) $ of a graph $G,$ such that $a$ is adjacent to $b,$ but
not to $c$,
and $N(a)\subseteq N(c)\cup N[b],$ will be called a \textit{switching triple}%
. It has been shown in \cite{BHH85} that the insertion of the
edge $(b,c)$
(if it is absent in $G$), or the removal of this edge (if it is present in $%
G $), does not alter the stability number of the graph $G.$ This
fact allows us to perform edge \textit{removal} and
\textit{insertion} corresponding to a switching triple $(a,b,c)$,
as additional stability preserving graph transformations.

It is easy to see that if $(a,b)$ is a magnet in a graph $G$,
then for any vertex $c\in N(b)\backslash N[a]$, the triple
$(a,b,c)$ is switching, and we may delete the edge $(b,c)$
without changing the stability number of $G$. After deletion of
all such edges, neighborhood reduction can be applied to the pair
of vertices $(a,b)$. Therefore, the magnet simplification can be
viewed as the result of the repeated applications of edge
removals, followed by neighborhood reductions.

Notice however that edge removal/insertion may be applicable even
if the graph contains no magnets. Moreover, in its turn, edge
insertion may also be helpful when used in conjunction with
struction. We shall illustrate this idea by the following simple
example.

\bigskip \begin{figure}[ht] \begin{center}
\begin{picture}(130,120) \put(80,20){\circle{20}}
\put(120,20){\circle{20}} \put(40,60){\circle{20}}
\put(40,20){\circle{20}} \put(120,60){\circle{20}}
\put(80,60){\circle{20}} \put(80,100){\circle{20}}
\put(50,60){\line(1,0){20}} \put(80,30){\line(0,1){20}}
\put(50,20){\line(1,0){20}} \put(90,20){\line(1,0){20}}
\put(120,30){\line(0,1){20}}
%\put(130,20){\line(1,0){20}}
\put(40,30){\line(0,1){20}}

\put(80,90){\line(2,-1){40}} \put(80,90){\line(0,-1){20}}
\put(80,90){\line(-2,-1){40}}
%\put(80,90){\line(3,-1){72}}
\put(77,19){$a_5$} \put(117,19){$a_6$} \put(37,59){$a_1$}
\put(37,19){$a_4$} \put(117,59){$a_3$} \put(77,59){$a_2$}
\put(77,99){$a_0$} \put(75,-3){(a)} \end{picture}
\begin{picture}(130,120) \put(80,20){\circle{20}}
\put(120,20){\circle{20}} \put(40,60){\circle{20}}
\put(40,20){\circle{20}} \put(120,60){\circle{20}}
\put(80,60){\circle{20}} \put(80,100){\circle{20}}
\put(50,60){\line(1,0){20}} \put(80,30){\line(0,1){20}}
\put(50,20){\line(1,0){20}} \put(90,20){\line(1,0){20}}
\put(120,30){\line(0,1){20}} \put(120,30){\line(-4,1){80}}
\put(40,30){\line(0,1){20}} \put(80,90){\line(2,-1){40}}
\put(80,90){\line(0,-1){20}} \put(80,90){\line(-2,-1){40}}
\put(120,30){\line(-2,1){40}} \put(77,19){$a_5$}
\put(117,19){$a_6$} \put(37,59){$a_1$} \put(37,19){$a_4$}
\put(117,59){$a_3$} \put(77,59){$a_2$} \put(77,99){$a_0$}
\put(75,-3){(b)} \end{picture} \begin{picture}(130,120)
\put(80,20){\circle{20}} \put(120,20){\circle{20}}
\put(40,60){\circle{20}} \put(40,20){\circle{20}}
\put(120,60){\circle{20}} \put(80,60){\circle{20}}
\put(80,100){\circle{20}} \put(50,60){\line(1,0){20}}
\put(80,30){\line(0,1){20}} \put(50,20){\line(1,0){20}}
\put(90,20){\line(1,0){20}} \put(120,30){\line(0,1){20}}
%\put(130,20){\line(1,0){20}}
\put(40,30){\line(0,1){20}} \put(80,90){\line(2,-1){40}}
\put(120,30){\line(-4,1){80}} \put(120,30){\line(-2,1){40}}
\put(77,19){$a_5$} \put(117,19){$a_6$} \put(37,59){$a_1$}
\put(37,19){$a_4$} \put(117,59){$a_3$} \put(77,59){$a_2$}
\put(77,99){$a_0$} \put(75,-3){(c)} \end{picture} \end{center}
\caption{Edge removal/insertion} \label{fig:ILL} \end{figure}

\bigskip

Given the graph $G,$ in Figure~\ref{fig:ILL}(a), we notice the
presence of the switching triples $(a_{0},a_{1},a_{6})$ and
$(a_{0},a_{2},a_{6}),$ so we add the edges $(a_{1},a_{6})$ and
$(a_{2},a_{6})$ to the graph $G$ (Figure~\ref{fig:ILL}(b)). After
this transformation, using the switching
triples $(a_{3},a_{0},a_{1})$, $(a_{3},a_{0},a_{2}),$ we delete the edges $%
(a_{0},a_{1})$, $(a_{0},a_{2})$ (Figure~\ref{fig:ILL}(c)). In the
resulting graph, vertex $a_{0}$ has degree 1, and the application
of the struction
operation centered at $a_{0},$ consists simply in deleting $a_{0}$ and $%
a_{3} $.

This example suggests the idea of combining the application of
struction with several stability preserving operations. More
precisely, we shall describe two transformations each of which
consists of combinations of the elementary transformations
described above.

(a) \textit{Guided struction}. Under the assumption that the
center of struction is in a particular vertex $v$ of the graph
$G,$ the guided struction performs some stability preserving
transformations in the neighborhood $N(v)$ of $v,$ in such a way
that the graph $G^{\prime }$ obtained after struction should have
as few vertices as possible. This goal is achieved by first
applying the technique (iii) described above, for removing as
many of the edges $(v,u)$ with $u$ $\in N(v))$ as possible.
Afterwards, the same technique (iii) is used for inserting as many edges $%
(u,w),$ with $u$, $w$ $\in N(v)$ as possible, in order to reduce
the number of new vertices introduced by struction. In fact, this
last transformation could be viewed as neighborhood reduction in
$G^{\prime }.$ Clearly, the net increase of the number of nodes
will be equal to the number of non-edges remaining in the
so-transformed neighborhood of $v,$minus $|N[v]|$. After
calculating $\nu _{v}$ for every $v$ $\in V,$ the center $v_{0}$
of the transformation is now selected to be the vertex which
minimizes $\nu _{v}.$

(b) \textit{Compactification}. It has been noticed that the
performance of struction is strongly influenced by the size of
the vertex set and by the density of the edge set. The efficiency
of struction is in general higher in the case of graphs having
higher densities of their edge sets. In order to increase the
efficiency of struction, compactification repeats as many times
as possible the stability preserving transformations (i) - (iii),
starting with edge insertions, followed by neighborhood
reductions and then by magnet simplifications.

In a first series of computational experiments we have compared
the efficiency of struction with that of guided struction. In a
second series of computational experiments we have compared the
efficiency of applying guided struction with or without a
preliminary compactification of the graph.

In all the experiments, we have randomly generated graphs having
50 vertices and densities of 10\%, 20\%, ...., 90\%. Parts of
these experiments were carried out on randomly generated graphs
with a uniform distribution of the edges. In other experiments,
the edges of the randomly generated graphs had a non-uniform
distribution, these graphs having been generated as unions of
randomly generated subgraphs of high and of low edge densities.
All the computations were carried out on a Pentium 3 1.7GHz
processor.

\begin{table}[tp] \begin{center}
\begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&47&10&0.05&47&10&0.09&0\\
50&20&50&25&0.05&50&25&0.11&0\\
50&30&54&40&0.06&54&40&0.11&0\\
50&40&78&65&0.06&78&65&0.12&0\\
50&50&101&83&0.09&100&82&0.14&1\\
50&60&110&90&0.09&103&89&0.15&6\\
50&70&125&94&0.1&74&60&0.13&41\\
50&80&114&97&0.1&42&70&0.1&63\\
50&90&79&98&0.07&31&88&0.11&61\\
\hline \end{tabular}

\medskip \centerline{(a) 1 application of Struction / Guided
Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&44&11&0.06&43&10&0.12&2\\
50&20&62&44&0.07&62&44&0.13&0\\
50&30&81&67&0.07&80&66&0.13&1\\
50&40&204&94&0.13&65&47&0.12&68\\
50&50&400&98&0.2&74&47&0.14&82\\
50&60&383&99&0.18&67&73&0.15&83\\
50&70&188&99&0.15&29&63&0.14&85\\
50&80&50&99&0.06&20&54&0.11&60\\
50&90&1&0&0&1&1&0.11&0\\
\hline \end{tabular}

\medskip \centerline{(b) 3 consecutive applications of Struction
/ Guided Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&39&14&0.06&39&14&0.12&0\\
50&20&66&55&0.07&65&42&0.13&2\\
50&30&561&98&0.18&77&64&0.14&86\\
50&40&613&99&0.19&65&45&0.12&89\\
50&50&298&99&0.14&48&40&0.15&84\\
50&60&98&99&0.18&37&48&0.15&62\\
50&70&20&99&0.16&5&47&0.14&75\\
50&80&1&0&0.06&0&0&0.12&100\\
50&90&0&0&0&0&0&0.11&N/A\\
\hline \end{tabular}

\medskip \centerline{(c) 5 consecutive applications of Struction
/ Guided Struction}

\end{center} \caption{Uniformly Randomly Generated Graphs}
\end{table}

%%%%%%%%%%%%%%% Table 2 %%%%%%%%%%%%%%%%%

\begin{table}[tp] \begin{center}
\begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&47&10&0.001&47&10&0.001&0\\
50&20&46&20&0.001&45&15&0.001&2\\
50&30&42&23&0.004&42&23&0.004&0\\
50&40&43&38&0.004&38&25&0.003&12\\
50&50&39&37&0.003&35&29&0.002&10\\
50&60&38&51&0.003&29&25&0.002&24\\
50&70&30&51&0.002&24&33&0.002&20\\
50&80&29&64&0.001&18&38&0.001&38\\
50&90&20&74&0.001&12&40&0.001&40\\
\hline \end{tabular}

\medskip \centerline{(a) 1 application of Struction / Guided
Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&42&10&0.002&42&10&0.001&0\\
50&20&37&14&0.001&37&14&0.001&0\\
50&30&34&20&0.004&33&15&0.004&3\\
50&40&32&29&0.002&28&14&0.003&13\\
50&50&26&25&0.003&24&15&0.003&8\\
50&60&26&39&0.003&23&22&0.002&12\\
50&70&15&35&0.002&10&34&0.002&33\\
50&80&9&16&0.001&5&21&0.001&44\\
50&90&5&0&0.001&5&0&0.001&0\\
\hline \end{tabular}

\medskip \centerline{(b) 3 consecutive applications of Struction
/ Guided Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&33&2&0.002&24&3&0.001&27\\
50&20&34&18&0.001&25&12&0.001&26\\
50&30&28&19&0.004&15&16&0.004&46\\
50&40&22&22&0.002&11&19&0.003&50\\
50&50&21&35&0.003&15&15&0.003&29\\
50&60&13&28&0.003&11&16&0.002&15\\
50&70&11&21&0.002&8&7&0.002&27\\
50&80&7&65&0.001&5&20&0.001&29\\
50&90&1&0&0.001&1&0&0.001&N/A\\
\hline \end{tabular}

\medskip \centerline{(c) 5 consecutive applications of Struction
/ Guided Struction}

\end{center} \caption{Non-Uniformly Randomly Generated Graphs}
\end{table}

%%%%%%% Table 3 %%%%%%%%%%%%%%%%%%%%%%

\begin{table}[tp] \begin{center}
\begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Compactification$+$Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&47&10&0.05&39&12&0.1&17\\
50&20&48&21&0.05&48&23&0.1&0\\
50&30&57&63&0.06&57&43&0.12&0\\
50&40&74&66&0.06&74&67&0.14&0\\
50&50&111&83&0.09&109&84&0.14&2\\
50&60&116&90&0.09&43&62&0.14&63\\
50&70&124&95&0.1&32&58&0.12&74\\
50&80&120&97&0.1&15&60&0.1&88\\
50&90&85&98&0.08&3&3&0.1&96\\
\hline \end{tabular}

\medskip \centerline{(a) 1 application of Struction /
Compactification $+$ Guided Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Compactification$+$Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&42&10&0.06&19&11&0.1&55\\
50&20&69&44&0.07&68&45&0.13&1\\
50&30&103&77&0.07&44&44&0.12&57\\
50&40&461&98&0.13&52&55&0.1&89\\
50&50&642&99&0.2&30&65&0.09&95\\
50&60&430&99&0.18&9&25&0.07&98\\
50&70&243&99&0.15&5&0&0.05&98\\
50&80&81&99&0.06&2&0&0.05&98\\
50&90&4&1&0&0&0&0.05&100\\
\hline \end{tabular}

\medskip \centerline{(b) 3 consecutive applications of Struction
/ Compactification $+$ Guided Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Compactification$+$Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&39&12&0.06&16&0&0.05&59\\
50&20&50&40&0.07&45&40&0.1&10\\
50&30&178&93&0.18&40&46&0.1&78\\
50&40&874&99&0.23&42&58&0.1&95\\
50&50&399&99&0.14&6&67&0.08&98\\
50&60&101&99&0.18&6&0&0.06&94\\
50&70&12&98&0.15&3&0&0.05&75\\
50&80&0&0&0.05&0&0&0.05&N/A\\
50&90&0&0&0&0&0&0.05&N/A\\
\hline \end{tabular}

\medskip \centerline{(c) 5 consecutive applications of Struction
/ Compactification $+$ Guided Struction}

\end{center} \caption{Uniformly Randomly Generated Graphs}
\end{table}

%%%%%%%%%%%%% Table 4 %%%%%%%%%%%%%%%%%%

\begin{table}[tp] \begin{center}
\begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Compactification$+$Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&47&10&0.001&28&1&0.001&40\\
50&20&46&21&0.001&22&8&0.001&52\\
50&30&51&48&0.004&19&0&0.002&63\\
50&40&39&30&0.004&15&1&0.001&62\\
50&50&40&40&0.003&18&8&0.001&55\\
50&60&39&53&0.003&13&3&0.001&67\\
50&70&35&61&0.002&10&8&0.001&71\\
50&80&22&51&0.001&9&0&0.001&59\\
50&90&18&61&0.001&5&0&0.001&72\\
\hline \end{tabular}

\medskip \centerline{(a) 1 application of Struction /
Compactification $+$ Guided Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Compactification$+$Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&40&8&0.002&26&0&0.001&35\\
50&20&41&20&0.001&20&0&0.001&51\\
50&30&36&25&0.004&16&0&0.002&56\\
50&40&32&26&0.002&16&14&0.001&50\\
50&50&30&33&0.003&13&0&0.001&57\\
50&60&28&48&0.003&9&0&0.001&68\\
50&70&18&36&0.002&9&0&0.001&50\\
50&80&10&24&0.001&7&0&0.001&30\\
50&90&6&0&0.001&6&0&0.001&0\\
\hline \end{tabular}

\medskip \centerline{(b) 3 consecutive applications of Struction
/ Compactification $+$ Guided Struction}

\bigskip \begin{tabular}{|c|c||c|c|c||c|c|c||c|} \hline
\multicolumn{2}{|c||}{\tiny Initial Graph}&
\multicolumn{3}{c||}{\tiny Struction}& \multicolumn{3}{c||}{\tiny
Compactification$+$Guided Struction}&
{\tiny Vertex Set}\\
\cline{1-8}
{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny \# Vertices}&{\tiny Density (\%)}&{\tiny Time (s)}&{\tiny Reduction (\%)}\\
\hline
50&10&34&6&0.002&22&0&0.001&35\\
50&20&31&10&0.001&20&0&0.001&35\\
50&30&23&9&0.004&15&0&0.002&35\\
50&40&26&32&0.002&11&0&0.001&58\\
50&50&21&25&0.003&10&0&0.001&52\\
50&60&43&35&0.003&8&0&0.001&81\\
50&70&10&31&0.002&5&0&0.001&50\\
50&80&9&0&0.001&4&0&0.001&56\\
50&90&1&0&0.001&1&0&0.001&0\\
\hline \end{tabular}

\medskip \centerline{(c) 5 consecutive applications of Struction
/ Compactification $+$ Guided Struction}

\end{center} \caption{Non-Uniformly Randomly Generated Graphs}
\end{table}


\textit{Experiment 1}. In this experiment, we have compared the
number of vertices of the graphs obtained in two alternative
ways. In the first alternative, we have simply applied struction
using as center a vertex which insures the smallest increase of
the number of vertices in the resulting
graphs, but have not included the stability preserving
transformations used in guided struction. This alternative was
compared with guided struction. We report in Tables 1(a) and 2(a)
the results of these experiments, applied to 27 uniformly and 27
non-uniformly generated graphs (3 graphs for each of the 9
density levels). It can be seen that the number of vertices of
$G^{\prime } $ when guided struction is applied to uniform graphs
of density exceeding 70\% is reduced by 36\% compared to the
number vertices obtained by applying struction. In the case of
non-uniformly generated graphs, the reductions in the size of
$V(G^{\prime })$ average 24\% and are significant for all the
tested graphs with densities exceeding 40\%. It can also be
seen that the total time needed for carrying out the guided
struction in the uniform case is under 0.2 sec., and is even
smaller in the non-uniform case.

\newpage

In Tables 1(b) and 2(b) we have repeated the above experiments,
applying them 3 times: first to a series of randomly generated
graphs $G_{i},$ then to the graphs $G_{i}^{\prime }$ obtained by
applying struction or guided
struction to the graphs $G_{i},$ and finally to the resulting graphs $%
G_{i}^{\prime \prime}.$ Here too, these experiments, were applied
to two groups of 27 graphs each, obtained similarly to those
presented above. It can be seen that the reduction in the size of
$V(G_{i}^{\prime \prime \prime })$ obtained by guided struction,
averages 48.5\% the graphs $G_{i}$ of high density, being lower
for the non-uniformly, and higher for the uniformly generated
graphs. The average computing time for executing guided struction
is less than 0.2 sec.

In Tables 1(c) and 2(c) we report the results of applying 5 times
struction, respectively guided struction. This time, it can be
seen that the average reduction in the size of the vertex set is
of 57\%, being somewhat lower in the case of non-uniform graphs
and higher in the case of uniform graphs. The average computing
time is of less than 0.2 sec.

In conclusion, it appears that the sequential application of
guided struction can be achieved with minimal computational
effort and results in substantially smaller transformed graphs
than those obtained by simply applying the struction method.

\textit{Experiment }2 differs from Experiment 1 by the fact that
the simple application of struction was compared with the
combined application of compactification, followed by guided
struction. In this case, it can be seen from Tables 3 and 4 (a -
c) that the sizes of the vertex sets obtained through
compactification + guided struction are on the average 67\% less
than those obtained by using the simple struction method for
graphs with densities exceeding 40\%, and that the necessary
computing time for compactification and guided struction never
exceeded 0.25 sec and was usually much lower.

Successful experiments are currently in progress for applying
more complex struction-based algorithms for computing the
stability number of graphs with hundreds and even thousands of
vertices. While the experiments reported in this paper
involve relatively small graphs, they clearly show that
compactification and guided struction offer substantial
improvements of the method, and have the potential of extending
its applicability to much larger categories of graphs.


\begin{thebibliography}{99} \bibitem{Ale83} V.E. Alekseev, On the
local restrictions effect on the complexity of finding the graph
independence number, Combinatorial-algebraic methods in applied
mathematics, Gorkiy Univ. Press, Gorkiy, (1983) 3-13 (in Russian).

\bibitem{Ale99} V.E. Alekseev, A polynomial algorithm for finding
maximum independent sets in fork-free graphs, Discrete Analysis
and Operations Research, Ser. 1, Vol. 6 (1999), no. 4, 3--19.

\bibitem{BH99} A. Brandst\"adt and P.L. Hammer, On the stability
number of claw-free $P_5$-free and more general graphs, Discrete
Applied Math. 95 (1999) 163-1667.

\bibitem{BHH85}  L. Butz, P.L. Hammer and D. Haussmann, Reduction
methods for the vertex packing problem, \textit{Proceedings of
the 17th Conference on Probability Theory} (Brasov 1982), 73-79,
VNU Sci. Press, Utrecht, 1985.

\bibitem{CKJ99} J. Chen, I. A. Kanj, and W. Jia, Vertex Cover:
Further Observations and Further Improvements, Journal of
Algorithms 41 (2001) 280-301.

\bibitem{CHJ90} Y. Crama, P. Hansen and B. Jaumard, The basic
algorithm for pseudo-Boolean programming revisited, Discrete
Applied Math. 29 (1990) 171-185.

\bibitem{SS93} C. De Simone and A. Sassano, Stability number of
bull- and chair-free graphs, Discrete Applied Math. 41 (1993),
121-129.



\bibitem{DeW84} D. de Werra, On some properties of the struction
of the graph, SIAM J. Alg. Disc. Meth. 5 (1984) 239-243.

\bibitem{Edm65}

J. Edmonds, Path, trees, and flowers, Canad. J. Math. 17 (1965),
449-447.

\bibitem{EHW84} Ch. Ebenegger, P.L. Hammer and D. de Werra,
Pseudo-Boolean functions and stability of graphs, Ann. Discrete
Math. 19 (1984), 83-98.

\bibitem{FHT93} M. Farber, M. Hujter and Zs. Tuza, An upper bound
on the number of cliques in a graph, Networks 23 (1993), 207-210.


\bibitem{GL02} M.U. Gerber and V.V. Lozin, On the stable set
problem in special $P_5$-free graphs, Discrete Applied Math. 125
(2003) 215-224.

\bibitem{Gol80} M.C. Golumbic, Algorithmic graph theory and
perfect graphs, Academic Press, New York, 1980.

\bibitem{GH88} M.C. Golumbic and P.L. Hammer, Stability in
circular-arc graphs, J. Algorithms 9 (1988), 314-320.


\bibitem{HMW85a} P.L.Hammer, N.V.R. Mahadev and D. de Werra,
Stability in CAN-free graphs, J. Combin. Theory B 38 (1985),
23-30.

\bibitem{HMW85b} P.L. Hammer, N.V.R. Mahadev and D. de Werra, The
struction of a graph: Application to CN-free graphs,
Combinatorica 5 (1985), 141-147.

\bibitem{HH91} P.L. Hammer and A. Hertz, On a transformation
which preserves the stability number, RUTCOR Research Report
69-91, Rutgers University, (1991).

\bibitem{Her86} A. Hertz, Quelques utilisations de la struction,
Discrete Math. 59 (1986) 79-89.

\bibitem{Her95} A. Hertz, Polynomially solvable cases for the
maximum stable set problem, Discrete Applied Math. 60 (1995),
195-210.

\bibitem{Her97} A. Hertz, On the use of Boolean methods for the
computation of the stability number, Discrete Applied Math. 76
(1997), 183-203.

\bibitem{Her00} A. Hertz, On a transformation which preserves the
stability number, Yugoslav Journal of Operations Research, 10/1
(2000) 1-12.

\bibitem{HW93} A. Hertz and D. de Werra, On the stability number
of AH-free graphs, J. Graph Theory 17 (1993), 53-63.

\bibitem{HT94} K.W. Hoke and M.F. Troyon, The struction algorithm
for the maximum stable set problem revisited, Discrete Math. 131
(1994), 105-113.

\bibitem{LP86} L. Lov\'asz and M.D. Plummer, Matching theory,
Ann. Discrete Math. 29 (1986).

\bibitem{Loz00} V.V. Lozin, Stability in $P_5$- and banner-free
graphs, European journal for Operational Research, 125 (2000).

\bibitem{Loz00b} V.V. Lozin, Conic reduction of graphs for the
stable set problem, Discrete Mathematics, 222 (2000) 199-211.

\bibitem{MS96} C. Mannino and A. Sassano, Edge projection and the
maximum cardinality stable set problem, DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, 26 (1996) 205-219.

\bibitem{MS99}

C. Mannino and E. Stefanutti, An augmentation algorithm for the
maximum weighted stable set problem, Computational Optimization
and Applications, 14 (1999) 367-381.


%\bibitem{Min}
%G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J.
%Combin. Theory B 28 (1980), 284-304.

\bibitem{Mos97} R.Mosca, Polynomial algorithms for the maximum
stable set problem on particular classes of $P_5$-free graphs,
Information Processing Letters, 61 (1997), 137-144.


%\bibitem{Sbi}
%N. Sbihi, Algorithme de recherche d\'un stable de cardinalit\'e maximum dans
%un graphe sans \'etoile, Discrete Math. 29 (1980), 53-76.

\bibitem{TIAS97} S. Tsukiyama, M. Ide, H. Ariyoshi and I.
Shirakawa, A new algorithm for generating all the maximal
independent sets, SIAM J. Computing 6 (1977), 505-517

\end{thebibliography}
\end{document}