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 / i / Solution

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.