Maximum Independent Set, in depth: vertex cover and clique duality, easy graph classes, branch-and-reduce measured, greedy bounds and weighted trees

Independent set, vertex cover and clique

Three problems are one problem seen from different sides. S is independent in G exactly when the remaining vertices V \ S touch every edge, so they form a vertex cover. That gives α(G) + τ(G) = n, where α is the largest independent set and τ the smallest vertex cover. S is independent in G exactly when it is a clique in the complement graph. So an MIS solver is also a vertex cover solver and a clique solver. The choice between views is practical: sparse graphs have dense complements, so an MIS solver suits sparse inputs where a clique solver would need the dense complement. The maximum clique article covers the dense-graph side with colouring bounds and bitsets.

Keep maximal and maximum apart. A maximal independent set cannot be extended by one vertex, and a single greedy pass finds one in linear time. A maximum independent set is the largest of all, and finding it is the hard problem. A star with k leaves shows the gap: picking the centre first gives a maximal set of size 1, while the leaves give size k.

Hardness extends to approximation. Unless P = NP, no polynomial algorithm approximates MIS within n^(1−ε) for any fixed ε > 0 on general graphs. In parameterised terms, deciding whether an independent set of size k exists is W[1]-hard, unlike vertex cover of size k, which is fixed-parameter tractable.

Graph classes where MIS is easy

Before writing a general solver, check whether your graph belongs to a class where MIS is polynomial. Conflict graphs from real systems often do.

The interval case is the familiar interval-scheduling greedy, since non-overlapping intervals are exactly an independent set of the interval graph. The bipartite case comes from König's theorem: the minimum vertex cover equals the maximum matching, so α = n − ν. Detecting the class is cheap. A BFS 2-colouring tests bipartiteness, and lexicographic BFS followed by a perfect-elimination check tests chordality.

Branch and reduce

Exact algorithms for general graphs combine safe reduction rules with branching. A rule is safe when some maximum independent set agrees with its choice.

• Degree 0: an isolated vertex is always in some MIS, so take it.
• Degree 1: a pendant vertex v with neighbour u can be taken. Any MIS that contains u can swap u for v without losing size, so take v and delete u.
• Branch: pick a maximum-degree vertex v. Either v is out (delete it) or v is in (delete v and its neighbours). Return the larger result.

Branching on a vertex of degree d removes 1 vertex on one side and d + 1 on the other. With d ≥ 3 the running time obeys T(n) ≤ T(n−1) + T(n−4), which solves to about 1.38ⁿ. Graphs of maximum degree 2 are disjoint paths and cycles. Paths dissolve under the degree-1 rule, and a cycle needs only one branch before it becomes a path. Research solvers add stronger rules, such as degree-2 folding, domination and LP-based reductions, and tighter branching. The structure stays the same.

def remove(adj, drop):
    return {v: adj[v] - drop for v in adj if v not in drop}

def mis(adj):
    """Return a maximum independent set of adj (dict: vertex -> set of neighbours)."""
    taken = set()
    changed = True
    while changed:                                  # reduction rules to a fixpoint
        changed = False
        for v in list(adj):
            if v in adj and len(adj[v]) <= 1:       # degree 0 or 1: safe to take
                taken.add(v)
                adj = remove(adj, {v} | adj[v])
                changed = True
    if not adj:
        return taken
    v = max(adj, key=lambda x: len(adj[x]))         # branch on maximum degree
    with_v = {v} | mis(remove(adj, {v} | adj[v]))
    without_v = mis(remove(adj, {v}))
    return taken | max(with_v, without_v, key=len)

Measured: what the rules buy

The solver was checked against brute-force enumeration on 300 random graphs with up to 14 vertices and edge probabilities from 0.1 to 0.5. Sizes matched in every case, and every returned set was independent. The table then compares the same branching with and without the two rules on G(n, p) graphs. It also shows the min-degree greedy result and the Caro–Wei lower bound, both explained in the next section.

Two patterns are worth noticing. On sparse graphs the rules are the whole story: branching alone grows about twelvefold per ten vertices, while with the rules the 50-vertex graph needed under 300 nodes and 0.01 seconds. On the denser graph the rules fire less, because few vertices have degree 1, and their gain shrinks to about 13 times. Denser graphs have small α, so clique-style colouring bounds become the better tool there.

Greedy, bounds and local search

When exact search is too slow, use a heuristic and know how far it can be from optimal. Min-degree greedy repeatedly takes a vertex of smallest degree and deletes it with its neighbours. It always returns at least the Caro–Wei bound Σ 1/(d(v)+1). By convexity that is at least n/(d̄+1) for average degree d̄, which is Turán's bound. In the table, greedy came within one or two vertices of α, far above the bound, which is typical of sparse random graphs and not a guarantee.

Local search improves a greedy answer. A (1,2)-swap removes one vertex from the set and adds two non-adjacent neighbours that it alone blocked. Repeated swaps with random perturbation are the core of the strongest practical heuristics, which follow a reduce-then-search pattern: apply exact reductions until the kernel stops shrinking, run local search on the kernel, then lift the solution back through the reductions.

The bounds also give a cheap quality check. If your heuristic returns s and an upper bound gives U, the gap U − s tells you whether exact search is worth starting. Upper bounds come from a clique cover (an independent set takes at most one vertex per clique), from the LP below, or from n − ν for a maximum matching of size ν, since every vertex cover needs one endpoint of each matching edge.

Weighted MIS and the tree DP

Real conflict problems usually have weights: revenue per job, priority per label. Maximum weight independent set (MWIS) keeps the structure but changes the rules. The degree-1 rule becomes "take pendant v if w(v) ≥ w(u)". Without the weight condition it is unsafe. On trees, MWIS is a two-state dynamic programme, the same pattern as in tree DP:

def tree_mwis(n, w, parent):          # parent[v] < v for v >= 1, vertex 0 is the root
    kids = {v: [] for v in range(n)}
    for v in range(1, n):
        kids[parent[v]].append(v)
    inc, exc = [0] * n, [0] * n
    for v in reversed(range(n)):      # children are processed before parents
        inc[v] = w[v] + sum(exc[c] for c in kids[v])
        exc[v] = sum(max(inc[c], exc[c]) for c in kids[v])
    return max(inc[0], exc[0])

On a random 12-vertex tree with weights 1 to 9 it returned 36, matching brute force over all 4,096 subsets. On a 200,000-vertex tree it ran in 0.43 seconds of pure Python. Iterate children before parents as shown. A recursive version hits Python's recursion limit on deep trees long before it runs out of time.

The integer programme and half-integrality

The integer programme is short: maximise Σ x_v (or Σ w_v x_v) subject to x_u + x_v ≤ 1 for every edge, with x_v ∈ {0, 1}. Its LP relaxation is weak, because x_v = 1/2 everywhere is always feasible, so the LP bound is at least n/2 even when α is tiny. Two facts make it useful anyway. The LP has an optimal solution with every x_v in {0, 1/2, 1}, which is half-integrality. Nemhauser and Trotter showed that some maximum independent set contains every vertex the LP sets to 1 and avoids every vertex it sets to 0, so the LP is an exact reduction rule. For solving, add clique inequalities (Σ x_v ≤ 1 over each clique), which tighten the bound sharply on dense graphs. A MIP solver on that model is a useful baseline to compare a custom solver against.

Failure modes

• Unsafe rules. Using the unweighted degree-1 rule on a weighted instance, or applying a rule from the vertex cover literature without translating it. Test every rule against brute force on small random graphs, as above.
• Wrong solution after reductions. Folding-style rules change the graph, so the final set must be mapped back. Check independence and size on the original graph.
• Greedy taken as optimal. A maximal set is not a maximum one. Report the gap to an upper bound.
• Clique solver on a sparse graph. Complementing a sparse graph with a million vertices produces about 5 × 10¹¹ edges.
• Recursion depth. Branching and tree DP written recursively overflow on large inputs. Use explicit stacks or orders.
• Unbounded runs. Exact search has no useful worst-case time. Always pass a node or time budget and return the best set found so far.

Operational guidance and trade-offs

In practice, run this sequence. Split the graph into connected components and solve each one separately, since α adds up across components. Test for an easy class. Apply reductions and measure the kernel. If the kernel is small, solve it exactly with branching or a MIP. If it is large, run local search on it with a time limit. Report the solution, an upper bound and their gap. The trade-off is time against certainty: exact methods prove optimality but have exponential worst cases, while heuristics give good answers quickly with no proof. For small k, the complementary question "can I delete k vertices to remove all conflicts?" is vertex cover, which is fixed-parameter tractable and often the better formulation. Vertex cover approximation gives a 2-approximation for that side, but the guarantee does not carry over to MIS.

What to do next

1. Run the branch-and-reduce code with and without the rules on your own graphs and record the node counts.
2. Add a node budget that returns the best set found so far, and log the gap to a clique-cover upper bound.
3. Check whether your conflict graph is bipartite, an interval graph or a tree, and use the polynomial method if it is.
4. Implement the weighted degree-1 rule and verify it against brute force on 300 random weighted graphs.
5. Write the ILP with clique inequalities and compare its solve time with the branching solver.
6. For large sparse graphs, add (1,2)-swap local search on the reduced kernel and compare its result with greedy.