Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes (aamas23-00255)

Given rational masses \(\mu_1,\ldots,\mu_\tau>0\) summing to \(1\) on communities arranged as \(C_\tau\), choose \(S\subseteq[\tau]\) minimizing \(\mu(S)=\sum_{i\in S}\mu_i\) such that forcing every resident in \(S\) blue, respectively white, makes synchronous MM reach the all-blue, respectively all-white, state for every initial assignment outside \(S\), where each community has one public color and retains it when its two neighbors tie.

A society is given by its support: a cyclically ordered list of \(\tau\ge 3\) community types with positive binary rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. The interaction graph is the simple undirected cycle \(C_\tau\), with \(m=\tau\) edges.
Each community has one public color, blue or white. In synchronous Majority Model (MM) rounds, each community adopts its two neighbors’ common color when they agree and retains its own color when they disagree. Neighbor influence is unweighted; masses determine only selection cost.
A set \(S\subseteq\{1,\ldots,\tau\}\) is winning if, for each color \(a\), every initial community coloring assigning \(a\) to all communities in \(S\) eventually reaches the all-\(a\) coloring. Selection fixes colors only initially; all communities subsequently update. Communities are selected whole, at cost \(\mu(S)=\sum_{i\in S}\mu_i\).
Given also a binary rational budget \(q\in[0,1]\), consider whether a winning set of cost at most \(q\) exists. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).

Is deciding whether there exists a winning set \(S\) with \(\mu(S)\le q\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For the discrete MM on an unweighted cycle \(C_n\), the minimum winning-set cardinality is \(\lfloor n/2\rfloor+1\), and an optimal set has an explicit polynomial-time construction ([Zehmakan](https://link.springer.com/article/10.1007/s10458-024-09651-y)). No result settling the exact mass-cost problem above was located in the searches performed.

Result. The decision problem is in \(\mathrm{P}\). An exact algorithm uses \(\mathcal{O}(m+\tau)\) integer arithmetic operations on integers of \(\mathcal{O}(L)\) bits, and therefore \(\mathcal{O}((m+\tau)L^2)\) bit operations using elementary arithmetic. Here \(m=\tau\).

The key is a complete characterization of winning sets. The proof below is self-contained; it strengthens the cardinality characterization in [Zehmakan’s Theorem 3.2](https://link.springer.com/article/10.1007/s10458-024-09651-y) sufficiently to optimize arbitrary mass costs.

1. Exact characterization of winning sets. Write \(V=\{1,\ldots,\tau\}\), with indices interpreted cyclically. A vertex cover is a set meeting every edge; an independent set contains no adjacent vertices.

Proposition. A set \(S\subseteq V\) is winning if and only if:

• \(V\setminus S\) is independent, equivalently \(S\) is a vertex cover.
• \(S\) contains two adjacent vertices.

Necessity. Fix a target color \(a\), and initially assign \(a\) exactly to \(S\).

If two adjacent vertices lie outside \(S\), they initially have the opposite color. They retain that color forever: provided both have it in one round, each has a neighbor of its own color, so its neighbors either agree on that color or disagree, in which case it retains its color. Induction proves permanence. Consequently, \(S\) must meet every edge.

Suppose now that \(S\) meets every edge but contains no adjacent vertices. Each edge then has exactly one endpoint in \(S\). Thus the initial coloring alternates around the cycle, which forces \(\tau\) to be even. Every vertex has two neighbors of the opposite color, so every round flips every color. The process oscillates between the two alternating colorings and never reaches a monochromatic coloring. Therefore \(S\) must also contain an edge.

Sufficiency. Fix either target color \(a\) and any initial coloring assigning \(a\) to every vertex of \(S\). Encode \(a\) by \(1\) and the opposite color by \(0\). The update rule is exactly

\(x_i(t+1)=\operatorname{maj}\bigl(x_{i-1}(t),x_i(t),x_{i+1}(t)\bigr)\),

where \(\operatorname{maj}\) returns the value appearing at least twice. This identity follows directly from retaining the current color when the two neighbors disagree.

Initially, the vertices colored \(0\) form an independent set, since they are a subset of \(V\setminus S\). We first prove that this property persists.

Assume that no two adjacent vertices have value \(0\) at time \(t\). A vertex currently colored \(0\) has both neighbors colored \(1\), so it becomes \(1\). A vertex currently colored \(1\) becomes \(0\) exactly when both neighbors are \(0\). Hence

\(x_i(t+1)=0\quad\Longleftrightarrow\quad x_{i-1}(t)=x_{i+1}(t)=0.\)

If adjacent vertices \(i\) and \(i+1\) both became \(0\), this equivalence would imply \(x_{i+1}(t)=x_i(t)=0\), contradicting independence. Thus the vertices colored \(0\) remain independent.

By the second hypothesis, there is initially a consecutive block of at least two vertices colored \(1\). Every vertex in such a block remains \(1\) in the next round, because its own color and at least one neighbor’s color are \(1\).

Consider a vertex \(v\) immediately outside the block. If \(v\) is currently \(1\), it remains \(1\) because it has a neighbor in the block. If \(v\) is currently \(0\), both its neighbors are \(1\), by independence of the vertices colored \(0\); therefore it becomes \(1\).

Consequently, until the entire cycle is colored \(1\), the block grows by at least one vertex per round. It fills the cycle within at most \(\tau-2\) rounds. This argument applies to every allowed initial coloring and either choice of \(a\), proving that \(S\) is winning.

2. Exact mass optimization. Let \(z_i\in\{0,1\}\) indicate whether community \(i\) is selected. By the proposition, we must minimize \(\sum_{i=1}^{\tau}\mu_i z_i\) subject to

\(z_i+z_{i+1}\ge 1\quad\text{for every cyclic edge},\)

and

\(z_i=z_{i+1}=1\quad\text{for at least one cyclic edge}.\)

These conditions can be enforced by a dynamic program with a constant number of states.

First convert costs and budget to integers. Write \(\mu_i=a_i/b_i\) and \(q=a_q/b_q\), with positive integer denominators, and define

\(D=b_q\prod_{i=1}^{\tau}b_i,\qquad W_i=a_i(D/b_i),\qquad Q=a_q(D/b_q).\)

Then \(\sum_i W_i=D\), and \(\mu(S)\le q\) is equivalent to \(\sum_{i\in S}W_i\le Q\).

Run the following dynamic program separately for each fixed first bit \(s\in\{0,1\}\).

For a prefix \(z_1,\ldots,z_i\), let \(F_i^s(b,h)\) denote its minimum integer cost, subject to:

• \(z_1=s\) and \(z_i=b\);
• no edge within the prefix has endpoint bits \((0,0)\);
• \(h\in\{0,1\}\) records whether an edge within the prefix has endpoint bits \((1,1)\).

Unattainable states have value \(+\infty\). Initialize

\(F_1^s(s,0)=sW_1.\)

For each state \((b,h)\) and next bit \(c\in\{0,1\}\), reject the transition if \(b=c=0\). Otherwise set \(h'=h\lor(b\land c)\), where \(\lor\) and \(\land\) are Boolean operations, and update

\(F_{i+1}^s(c,h')\leftarrow\min\bigl\{F_{i+1}^s(c,h'),\,F_i^s(b,h)+cW_{i+1}\bigr\}.\)

After processing all communities, account for the closing edge between \(\tau\) and \(1\). Accept a final state \((b,h)\) precisely when

\(b\lor s=1\qquad\text{and}\qquad h\lor(b\land s)=1.\)

The first condition covers the closing edge; the second requires a selected adjacent pair somewhere on the cycle.

Correctness. At initialization, the unique represented prefix has exactly the stated cost and properties. Each transition appends one bit, rejects exactly the newly created uncovered edge, updates the adjacent-pair flag exactly, and adds exactly the new selection cost. Induction therefore proves the stated meaning of every table entry. Future transitions depend only on the last bit, the flag, and the fixed first bit, so retaining the cheapest prefix for each state loses no feasible optimum.

The final conditions impose exactly the remaining cyclic constraints. Thus the minimum accepted cost \(K\), over both first-bit choices, is the minimum cost of a winning set. The answer is yes exactly when \(K\le Q\). A feasible state always exists because selecting all communities is winning.

3. Running time and verification. Each first-bit choice has four states per position and at most two transitions per state. The dynamic program therefore performs \(\mathcal{O}(\tau)\) additions and comparisons.

The bit length of \(D\) is \(\mathcal{O}(L)\), because it is a product of denominators whose total encoded length is at most \(L\). Every \(W_i\), \(Q\), and finite table value is at most \(D\), and hence also has \(\mathcal{O}(L)\) bits. Computing the integer costs takes \(\mathcal{O}(\tau)\) integer multiplications and divisions. Using elementary arithmetic, the complete algorithm takes \(\mathcal{O}(\tau L^2)=\mathcal{O}((m+\tau)L^2)\) bit operations. This bound depends polynomially on the encoding length, not on the numerical value of the common denominator.

As supplementary checks, exhaustive computation verified the characterization for every set and every compatible initial coloring on cycles with \(3\le\tau\le12\). The dynamic program also matched exhaustive optimization on \(270\) positive-integer weight instances with \(3\le\tau\le11\). These checks are corroboration; the proofs above establish correctness for all inputs.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The characterization, exact optimization algorithm, and polynomial bit complexity are correct as written. No major or minor mathematical issues were found. The argument resolves the mass-cost problem in the intended model.

• Model and quantifiers. The proof uses the simple cycle with \(\tau\ge3\), so every vertex has two distinct neighbors. Its update identity

\[ x_i(t+1)=\operatorname{maj}(x_{i-1}(t),x_i(t),x_{i+1}(t)) \]
agrees exactly with the specified neighbor rule: agreeing neighbors determine the next color, and disagreeing neighbors leave the current color unchanged. Masses enter only the objective function.

Necessity uses a permitted initial coloring, which is sufficient to disprove the universal winning condition. Sufficiency handles every initial coloring compatible with the selected set and either target color. Selected vertices are never treated as permanently fixed.

• Necessity of covering every edge. The permanence argument for two adjacent vertices of the opposite color is valid under synchronous updates. If both currently have that color, each has a neighbor of that color. Its other neighbor either agrees, forcing that same color, or disagrees, causing retention. Thus both retain their colors simultaneously, and induction applies. An uncovered edge therefore prevents eventual consensus on the target color.

• Necessity of a selected adjacent pair. Assuming the cover condition, absence of adjacent selected vertices makes every edge have exactly one selected endpoint. The resulting initial coloring alternates, which is possible only on an even cycle. Every vertex then has two neighbors of the opposite color and flips each round. The two alternating colorings are distinct and nonmonochromatic, so this initial coloring violates winning.

The argument also handles odd cycles correctly: the assumed combination of conditions cannot occur there.

• Persistence of independence of the opposite color. Initially, all zero vertices belong to the independent complement of \(S\). Under this invariant, every current zero changes to one, and a current one changes to zero exactly when both neighbors are zero. Consequently, the displayed equivalence

\[ x_i(t+1)=0\quad\Longleftrightarrow\quad x_{i-1}(t)=x_{i+1}(t)=0 \]
is correct under the stated assumption.

Applying it to two adjacent alleged zeros at the next time forces those same two adjacent vertices to have been zero at the current time, contradicting independence. The induction is sound, including for \(\tau=3\).

• Growth of the target-colored block. An initially selected adjacent pair provides a block of at least two ones. Every vertex in the block has itself and at least one neighbor colored one, so the whole block survives the next synchronous update.

The argument for a vertex immediately outside the block correctly covers both possible current colors. A one remains one because of its block neighbor; a zero becomes one because the established independence invariant gives it two one neighbors. Therefore the surviving block gains at least one vertex whenever it is proper. Starting with at least two vertices, the stated upper bound of \(\tau-2\) rounds follows.

The already monochromatic case requires no growth. When exactly one vertex remains outside the block, the same reasoning applies. Thus the sufficiency proof covers all permitted cycle sizes and initial colorings.

• Translation to exact optimization. The two constraints on the bits \(z_i\) express exactly the proved characterization: no cyclic edge has two unselected endpoints, and some cyclic edge has two selected endpoints. Minimizing the stated linear cost therefore minimizes winning-set cost.

The common denominator \(D\) is a positive integer divisible by every input denominator. Hence every \(W_i\) and \(Q\) is an integer, and multiplication by \(D>0\) preserves the budget inequality exactly. No rounding or numerical approximation is introduced.

• Dynamic-programming initialization and transitions. For each fixed first bit \(s\), the initialized prefix has length one, cost \(sW_1\), and no internal edge. Its flag must therefore be zero.

Each transition checks exactly the newly introduced edge, updates the flag precisely when that edge has two selected endpoints, and adds the new vertex’s cost. Unattainable entries are declared to have value \(+\infty\), providing the required initialization of other entries.

The justification for discarding more expensive prefixes is valid: future constraints and costs depend only on the last bit, the adjacent-pair flag, and the fixed first bit. No relevant information is omitted from the state.

• Closing edge and final decision. The condition \(b\lor s=1\) excludes precisely an uncovered closing edge. The condition \(h\lor(b\land s)=1\) requires a selected adjacent pair either within the prefix or on the closing edge. Taking the minimum over both first-bit choices covers every cyclic selection.

Selecting all vertices supplies an accepted state, so the optimum \(K\) is finite. Comparing \(K\) with \(Q\) answers the original decision problem exactly.

• Arithmetic and bit complexity. There are four states per position for each of two first-bit choices, with at most two transitions per state. Thus the dynamic program uses \(\mathcal{O}(\tau)\) arithmetic operations.

The product defining \(D\) has \(\mathcal{O}(L)\) bits because the denominator encodings have total length at most \(L\). The bounds \(W_i\le D\) and \(Q\le D\) follow from the mass and budget ranges. Every finite table entry is a subset cost and is also at most \(D\).

Computing the common denominator and scaled costs requires \(\mathcal{O}(\tau)\) multiplications and divisions on integers of \(\mathcal{O}(L)\) bits. Elementary arithmetic therefore gives the claimed bound
\[ \mathcal{O}(\tau L^2)=\mathcal{O}((m+\tau)L^2), \]
since \(m=\tau\). This is polynomial in input length even when the numerical denominator is large.

• Edge cases, citation, and reported checks. The smallest permitted cycle, odd and even cycles, the full selected set, and an initially monochromatic coloring are covered by the written proof. Budgets \(q=0\) and \(q=1\) require no modification to the algorithm.

The cited [Theorem 3.2](https://link.springer.com/article/10.1007/s10458-024-09651-y) does state the claimed minimum cardinality for MM on cycles. The submitted argument does not rely on that theorem to establish its stronger characterization.

The reported exhaustive checks are not independently reproducible from the supplied output because no code or execution records are included. They are explicitly supplementary, however, and no proof step depends on them. This creates no gap in the mathematical conclusion.

Repair feedback: No mathematical clarification or repair is required. Providing the computational artifacts would make the supplementary checks auditable, but is unnecessary to verify the result.

⟨structured verdict parsed — rendered above⟩