What Is an Independent Set? The Graph Concept Behind House Robber
- Independent set in graph theory: a vertex subset where no two chosen vertices share an edge; maximum independent set is NP-hard on arbitrary graphs
- Tree DP: the include/exclude recurrence solves maximum weighted independent set on trees in O(n) time and O(h) stack space
- König's theorem: on bipartite graphs, maximum independent set equals n minus maximum matching, solvable in polynomial time via Hopcroft-Karp
- House Robber (LeetCode 198 and 337) is maximum weight independent set on a path or binary tree, reducing to rolling DP or tree DP
- Complement duality: an independent set in G is a clique in the complement graph; vertex cover and independent set are complements in the vertex set
- Interview signal: phrases like "no two adjacent" or "maximize with no consecutive picks" encode the independent set constraint
"No two adjacent houses." You've seen it a hundred times. Write the DP, return prev1, close the tab. Two minutes. Done.
Then an interviewer asks how you'd generalize this to an arbitrary graph, and you stare at the screen like someone switched the language to Brainfuck mid-problem.
Same problem. Different name. House Robber is maximum weight independent set on a path graph, and once you know that, every "no two adjacent X" variant becomes instantly recognizable. You stop reinventing the wheel and start matching patterns.
What Makes a Set Independent
In G = (V, E), an independent set S ⊆ V satisfies one constraint: for every u, v ∈ S, the edge (u, v) ∉ E. No two chosen vertices can be neighbors.
Take a five-node graph with edges 1-2, 2-3, 3-4, 4-5, and an extra edge 1-3:
Valid sets: {1, 4}, {2, 4}, {1, 5}. The maximum is size 2. Node 3 connects to 1, 2, and 4, so picking it kills three options at once. Any single vertex qualifies trivially. The empty set too. Neither wins you anything.
Why the General Case Will Ruin Your Day
Finding the maximum independent set on an arbitrary graph is NP-hard. The decision version, "does a graph have an independent set of size k?", is NP-complete, sitting right next to SAT and 3-coloring on the list of problems that haunt computer scientists. You can verify a candidate in O(|S|²) by checking every pair, but finding the optimal one means searching exponentially many subsets in the worst case.
In other words: brute force is your only friend on a general graph, and your friend is terrible.
At least in interviews, the graph always has some structure hiding in there.
Two structural facts worth knowing before you give up entirely.
The complement graph G' has an edge wherever G doesn't. An independent set in G is a clique in G'. Maximum independent set and maximum clique are exactly as hard as each other, which is a fun way of saying they're both awful.
A vertex cover is a set of vertices that touches every edge. If S is an independent set, then V \ S is a vertex cover. The two are complements in the vertex set. Solve one and you have the other for free. Small silver lining.
When the Problem Gets Tractable
General graphs: NP-hard. Specific graph families: actually solvable. This is where the fun starts.
Trees: O(n) DP
On a tree, run a simple DP. At each node, you have two choices: include it (which forces you to skip both children) or exclude it (which lets each child pick its own optimal value):
def max_independent_set(root): def dp(node): if not node: return 0, 0 left_inc, left_exc = dp(node.left) right_inc, right_exc = dp(node.right) include = node.val + left_exc + right_exc exclude = max(left_inc, left_exc) + max(right_inc, right_exc) return include, exclude inc, exc = dp(root) return max(inc, exc)
O(n) time, O(h) space for the call stack. Trees have no cycles, so subproblem results from unrelated branches never interact. That's what makes the recurrence valid. Add a single back edge and this assumption breaks.
Bipartite Graphs: König's Theorem
For bipartite graphs, maximum independent set = n minus maximum matching. That's König's theorem.
The chain: König says minimum vertex cover equals maximum matching for bipartite graphs. Vertex cover and independent set are complements in the vertex set. So MIS = n minus min cover = n minus max matching. Hopcroft-Karp finds the matching in O(E√V), making the whole thing polynomial. One of those results where the proof path is longer than it looks from the outside.
Interval Graphs: Just Sort by End Time
On interval graphs (vertices are intervals, edges connect overlapping ones), MIS reduces to interval scheduling. Pick the maximum number of non-overlapping intervals. Sort by end time, greedily take anything that doesn't overlap the last pick:
def max_non_overlapping(intervals: list[tuple[int, int]]) -> int: intervals.sort(key=lambda x: x[1]) count, end = 0, float('-inf') for start, finish in intervals: if start >= end: count += 1 end = finish return count
O(n log n). You've almost certainly solved this before under the name "activity selection" or "meeting rooms" without connecting it to independent sets. Now you have the name.
More broadly, for perfect graphs, both MIS and maximum clique run in polynomial time via the ellipsoid method. Chordal graphs, comparability graphs, and interval graphs are all perfect. The key property: chromatic number equals clique number at every induced subgraph. File this under "useful to know, painful to re-derive cold."
House Robber Is This Problem
LeetCode 198: houses in a row, non-negative values, maximize what you take without hitting two adjacent houses. A path graph. Every house is a node. Every pair of consecutive houses is an edge. Maximum weight independent set on a path:
def rob(nums: list[int]) -> int: if not nums: return 0 prev2, prev1 = 0, 0 for num in nums: curr = max(prev1, prev2 + num) prev2, prev1 = prev1, curr return prev1
O(n) time. O(1) space, rolling two variables since the recurrence only looks back two steps.
LeetCode 213 (House Robber II) makes the street circular: first and last houses are now neighbors. That's a path graph with one extra edge. You can't include both ends. Two passes: once excluding the first house, once excluding the last, take the max. Same DP, run twice.
LeetCode 337 (House Robber III) puts the houses in a binary tree. That's MIS on a weighted tree. Same tree DP from the section above. Every House Robber variant is asking for maximum weight independent set on a specific graph structure. Naming that structure tells you the approach before you've written a line.
How Complexity Shifts by Graph Type
| Graph type | Complexity | Notes |
|---|---|---|
| General graph | NP-hard | Exponential worst case |
| Tree | O(n) time, O(h) space | Tree DP with include/exclude |
| Path graph | O(n) time, O(1) space | House Robber DP, two rolling vars |
| Cycle | O(n) time, O(1) space | Two passes: exclude-first, exclude-last |
| Bipartite graph | O(E√V) | König's theorem + Hopcroft-Karp |
| Interval graph | O(n log n) | Interval scheduling greedy |
For the tree case, O(h) is the recursion stack depth. If you're on a deeply unbalanced tree near the stack limit, iterative postorder traversal substitutes cleanly.
How to Spot It When It's Wearing a Disguise
You won't see "maximum independent set" on a whiteboard. You'll see it dressed up in a trench coat and fake mustache, pretending to be a completely different problem.
The problem wasn't hard. You just hadn't named it yet.
Signal phrases that encode this constraint:
- "No two adjacent elements can be selected"
- "Cannot pick two elements within distance k"
- "Maximize the sum with no two consecutive choices"
- "Assign tasks so no two conflicting ones run simultaneously"
When you see those words, the translation is automatic: draw the conflict graph, identify the graph type, pick the algorithm. Say a problem gives you a list of tasks where each has a profit and conflicts with the immediately preceding and following task. Path graph. Edge between consecutive tasks. You want the two-variable rolling DP and you're done in five minutes.
Once you name the structure, the approach follows. Path or tree: DP with include/exclude. Bipartite: max matching plus König's. Small general graph (n ≤ 20): bitmask DP over all 2^n subsets. Large general graph with no obvious structure: the problem either wants you to recognize NP-hardness, or there's a structural constraint hiding in plain sight that collapses the search space.
The gap between knowing the reduction and stating it fluently under pressure is real. Practicing "no two adjacent means independent set, this graph is a path, so I want rolling DP" out loud with SpaceComplexity until it's reflexive is the kind of rep that actually shows in the room.
How This Connects to Other Graph Problems
Vertex cover: V minus an independent set. Minimum vertex cover is NP-hard on general graphs, polynomial on bipartite graphs via König's theorem.
Clique: independent set on the complement graph. NP-hard, equivalent to MIS by construction. Same problem, different outfit.
Dominating set: every vertex is in S or adjacent to a vertex in S. Unlike an independent set, a dominating set can have edges inside it. Easier to confuse these two than you'd expect.
Graph coloring: each color class in a valid k-coloring is an independent set. The chromatic number is the minimum number of independent sets needed to partition V. This is why "graph coloring" shows up in register allocation, scheduling, and a dozen other places where you need to partition things into non-conflicting groups.