independent.vertex.sets {igraph} | R Documentation

## Independent vertex sets

### Description

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

### Usage

    independent.vertex.sets(graph, min=NULL, max=NULL)
    largest.independent.vertex.sets(graph)
    maximal.independent.vertex.sets(graph)
    independence.number(graph)

### Arguments

`graph` | The input graph, directed graphs are considered as undirected, loop edges and multiple edges are ignored.
`min` | Numeric constant, limit for the minimum size of the independent vertex sets to find. `NULL` means no limit.
`max` | Numeric constant, limit for the maximum size of the independent vertex sets to find. `NULL` means no limit.

### Details

`independent.vertex.sets` finds all independent vertex sets in the network, obeying the size limitations given in the `min` and `max` arguments.

`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.

`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.

`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.

### Value

`independent.vertex.sets`, `largest.independent.vertex.sets` and `maximal.independent.vertex.sets` return a list containing numeric vertex ids, each list element is an independent vertex set.
`independence.number` returns an integer constant.

### Author(s)

Tamas Nepusz ntamas@rmki.kfki.hu ported it from the Very Nauty Graph Library by Keith Briggs google@for.it and Gabor Csardi csardi@rmki.kfki.hu wrote the R interface and this manual page.

### References

S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505–517, 1977.

### See Also

`cliques`

### Examples

    # 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))

[Package igraph version 0.5.2 Index]