Maximal Independent Set

Supported Graph Characteristics

Undirected edges

Homogeneous vertex types

Algorithm links: Maximal Independent Set (contains links to all algorithm variants)

An independent set of vertices does not contain any pair of vertices that are neighbors, i.e., ones which have an edge between them. A maximal independent set (MIS) is the largest independent set that contains those vertices; you cannot improve upon it unless you start over with a different independent set. However, the search for the largest possible independent set is an NP-hard problem: there is no known algorithm that can find that answer in polynomial time. So we settle for the maximal independent set.

This algorithm finds use in applications wanting to find the most efficient configuration which "covers" all the necessary cases. For example, it has been used to optimize delivery or transit routes, where each vertex is one transit segment and each edge connects two segments that can not be covered by the same vehicle.

Since there could be multiple maximal independent sets, there are two versions of the Maximal Independent Set algorithm:

Deterministic. The deterministic version makes sure that you get the same results every time.
Randomized. The randomized version can produce different results every time you run it. The random version requires a user-defined function (UDF). See Query User-Defined Functions for how to add a UDF.

Notes

This algorithm ignores edge weights.

Specifications

Deterministic MIS

tg_maximal_indep_set(STRING v_type, STRING e_type,
INT max_iter = 100, BOOL print_accum = TRUE, STRING file_path = "")

Randomized MIS

tg_maximal_indep_set_random(STRING v_type, STRING e_type,
    INT max_iter = 100, BOOL print_accum = TRUE, STRING file_path = "")

Parameters

Parameter Description Default Value

Parameter	Description	Default Value
`STRING v_type`	The vertex type to use	(empty string)
`STRING e_type`	The edge type to use	(empty string)
`INT max_iter`	The number of nearest neighbors to consider	N/A
`BOOL print_accum`	If true, print output in JSON format to the standard output.	True
`STRING file_path`	If not empty, write output to this file.	(empty string)

STRING v_type

The vertex type to use

(empty string)

STRING e_type

The edge type to use

(empty string)

INT max_iter

The number of nearest neighbors to consider

N/A

BOOL print_accum

If true, print output in JSON format to the standard output.

True

STRING file_path

If not empty, write output to this file.

(empty string)

Output

Returns a set of vertices that form a maximal independent set.

If the graph is a set of N unconnected vertices, then the maximal independent set is all N vertices.

Time complexity

This algorithm has a complexity of \$O(E)\$, where \$E\$ is the number of edges.

Example

Consider our social10 graph, with three components.

It is clear that for each of the two triangles — (Alex, Bob, Justin) and (Chase, Damon, Eddie) — we can select one vertex from each triangle to be part of the MIS.

For the 4-vertex component (Fiona, George, Howard, Ivy), it is less clear what will happen. If the algorithm selects either George or Ivy, then no other independent vertices remain in the component. However, the algorithm could select both Fiona and Howard; they are independent of one another.

This demonstrates the uncertainty of the Maximal Independent Set algorithm and how it differs from Maximum Independent Set. A maximum independent set algorithm would always select Fiona and Howard, plus 2 others, for a total of 4 vertices. The maximal independent set algorithm relies on chance. It could return either 3 or 4 vertices.