AI Glossary / Graphs and symbolic AI / Beginner
Maximal independent set
Definition
A maximal independent set is a set of graph nodes with no edges between selected nodes, to which no additional node can be added without creating an edge inside the set. “Maximal” means the set cannot be extended by adding nodes. It does not mean that it contains the largest possible number of nodes.
What it means
Imagine several jobs, with an edge between two jobs whenever they cannot run together. An independent set is a compatible collection. A maximal independent set is a collection that has no room for another currently unselected job, given the jobs already chosen.
There may still be a larger compatible collection if some chosen jobs are replaced. That distinction separates maximal from maximum. Every maximum independent set is maximal, but a maximal independent set can be much smaller than the maximum. The distinction matters whenever “we cannot add anything else” is mistakenly interpreted as “we found the best solution.”
How it works
For a simple undirected graph, one construction starts with an empty independent set. Choose an eligible node, add it, and remove that node and its neighbors from the eligible candidates. Continue until no candidates remain. Each selected node is compatible with those already selected, and every excluded node has a selected neighbor when the procedure finishes.
Different choices can produce different maximal sets. A predetermined independent starting set can be extended in the same way, but incompatible required starting nodes cannot form a valid independent set.
NetworkX provides a randomized maximal_independent_set routine with an optional starting node set and random seed. Its documentation explicitly distinguishes this task from finding a maximum independent set. This entry uses the standard simple, undirected, loop-free graph setting; directed conflicts or self-conflicts require clearly specified modeling rules.
Three practical examples
- Batch scheduling: select a group of jobs with pairwise resource conflicts represented by edges, then stop when no further job fits the selected group.
- Wireless planning: form a set of transmissions without modeled pairwise interference, recognizing that actual interference may require a richer model.
- Review sampling: select mutually nonadjacent representatives in a similarity graph, where edges represent a chosen threshold of excessive similarity.
Think of it this way
Think of seating guests who must not share a table with certain other guests. A table is maximal when every remaining guest conflicts with someone already seated. Another seating arrangement might accommodate more people.
The analogy is limited to pairwise conflicts. Constraints such as a table-wide noise limit or a total weight limit cannot necessarily be represented by drawing edges between individual pairs alone.
Worked example
Build a star graph with center H and leaves A, B, C, and D. Connect H to each leaf and include no edges between leaves. Add a separate isolated node E.
If the construction selects H first, it excludes A, B, C, and D. It can still add E, producing {H,E}, an independent set of size 2. This set is maximal because every unselected leaf touches H. The singleton {H} is not maximal: E could still be added.
Alternatively, select the four leaves and E, producing {A,B,C,D,E}, of size 5. No selected pair is connected, and the only omitted node H conflicts with the leaves. This set is also maximal and is maximum: choosing H rules out all four leaves, while omitting H allows at most the five other nodes. Thus the two maximal sets have sizes 2 and 5. The first is not wrong for a maximal-set task, but it does not solve the largest-set objective.
Illustrative case study
Fictional case: a testing laboratory uses a conflict graph to create a batch of instrument jobs. A developer returns a maximal independent set and labels the result “maximum available throughput.” An operations reviewer finds an alternative batch with more jobs.
The team corrects the description and decides whether a quick valid batch is sufficient for the workflow. For periods when utilization matters more, it evaluates a method aimed at a larger or more valuable independent set. It also checks whether shared capacity limits extend beyond pairwise conflicts. The fictional case illustrates an objective mismatch, not a measured improvement in laboratory throughput.
Common misconceptions and mistakes
Do not confuse maximal with maximum, independent with disconnected, or nodes with edges. An independent set contains no internal edge at all; a disconnected induced subgraph may still contain edges within its components. A matching is a set of non-touching edges, which is a different graph object.
Size is not value. A large set of low-priority jobs may be less useful than a smaller high-priority set. Nor does repeating a randomized maximal-set procedure prove optimality, even if the best observed size stops improving. A certificate of maximality only shows that no single additional node fits the current selection.
Business use
A maximal independent set can offer a practical stopping condition when a team needs one feasible, non-extendable collection quickly. The choice is appropriate only if the graph faithfully describes the compatibility requirement and the business objective does not demand global optimality.
Record the selected nodes, reasons excluded nodes conflict, any required starting nodes, and the selection procedure. If priorities or costs matter, state the objective explicitly and choose an appropriate weighted or constrained formulation. Report a heuristic result as a feasible selection rather than implying that no better replacement arrangement exists.
People also ask
Can there be several maximal independent sets?
Yes. Their membership and sizes can differ, as the star example shows.
Must every isolated node be included?
Yes, in a maximal independent set of a simple loop-free graph, because an omitted isolated node could always be added.
Can a maximal set become larger by replacing nodes?
Yes. Maximality forbids additions while keeping the current selection; it does not rule out beneficial exchanges.
Check your understanding
in the worked graph, is {A,B,C,D} maximal?
Answer: no. Although the four leaves are mutually independent, isolated E can still be added. Adding E produces the size-5 maximum independent set, which is necessarily also maximal.
Related terms
- Graph coloring
- Greedy algorithms
- Independent set
- maximum independent set
- conflict graph
- matching
- clique
- dominating set
- greedy algorithm
- combinatorial optimization
Learn next
draw a small conflict graph and verify a proposed set in two stages: first check that no selected pair shares an edge, then check that every omitted node has a selected neighbor. Compare this certificate of maximality with the stronger reasoning needed to prove maximum size.
More in Graphs and symbolic AI
- Markov chain Monte Carlo - Markov chain Monte Carlo, or MCMC, is a family of methods for estimating quantities from a probability distribution by generating a dependent sequence of...
- Markov network - A Markov network is a probabilistic graphical model that uses an undirected graph to represent relationships among variables.
- Markov reward process - A Markov reward process, or MRP, is a Markov state-transition model equipped with rewards.
- Maximin - Maximin is a decision rule that chooses the option with the best worst-case payoff.
- Maximin equilibrium - In the standard two-player zero-sum setting, a maximin equilibrium is a pair of strategies in which each player secures the best worst-case expected payoff...
- Maximum a posteriori - Maximum a posteriori, usually abbreviated MAP, selects a value or hypothesis that maximizes its posterior probability after evidence is observed.
Sources
NetworkX, maximal_independent_set API documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.mis.maximal_independent_set.html. The primary documentation's definition, starting-set requirements, randomization, and maximum-versus-maximal distinction were read. No library execution is claimed; the star graph and its optimality argument are original, directly checked examples.
Previous: Maximal entropy random walk Next: Maximin