# Independent sets

*Graphs.jl* contains functions related to independent sets.

## Index

## Full docs

`Graphs.independent_set`

— Method`independent_set(g, DegreeIndependentSet())`

Obtain an independent set of `g`

using a greedy heuristic based on the degree of the vertices.

**Implementation Notes**

A vertex is said to be valid if it is not in the independent set or adjacent to any vertex in the independent set. Initilalise the independent set to an empty set and iteratively choose the vertex that is adjacent to the fewest valid vertices in the independent set until all vertices are invalid.

**Performance**

Runtime: O((|V|+|E|)*log(|V|)) Memory: O(|V|)

`Graphs.independent_set`

— Method`independent_set(g, MaximalIndependentSet(); rng=nothing, seed=nothing)`

Find a random set of vertices that are independent (no two vertices are adjacent to each other) and it is not possible to insert a vertex into the set without sacrificing the independence property.

**Implementation Notes**

Performs Approximate Maximum Independent Set once. Returns a vector of vertices representing the vertices in the independent set.

**Performance**

Runtime: O(|V|+|E|) Memory: O(|V|) Approximation Factor: maximum(degree(g))+1

**Optional Arguments**

`rng=nothing`

: set the Random Number Generator.- If
`seed >= 0`

, a random generator is seeded with this value.