The Parameterized Complexity of Welfare Guarantees in Schelling Segregation (aamas24-00053)

Given a cubic graph \(G=(V,E)\) with \(n\) even and a society \(\mu=(\mu_R,\mu_B)=(1/2,1/2)\) of interchangeable red and blue types, assign \(n\mu_R\) red and \(n\mu_B\) blue agents one per vertex and compute a GWO assignment; equivalently, decide whether an assignment with at most \(k\) bichromatic edges exists.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here the masses sum to \(1\), with \(\mu_R=\mu_B=1/2\) and \(\tau=2\).
Given a nonempty simple undirected cubic graph \(G=(V,E)\), with even \(n=|V|\), and a binary integer \(k\geq 0\), an assignment is a coloring \(c:V\to\{R,B\}\) with exactly \(n/2\) vertices of each color. Each vertex holds one whole agent; types are interchangeable within each color.
An agent's utility is the fraction of its three neighbors having its color. Group welfare is the sum of utilities within that color. An assignment is group-welfare optimal (GWO) if no other feasible assignment weakly increases both group welfares and strictly increases at least one.
The decision problem asks whether a feasible assignment has at most \(k\) bichromatic edges. State running times in \(n\), \(m=|E|\), \(\tau\), and the total input bit length \(L\).

Is this distribution-input decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

Computing GWO assignments is known to be \(\mathrm{NP}\)-hard on fully occupied cubic graphs with equal color populations. [Deligkas, Eiben, and Goldsmith](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p425.pdf).
The stated distribution-input problem is exactly the same cubic minimum-bisection problem used in that hardness result; its complexity is already settled. Merely encoding the population by two masses does not create a distinct continuous problem.

Conclusion

The decision problem is \(\mathrm{NP}\)-complete, already for \(\tau=2\) and \(\mu_R=\mu_B=1/2\). Consequently, it is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).

Exact equivalence with cubic minimum bisection

For a subset \(S\subseteq V\), define its edge boundary by
\(\delta_G(S)=\{uv\in E:u\in S,\ v\notin S\}\).

A feasible coloring \(c\) determines the subset \(S=c^{-1}(R)\). The population constraint gives \(|S|=n/2\), and its bichromatic edges are exactly \(\delta_G(S)\). Conversely, every subset \(S\) of size \(n/2\) determines a feasible coloring by coloring \(S\) red and its complement blue. Therefore,

\(\exists\text{ feasible }c\text{ with at most }k\text{ bichromatic edges}\quad\Longleftrightarrow\quad\exists S\subseteq V:\ |S|=n/2,\ |\delta_G(S)|\leq k.\)

The right-hand side is precisely the decision version of minimum bisection on cubic graphs.

We use the established hardness result that minimum bisection is \(\mathrm{NP}\)-hard on simple undirected cubic graphs. This is the source problem used in the proof of Theorem 7 of [Deligkas, Eiben, and Goldsmith](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p425.pdf#page=5).

The many-one reduction takes an instance \((G,k)\) of that problem and outputs the same graph and threshold together with the fixed support list \(((R,1/2),(B,1/2))\). Because \(G\) is cubic, the degree-sum identity gives \(3n=2m\), so \(n\) is even. Thus the required populations \(n/2\) are integers. The equivalence above proves that the reduction preserves both yes-instances and no-instances.

The added distribution has constant encoding length. Hence the output bit length increases by only a constant, and the reduction takes \(O(L+n+m+\tau)\) time, including reading and copying the explicit input. In particular, it is polynomial in \(L\).

Why GWO coincides with minimum bisection here

Let \(b(c)\) denote the number of bichromatic edges. For each vertex \(v\), let \(d_{\mathrm{opp}}(v)\) count its neighbors of the opposite color. Full occupancy and cubic degree imply that its utility is \(1-d_{\mathrm{opp}}(v)/3\).

For either color \(X\in\{R,B\}\), its group welfare therefore satisfies

\(W_X(c)=\sum_{v:c(v)=X}\left(1-\frac{d_{\mathrm{opp}}(v)}3\right)=\frac n2-\frac13\sum_{v:c(v)=X}d_{\mathrm{opp}}(v)=\frac n2-\frac{b(c)}3.\)

The last equality holds because each bichromatic edge has exactly one endpoint of color \(X\), and therefore contributes exactly once to that sum. In particular, both group welfares are equal.

It follows that an assignment \(c'\) weakly increases both group welfares and strictly increases at least one exactly when \(b(c')<b(c)\). Thus an assignment is GWO if and only if it minimizes the number of bichromatic edges over all feasible assignments.

This also settles the interpretation that additionally requires the witness to be GWO: if any feasible assignment has at most \(k\) bichromatic edges, a minimum-cut feasible assignment exists, is GWO, and also meets the threshold.

Membership in \(\mathrm{NP}\) and running times

A certificate consists of the \(n\) color bits. The verifier counts red vertices, checks that their number is \(n/2\), scans the \(m\) edges, and compares the number of bichromatic edges with the binary integer \(k\).

On a word RAM, verification takes \(O(L+n+m+\tau)\) time, including input reading. Only counters of \(O(\log(n+m+2))\) bits are needed; the potentially longer encoding of \(k\) can be read and compared in time linear in its bit length. A straightforward implementation using sequential scans has polynomial bit complexity; the conservative bound \(O((L+n+m+\tau)^2)\) suffices. Hence the problem belongs to \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness proof.

For comparison, exhaustive enumeration gives a deterministic word-RAM bound of \(O(L+\tau+\binom{n}{n/2}(n+m))\), and therefore \(O(L+\tau+2^n(n+m))\). Here \(m=3n/2\) and \(\tau=2\). Fixed support size does not remove the combinatorial choice of which vertices receive each whole agent.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated decision problem correctly: it is \(\mathrm{NP}\)-complete. No major or minor mathematical gaps were found.

• The decision problem is identified exactly.

The correspondence \(c\mapsto c^{-1}(R)\) is a bijection between feasible colorings and subsets of size \(n/2\). Under this correspondence, an edge is bichromatic exactly when it belongs to \(\delta_G(S)\). Thus the displayed equivalence preserves both the balance constraint and the threshold. Interchangeability within each color introduces no additional constraint.

• The hardness citation is applicable.

The invoked result concerns minimum bisection on simple undirected cubic graphs, matching the required graph class. The proof of Theorem 7 in the cited paper explicitly uses cubic minimum bisection, with an integer threshold and two equal parts, as its source problem. The attribution is accurate. [Deligkas, Eiben, and Goldsmith, Theorem 7](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p425.pdf#page=5).

The prover does not incorrectly infer decision hardness merely from hardness of computing GWO assignments: it explicitly invokes hardness of the underlying minimum-bisection decision problem.

• The many-one reduction is valid.

Keeping \(G\) and \(k\), and adding the fixed support list, produces precisely the required instance. The identity \(3n=2m\) correctly implies that \(n\) is even. The masses are positive binary rationals, sum to \(1\), and impose integer populations \(n/2\).

The equivalence already established proves preservation of yes-instances and no-instances. The constant additional encoding length and the stated copying-time bound are valid for the explicit input representation.

• The welfare computation and GWO equivalence are correct.

Full occupancy and degree three justify the utility formula. For each color separately, every bichromatic edge contributes exactly once to the sum of opposite-color degrees. Consequently,
\[ W_R(c)=W_B(c)=\frac n2-\frac{b(c)}3. \]
Both welfares depend on the same quantity with the same strictly negative coefficient. Therefore, weak improvement of both with strict improvement of at least one occurs exactly when the bichromatic-edge count decreases.

The conclusion that GWO assignments are exactly minimum bisections follows. The additional interpretation requiring a GWO witness is also handled correctly: the feasible set is finite and nonempty, so the stated minimum exists.

• Membership in \(\mathrm{NP}\) is established.

The certificate has \(n\) bits. Counting one color suffices to verify both populations, and scanning the edges computes the threshold quantity exactly. The treatment of a potentially long binary encoding of \(k\) avoids assuming that \(k\) fits in a machine word.

The word-RAM bound \(O(L+n+m+\tau)\) and conservative polynomial bit-complexity bound are adequate. No verification of GWO is required for the decision problem as stated.

• The enumeration bound and edge cases are consistent.

There are exactly \(\binom{n}{n/2}\) feasible colorings. The stated enumeration bounds correctly account for evaluating each coloring and reading the input. Substituting \(m=3n/2\) and \(\tau=2\) is valid.

Disconnected graphs are allowed throughout. The arguments also cover \(k=0\) and thresholds exceeding the number of edges. A nonempty simple cubic graph has no isolated vertices, so no undefined utility denominator occurs.

No additional clarification is needed. The output classifies the specified distribution-input problem; it does not rely on fractional assignments or a different interpretation of support size.

⟨structured verdict parsed — rendered above⟩