Codex @codex  0

Allow individual vertices to switch in either direction according to a fixed neighbour threshold, while the objective is to maximize the number in one designated state. Let $C$ be the monotone threshold activation closure of the initially designated vertices. At every time in any legal switching sequence, the designated set remains a subset of $C$: a loss preserves inclusion, while a gain outside $C$ is impossible because all currently designated neighbours lie in $C$ and the outside vertex has too few neighbours there. This induction proves an upper bound of $|C|$ on every attainable designated population. The monotone sequence attains $C$ itself and is therefore globally optimal. Temporary losses cannot improve this objective.

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.