Reverse-Delete Algorithm, in depth: the delete-while-feasible template, matroid duality, and the pruning step of primal-dual algorithms

The template and its one guarantee

The loop needs a ground set, a cost and a predicate that is monotone: adding elements to a feasible set keeps it feasible. Connectivity, "covers every element" and "contains an s-t path" are all monotone. Monotonicity buys one guarantee whatever the predicate: the output is minimal, meaning no single element can be removed. When x is put back, the kept set at that moment is a superset of the final set. If removing x broke feasibility then, it breaks it for the smaller final set too.

def reverse_delete(items, cost, feasible):
    """Return a minimal feasible subset of `items`, deleting costliest first.
    `feasible(kept)` must be monotone: supersets of feasible sets are feasible."""
    kept = set(items)
    if not feasible(kept):
        raise ValueError("the full set is infeasible; nothing to prune")
    for x in sorted(items, key=lambda x: (cost(x), x), reverse=True):
        kept.discard(x)
        if not feasible(kept):
            kept.add(x)                     # x is needed: put it back
    return kept

def connected(n, edges, kept):
    """Union-find check that the kept edge ids span all n vertices."""
    parent = list(range(n))
    def find(a):
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a
    comps = n
    for i in kept:
        _, u, v = edges[i]
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            comps -= 1
    return comps == 1

# MST: edges are (weight, u, v); ids break ties so the order is total.
# tree = reverse_delete(range(len(E)), lambda i: (E[i][0], i), lambda k: connected(n, E, k))

The cost is one oracle call per element, so n elements cost n times the oracle's cost. For connectivity that is O(m(n + m)) with a fresh union-find each time, which is why nobody computes large MSTs this way. Where it pays is when the predicate is expensive and opaque, such as "the build still passes" or "the network still meets its redundancy policy". Then reverse-delete needs nothing but the oracle.

When minimal is minimum: matroids and planar duality

Why is the result optimal for spanning trees and not in general? Spanning trees are the bases of the graphic matroid, and connected edge sets are its spanning sets. For any matroid, deleting elements from heaviest to lightest while the rest still spans yields a minimum-weight basis. This is the greedy algorithm run on the dual matroid: the deleted elements form a maximum-weight basis of the dual.

For planar graphs you can see that dual directly. In a connected plane graph G, T is a spanning tree exactly when the dual edges of the complement of T form a spanning tree of the dual graph G*, which has one vertex per face. So reverse-delete on G is maximum-weight Kruskal on G*. A test checks it on grid graphs. The generator builds each grid and its dual (one dual vertex per cell plus one for the outer face) so that edge i of G and edge i of G* share an id and a weight:

def kruskal(n, edges, maximum=False):
    parent = list(range(n))
    def find(a):
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a
    out = set()
    for i in sorted(range(len(edges)), key=lambda i: (edges[i][0], i), reverse=maximum):
        ru, rv = find(edges[i][1]), find(edges[i][2])
        if ru != rv:
            parent[ru] = rv
            out.add(i)
    return out

def grid_with_dual(rows, cols, rng):
    """Grid graph G and its planar dual G* (dual vertex 0 is the outer face)."""
    vid = lambda r, c: r * cols + c
    fid = lambda r, c: 1 + r * (cols - 1) + c if 0 <= r < rows - 1 and 0 <= c < cols - 1 else 0
    primal, dual = [], []
    for r in range(rows):
        for c in range(cols):
            if c + 1 < cols:                       # horizontal edge: faces above and below
                w = rng.random()
                primal.append((w, vid(r, c), vid(r, c + 1)))
                dual.append((w, fid(r - 1, c), fid(r, c)))
            if r + 1 < rows:                       # vertical edge: faces left and right
                w = rng.random()
                primal.append((w, vid(r, c), vid(r + 1, c)))
                dual.append((w, fid(r, c - 1), fid(r, c)))
    return primal, dual, rows * cols, 1 + (rows - 1) * (cols - 1)

for seed in range(200):
    rng = random.Random(seed)
    E, D, n, nf = grid_with_dual(rng.randint(2, 7), rng.randint(2, 7), rng)
    T = reverse_delete(range(len(E)), lambda i: (E[i][0], i), lambda k: connected(n, E, k))
    assert T == kruskal(n, E)                                        # same MST
    assert set(range(len(E))) - T == kruskal(nf, D, maximum=True)    # deleted = dual max tree

All 200 random grids, from 2 x 2 up to 7 x 7, passed both assertions. The duality is not just a curiosity. It means every reverse-delete fact is a Kruskal fact in disguise, and it gives you a second, independent implementation to test against.

The matroid view also tells you which other pruning jobs are safe. Any feasibility notion of the form "still contains a basis of some matroid" gives an optimal answer under heaviest-first deletion. Keeping a cheapest set of vectors that still spans a vector space is one example (the linear matroid). Requirements that combine two matroids are not, because the intersection of two matroids is not a matroid in general: keeping a set of links that stays connected in two different network layers at once is such a case. When you cannot name the matroid, assume the result is only minimal and test it against brute force on small cases.

When minimal is not minimum: set cover

Drop the matroid structure and minimal stops meaning minimum. Take the universe {0, 1, 2, 3, 4} and five sets:

Reverse-delete keeps {A, B, D} at cost 18. Brute force finds {C, E} at cost 10. Deleting C first was the mistake: it was expensive, but it was the only set that could cover 3 and 4 together. The loop is greedy and never reconsiders. This is the general picture for monotone predicates. You get minimality cheaply, and no approximation guarantee unless something else supplies one. In approximation algorithms, that something is LP duality.

Reverse deletion in primal-dual algorithms

Primal-dual approximation algorithms, for problems from shortest paths to Steiner forest, share a two-phase shape. First, grow: raise dual variables on the cut LP until constraints go tight, and add each tight element to a set F, until F is feasible. Second, prune: run reverse deletion over F in the reverse order of addition. For the generalised Steiner tree (Steiner forest) problem, this is the analysis behind the factor-2 algorithms of Agrawal, Klein and Ravi and of Goemans and Williamson, both 1995. The primal-dual chapter of Williamson and Shmoys's The Design of Approximation Algorithms presents it with reverse deletion. The pruning is load-bearing: the bound charges each kept element to the duals raised, and that charging only works when the final set is minimal. (LP duality and the Steiner tree article give the background.)

Shortest s-t path is the smallest case where all of this runs and can be checked exactly. The cut LP has one dual variable y_S for every vertex set S that contains s but not t. Growing the component of s and raising its dual until an edge goes tight turns out to be Dijkstra's algorithm. The pruning then strips the branches that do not lead to t:

def primal_dual_st_path(n, edges, s, t):
    """Grow duals on the cut LP, then prune in reverse order of addition."""
    load = [0.0] * len(edges)             # sum of y_S over sets S that edge crosses
    F, order, C, dual = set(), [], {s}, 0.0
    while t not in C:
        crossing = [i for i, (_, u, v) in enumerate(edges) if (u in C) != (v in C)]
        if not crossing:
            raise ValueError("t is unreachable")
        i = min(crossing, key=lambda i: (edges[i][0] - load[i], i))
        eps = edges[i][0] - load[i]       # raise y_C until edge i goes tight
        dual += eps
        for j in crossing:
            load[j] += eps
        F.add(i); order.append(i)
        _, u, v = edges[i]
        C |= {u, v}
    def joins(kept):                      # does `kept` contain an s-t path?
        adj = {}
        for j in kept:
            _, u, v = edges[j]
            adj.setdefault(u, []).append(v); adj.setdefault(v, []).append(u)
        seen, stack = {s}, [s]
        while stack:
            for y in adj.get(stack.pop(), []):
                if y not in seen:
                    seen.add(y); stack.append(y)
        return t in seen
    kept = set(F)
    for i in reversed(order):
        kept.discard(i)
        if not joins(kept):
            kept.add(i)
    return kept, dual

Worked example: grow, then prune

Take vertices 0 to 5, with s = 0 and t = 3, and edges (id: endpoints, cost) e0: 0-1, 4; e1: 0-2, 1; e2: 2-1, 2; e3: 1-3, 5; e4: 2-3, 8; e5: 1-4, 3; e6: 4-3, 1; e7: 0-5, 2; e8: 5-3, 6. The grow phase raised five duals:

F is then {e1, e7, e2, e5, e6}. Reverse deletion visits e6, e5, e2, e7, e1. Only e7, the dead-end branch to vertex 5, can go without cutting s from t. The kept path 0-2-1-4-3 costs 1 + 2 + 3 + 1 = 7, equal to the dual total. By weak duality, a feasible primal whose cost equals a feasible dual is optimal, so this run certifies itself. A randomised test on 276 reachable random multigraphs (seeds 0 to 299, 4 to 12 vertices) matched Dijkstra's distance in every case, and the dual total equalled it too. For Steiner forest the grown set is a forest whose minimal part can still be nearly twice the duals, and that is exactly where the factor 2 comes from.

Operational guidance

• Make the predicate monotone, or stop: "latency stays under 50 ms" is usually monotone in links kept, but "exactly two paths exist" is not. With a non-monotone oracle the loop's minimality argument fails silently.
• Fix the order completely: break cost ties by a stable id, as the code does, so reruns and audits reproduce the same output.
• Budget the oracle: n elements mean n calls. When calls are slow, prune in chunks first (delta debugging does this for failing inputs), then finish one element at a time.
• Log every decision: record each element with "deleted" or "needed". The needed list is your explanation of why each surviving element survived.
• Re-run the oracle on the final set: one extra call that confirms the output is feasible guards against an oracle with hidden state or caching bugs, which would otherwise ship an infeasible network or configuration.

Failure modes

• Expecting optimality off a matroid: the set-cover table shows a 1.8x gap from five sets. Unless the structure is a matroid or a dual bound covers you, report the result as minimal, never minimum.
• Pruning in forward order inside primal-dual code: for forest-shaped F the minimal subset is unique, so the order may look irrelevant in tests. On problems where F can contain overlapping redundancy, it changes which elements survive and can void the analysis. Follow the reverse order the proof assumes.
• An infeasible start: if the full set fails the predicate, there is nothing to prune. The code raises an error rather than returning a wrong "minimal" set.
• Disconnected input graphs: spanning-tree feasibility fails from the start. For a minimum spanning forest, change the predicate to "same number of components as the input".

What to do next

1. Copy reverse_delete and run it with the connectivity oracle against your Kruskal on random graphs, breaking ties by edge id.
2. Build the grid dual and confirm that the deleted edges form a maximum spanning tree of G*, as a second independent test.
3. Reproduce the five-set cover counterexample, then add a brute-force check to any pruning tool you ship, so you know your typical gap.
4. Run primal_dual_st_path on the worked example and confirm that the dual total equals the path cost.
5. Read the primal-dual chapter of Williamson and Shmoys and work through the Steiner forest analysis, noting exactly where minimality is used.
6. For a production pruning job, write down why the predicate is monotone before writing any code.