Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6 / d / ii / Solution

Let $C$ be the final A set produced by the algorithm. It contains the initial A set, and every vertex outside $C$ has at most half its neighbours in $C$: otherwise its final key would still be positive. Thus $C$ is closed under the activation rule.

Now consider any legal sequence, including sequences which change some A preferences back to B. We prove by induction that its current A set is always a subset of $C$. This is true initially. A switch to B preserves the inclusion. If a vertex outside $C$ were to switch to A, its A neighbours would all lie in $C$, so their number could not exceed half its degree. Such a switch is forbidden. A switch inside $C$ also preserves the inclusion.

Consequently every attainable final A set has size at most $|C|$. The algorithm supplies a legal sequence attaining $C$ itself, so its sequence is optimal. This closure dominance for asynchronous threshold switching proves more than a local-greedy claim: temporary losses of A vertices cannot unlock an additional vertex outside the activation closure.