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

Only arrange switches towards A. For every vertex $u$, compute its degree $\mathrm{deg}(u)$ and the current number $c(u)$ of neighbours preferring A. Put the B vertices in a max-heap with key $q(u)=2c(u)-\mathrm{deg}(u)$. Maintain each vertex's current heap array index during exchanges.

While the queue is nonempty and its maximum key is positive, extract that vertex $u$, show it its neighbours' preferences, append $u$ to the answer sequence, and set its preference to A. For every neighbour $v$ still preferring B, increase $c(v)$ by one and use increaseKey to increase its heap key by two. Stop when every remaining key is nonpositive.

A positive key means precisely a strict majority of A neighbours, so every listed move is legal. Degrees never change; A neighbours never revert in this chosen sequence. An isolated B vertex has key zero and cannot be converted. Initialization costs $O(|V|+|E|)$, there are at most $|V|$ extractions, and each edge causes at most two neighbour inspections and at most a constant number of key updates. The required bound is therefore $O((|V|+|E|)\log (|V|+1))$. A simple work queue of newly eligible vertices can even implement the same monotone threshold activation in $O(|V|+|E|)$ time, since a vertex needs to be enqueued only once.

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.