max_independent_vertex_set

max_independent_vertex_set#

graph_tool.topology.max_independent_vertex_set(g, high_deg=False, mivs=None)[source]#

Find a maximal independent vertex set in the graph.

Parameters:
gGraph

Graph to be used.

high_degbool (optional, default: False)

If True, vertices with high degree will be included first in the set, otherwise they will be included last.

mivsVertexPropertyMap (optional, default: None)

Vertex property map where the vertex set will be specified.

Returns:
mivsVertexPropertyMap

Boolean vertex property map where the set is specified.

Notes

A maximal independent vertex set is an independent set such that adding any other vertex to the set forces the set to contain an edge between two vertices of the set.

This implements the algorithm described in [mivs-luby], which runs in time \(O(V + E)\).

References

[mivs-luby]

Luby, M., “A simple parallel algorithm for the maximal independent set problem”, Proc. 17th Symposium on Theory of Computing, Association for Computing Machinery, pp. 1-10, (1985) DOI: 10.1145/22145.22146 [sci-hub, @tor].

Examples

>>> g = gt.GraphView(gt.price_network(300), directed=False)
>>> res = gt.max_independent_vertex_set(g)
>>> gt.graph_draw(g, vertex_fill_color=res, output="mivs.pdf")
<...>
../_images/mivs.png

Vertices belonging to the set are in yellow.#

Contents