\HeaderA{independent.vertex.sets}{Independent vertex sets}{independent.vertex.sets}
\aliasA{independence.number}{independent.vertex.sets}{independence.number}
\aliasA{largest.independent.vertex.sets}{independent.vertex.sets}{largest.independent.vertex.sets}
\aliasA{maximal.independent.vertex.sets}{independent.vertex.sets}{maximal.independent.vertex.sets}
\keyword{graphs}{independent.vertex.sets}
\begin{Description}\relax
A vertex set is called independent if there no edges
between any two vertices in it. These functions find independent
vertex sets in undirected graphs
\end{Description}
\begin{Usage}
\begin{verbatim}
independent.vertex.sets(graph, min=NULL, max=NULL)
largest.independent.vertex.sets(graph)
maximal.independent.vertex.sets(graph)
independence.number(graph)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The input graph, directed graphs are considered as
undirected, loop edges and multiple edges are ignored.
\item[\code{min}] Numeric constant, limit for the minimum size of the
independent vertex sets to find. \code{NULL} means no limit.
\item[\code{max}] Numeric constant, limit for the maximum size of
the independent vertex sets to find. \code{NULL} means no limit.

\end{ldescription}
\end{Arguments}
\begin{Details}\relax
\code{independent.vertex.sets} finds all independent vertex sets in
the network, obeying the size limitations given in the \code{min} and
\code{max} arguments.

\code{largest.independent.vertex.sets} finds the largest independent
vertex sets in the graph. An independent vertex set is largest if
there is no independent vertex set with more vertices.

\code{maximal.independent.vertex.sets} finds the maximal independent
vertex sets in the graph. An independent vertex set is maximal if it
cannot be extended to a larger independent vertex set. The largest
independent vertex sets are maximal, but the opposite is not always
true.

\code{independece.number} calculate the size of the largest
independent vertex set(s).

These functions use the algorithm described by Tsukiyama et al., see
reference below.
\end{Details}
\begin{Value}
\code{independent.vertex.sets}, \code{largest.independent.vertex.sets}
and \code{maximal.independent.vertex.sets} return a list containing
numeric vertex ids, each list element is an independent vertex set.

\code{independence.number} returns an integer constant.
\end{Value}
\begin{Author}\relax
Tamas Nepusz \email{ntamas@rmki.kfki.hu} ported it from the Very
Nauty Graph Library by Keith Briggs \email{google@for.it} and Gabor Csardi
\email{csardi@rmki.kfki.hu} wrote the R interface and this manual page.
\end{Author}
\begin{References}\relax
S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm
for generating all the maximal independent sets. \emph{SIAM J Computing},
6:505--517, 1977.
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{cliques}{cliques}}
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
# A quite dense graph
g <- erdos.renyi.game(100, 0.8)
independence.number(g)
independent.vertex.sets(g, min=independence.number(g))
largest.independent.vertex.sets(g)
# Empty graph
subgraph(g, largest.independent.vertex.sets(g)[[1]])

length(maximal.independent.vertex.sets(g))
\end{ExampleCode}
\end{Examples}

