Maximal Independent Set Example

Abstract

Given an undirected graph with nodes representing people, and an edge between $A$ and $B$ if $A$ and $B$ are enemies, find the largest set of people such that no two are enemies. In other words: given an undirected graph, find the largest set of vertices such that no two are connected by an edge.

• Category: Backtracking / Graph Optimization (NP-Hard)
• Input: An undirected graph $G$
• Output: The largest independent set of $G$
• Paradigm: Backtracking — branch on “include this vertex or not,” recursively, refined over three iterations below
• Typical use cases: scheduling/conflict-avoidance problems, the canonical example of squeezing a much better exponential base out of brute-force backtracking via case analysis

---

Problem Specification

• Instance: Undirected graph $G$.
• Solution Format: Subset of vertices.
• Constraint: No two vertices in the subset are connected by an edge.
• Objective: Maximize the size of the subset.
• Goal: Maximize.

---

Candidate Strategies / Approaches

Backtracking approach: do exhaustive search locally, but use the constraints to simplify the problem as you go.

• What is a local decision? Do we pick vertex $A$ or not?
• What are the possible answers to this decision? Yes or no.
• How do the answers affect the future of the problem?
  • If we pick $A$: recurse on the subgraph $G-(A\cup A\text{’s neighbors})$, and add 1 for $A$ (since none of $A$‘s neighbors can ever be picked alongside $A$).
  • If we don’t pick $A$: recurse on the subgraph $G-A$.

This one branching rule is the seed for all three algorithm versions below — what changes across MIS1 → MIS2 → MIS3 is when it’s safe to skip computing one of the two branches entirely.

---

Algorithm Iterations

MIS1 — Naive Backtracking

Algorithm 2 Maximal Independent Set

procedure MIS1($G: \text{undirected graph}$)

if $|V| = 0$ then

return $\emptyset$

Pick a vertex $v$

In = $MIS1(G - \{ v \text{ and all of } v \text{'s neighbors} \} \cup \{v\})$

Out = $MIS1(G - \{v\})$

if $|\text{In}| > |\text{Out}|$ then

return In

else

return Out

Correctness

• Base Case ($n=0$): MIS1 correctly returns the empty set.
• Inductive Hypothesis: for $n>0$, MIS1 correctly returns the maximum independent set of any graph with $k$ vertices, for $1\le k<n$.
• Argument: In is the best independent set containing $v$; Out is the best independent set not containing $v$. Every independent set either contains $v$ or doesn’t, so the better of the two is the true maximum independent set of $G$.

Time Analysis

Both In and Out cost $T(n-1)$ in the worst case (In removes at least $v$ itself — possibly more if $v$ has neighbors, but the worst case for the bound is when $v$ has no neighbors and only 1 vertex is removed; Out always removes exactly $v$):

$T(n)\le 2T(n-1)+O(n)⟹T(n)\in O(2^n)$

Worst Case for MIS1

When you pick a vertex $v$ with no neighbors, the In subproblem only decreases by 1 (same as Out) — but do we actually need to consider Out at all in that case? Shouldn’t we just pick $v$? More generally: if a vertex $v$ has no neighbors, the In case is always at least as good as the Out case — including an isolated vertex can never conflict with anything else, so there’s no reason to ever leave it out.

---

MIS2 — Skip Out When $\mathrm{deg}(v)=0$

Algorithm 3 Maximal Independent Set

procedure MIS2($G: \text{undirected graph}$)

if $|V| = 0$ then

return $\emptyset$

Pick a vertex $v$

In = $MIS2(G - \{ v \text{ and all of } v \text{'s neighbors} \} \cup \{v\})$

if $deg(v) == 0$ then

return In

Out = $MIS2(G - \{v\})$

if $|\text{In}| > |\text{Out}|$ then

return In

else

return Out

Time Analysis

$$\begin{array}{rl}T(n)& =\max (T(n-1),T(n-1)+T(n-2)+O(n))\\ T(n)& =T(n-1)+T(n-2)+O(n)\\ T(n)& \in O(1.62^n)\ll O(2^n)\end{array}$$

(This is exactly the Fibonacci recurrence — $1.62\approx \phi$, the golden ratio.) A huge improvement from the initial approach.

Worst Case for MIS2

When you pick a vertex $v$ with exactly one neighbor, the In subproblem only decreases by 2 (removing $v$ and its one neighbor) — but do we actually need to consider Out here either? Shouldn’t we just pick $v$? More generally: if a vertex $v$ has one neighbor, the In case is always at least as good as the Out case. This one takes a bit more convincing than the degree-0 case.

Claim: suppose $v$ is a vertex of $G$ with only one neighbor, $u$. Suppose $OS$ is an independent set that does not include $v$. There is an independent set $O{S}^{\prime }$ that does include $v$, with $|O{S}^{\prime }|\ge |OS|$.

Proof: consider two cases based on whether $OS$ contains $u$ (v’s only neighbor):

• Case 1 — $OS$ does not contain $u$: let $O{S}^{\prime }=OS\cup v$. Since $OS$ doesn’t contain $v$‘s only neighbor, adding $v$ can’t create a conflict, so $O{S}^{\prime }$ is valid, and $|O{S}^{\prime }|=|OS|+1$.
• Case 2 — $OS$ contains $u$: let $O{S}^{\prime }=(OS-u)\cup v$. $O{S}^{\prime }$ no longer contains $v$‘s only neighbor, so by the validity of $OS$ elsewhere, $O{S}^{\prime }$ is valid, and $|O{S}^{\prime }|=|OS|$.

Either way, $|O{S}^{\prime }|\ge |OS|$, so including $v$ is never worse than excluding it.

---

MIS3 — Also Skip Out When $\mathrm{deg}(v)=1$

Algorithm 4 Maximal Independent Set

procedure MIS3($G: \text{undirected graph}$)

if $|V| = 0$ then

return $\emptyset$

Pick a vertex $v$

In = $MIS3(G - \{ v \text{ and all of } v \text{'s neighbors} \} \cup \{v\})$

if $deg(v) == 0$ or $deg(v) == 1$ then

return In

Out = $MIS3(G - \{v\})$

if $|\text{In}| > |\text{Out}|$ then

return In

else

return Out

Time Analysis

$$\begin{array}{rl}T(n)& =T(n-1)+T(n-3)+O(n)\\ & \in O(1.48^n)\end{array}$$

---

Time & Space Complexity Analysis

Summary Across Iterations

Version	Skips Out when	Recurrence	Bound
MIS1	Never	$T(n)=2T(n-1)+O(n)$	$O(2^n)$
MIS2	$\mathrm{deg}(v)=0$	$T(n)=T(n-1)+T(n-2)+O(n)$	$O(1.62^n)$
MIS3	$\mathrm{deg}(v)\in 0,1$	$T(n)=T(n-1)+T(n-3)+O(n)$	$O(1.48^n)$

The pattern is clear: proving that low-degree vertices are always safe to include (never worse than excluding) lets you skip computing an entire recursive branch for them, and handling more and more low-degree cases keeps shrinking the exponential base. The best known MIS algorithm is around $O(1.2^n)$, due to Robson, building on Tarjan and Trojanowski — it does much more elaborate case analysis for small-degree vertices, following exactly this same pattern to its logical extreme.

Space

Each version’s space is dominated by recursion depth, which is $O(n)$ in the worst case (one vertex removed per level in the shallowest branch).

---

Drawbacks / Constraints

• Still exponential. Maximal (maximum) Independent Set is NP-hard, so no polynomial-time algorithm is expected for the general case, no matter how much low-degree case analysis is added.
• Diminishing returns, rapidly increasing complexity. Going from MIS1 → MIS2 → MIS3 required proving a genuine exchange-argument-style claim just to handle degree-1 vertices; Robson’s $O(1.2^n)$ result needs “much more elaborate case analysis” for small-degree vertices, illustrating that each further improvement costs substantially more implementation and proof effort for a shrinking marginal gain.
• Only helps low-degree vertices. This whole line of refinement exploits the fact that a low-degree vertex barely shrinks the graph on the Out branch — it doesn’t directly help with dense graphs where most vertices have high degree.

Toward Dynamic Programming

Each MIS call recurses on an induced subgraph obtained by deleting a small set of vertices — but which specific subgraph you get depends on the sequence of choices made to get there, so in general graphs there’s no small, reusable set of subproblems to memoize. This is exactly the boundary case that makes Dynamic Programming work beautifully on some backtracking problems (where subproblems collapse to a polynomial-size, reusable set — e.g. “the best solution using only elements $\mathrm{1..}i$”) but not on others like general-graph MIS, where the reachable subgraphs don’t collapse that way.

The exception that proves the rule: restrict the input to a tree, and the subproblems do collapse — each vertex’s subtree is a clean, reusable subproblem, since subtrees never overlap. See Maximum Independent Set in Trees for the resulting $O(n)$ DP solution, a direct contrast to this note’s exponential general-graph result.

---

References / Links

• Backtracking
• Dynamic Programming