d4-conf-wine-2019-0031 (d4-conf-wine-2019-0031)

Given a connected graph \(G=(V,E)\) with \(|V|\ge 2\), maximum degree \(\Delta_G\), and \(\tau>3\Delta_G/(3\Delta_G+1)\), choose masses \(x_{v,i}\ge 0\) for \(v\in V\) and \(i\in\{R,B\}\), with \(x_{v,R}+x_{v,B}=1/|V|\) for each \(v\) and \(\sum_v x_{v,i}=1/2\) for each type. Define \(r_{v,i}(x)=\frac{\sum_{u\in N(v)}x_{u,i}}{\sum_{u\in N(v)}(x_{u,R}+x_{u,B})}\). Find a feasible allocation maximizing \(\sum_{v,i}x_{v,i}\mathbf{1}[r_{v,i}(x)\ge\tau]\), the mass of content residents, where each district's residents see the type mixture across all adjacent districts.

Given a connected simple unweighted undirected graph \(G=(V,E)\), let \(m=|V|\ge 2\) and \(\Delta_G=\max_{v\in V}\deg_G(v)\). The input includes a binary rational intolerance threshold \(\theta\) satisfying \(3\Delta_G/(3\Delta_G+1)<\theta<1\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) denotes support size, not the number of possible types. Here the support is \(\{R,B\}\), with \(\tau=2\) and mass \(1/2\) per type, so total mass is \(1\).
An allocation consists of divisible real masses \(x_{v,i}\ge 0\) satisfying \(x_{v,R}+x_{v,B}=1/m\) for every \(v\), and \(\sum_{v\in V}x_{v,i}=1/2\) for each \(i\in\{R,B\}\).
Let \(N(v)=\{u\in V:\{u,v\}\in E\}\) and \(r_{v,i}(x)=\frac{\sum_{u\in N(v)}x_{u,i}}{\sum_{u\in N(v)}(x_{u,R}+x_{u,B})}\). All type-\(i\) residents at \(v\) are content exactly when \(r_{v,i}(x)\ge\theta\), including equality.
Maximize \(F(x)=\sum_{v\in V}\sum_{i\in\{R,B\}}x_{v,i}\mathbf{1}[r_{v,i}(x)\ge\theta]\) over all feasible allocations; no equilibrium or movement constraint is imposed. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).

Is exact maximization of \(F\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For indivisible residents, maximizing the number content is NP-hard on arbitrary graphs in this threshold regime, even with two equally numerous types and every vertex occupied ([source](https://hpi.de/friedrich/docs/publications/2019/WINE.pdf)).
Existing work on continuous type values retains finitely many indivisible agents occupying distinct vertices ([source](https://ceur-ws.org/Vol-3587/9970.pdf)); no result settling this exact divisible-mass problem was located.

Result

Exact maximization is \(\mathrm{NP}\)-hard, even with \(\tau=2\), equal type masses, and an intolerance threshold of binary encoding length \(O(\log m)\).

The essential step is to control the benefit of divisibility. For a suitable threshold, the divisible optimum determines the indivisible optimum by rounding down its normalized value.

1. Normalization and the discrete source problem

Write \(d_v=\deg_G(v)\), \(\Delta=\Delta_G\), and introduce
\[ y_v=m x_{v,R}. \]
Then \(m x_{v,B}=1-y_v\), and feasibility becomes
\[ 0\le y_v\le1,\qquad \sum_{v\in V}y_v=\frac m2. \]
Connectedness and \(m\ge2\) ensure \(d_v\ge1\). The neighborhood fractions are
\[ r_{v,R}=\frac1{d_v}\sum_{u\in N(v)}y_u,\qquad r_{v,B}=1-r_{v,R}. \]
Let \(H_\theta(y)=mF(x)\). Thus
\[ H_\theta(y)= \sum_v y_v\mathbf1[r_{v,R}\ge\theta] +\sum_v(1-y_v)\mathbf1[r_{v,B}\ge\theta]. \]

For an even-order graph, define \(C(G)\) as the maximum number of content vertices among balanced pure assignments \(z\in\{0,1\}^V\), where a vertex is content precisely when every neighbor has its own color.

We use the following discrete hardness consequence supplied in the question: deciding whether \(C(G)\ge K\) is \(\mathrm{NP}\)-hard on connected simple graphs of even order. The reduction in Theorem 14 of [Echzell et al., *Convergence and Hardness of Strategic Schelling Segregation*](https://hpi.de/friedrich/docs/publications/2019/WINE.pdf) establishes value hardness with two equally numerous types and full occupancy.

To check the content criterion, a pure vertex with an opposite-colored neighbor has same-color fraction at most
\[ 1-\frac1{d_v}\le1-\frac1\Delta <\frac{3\Delta}{3\Delta+1}. \]
Consequently, throughout the stated discrete threshold regime, content is equivalent to having no opposite-colored neighbor. This establishes the formulation of \(C(G)\) used here.

2. A rounding lemma for divisible allocations

Lemma. Suppose \(m\) is even and choose
\[ \varepsilon=\frac1{8m\Delta}, \qquad \theta=1-\varepsilon. \]
For every feasible divisible allocation \(y\), there is a balanced pure assignment \(z\) with at least
\[ H_\theta(y)-\frac14 \]
content vertices.

Proof. Set
\[ \delta=\Delta\varepsilon=\frac1{8m}. \]
Define the sets of vertices whose neighborhoods satisfy the respective content conditions:
\[ A=\{v:r_{v,R}(y)\ge\theta\}, \qquad B=\{v:r_{v,B}(y)\ge\theta\}. \]
Because \(\theta>1/2\) and the two neighborhood fractions sum to one, \(A\cap B=\varnothing\).

For \(v\in A\),
\[ \sum_{u\in N(v)}(1-y_u)\le d_v\varepsilon. \]
All summands are nonnegative, so every \(u\in N(v)\) satisfies
\[ 1-y_u\le d_v\varepsilon\le\delta. \]
Similarly, \(v\in B\) implies \(y_u\le\delta\) for every \(u\in N(v)\).

Let
\[ S_R=\bigcup_{v\in A}N(v), \qquad S_B=\bigcup_{v\in B}N(v). \]
These sets are disjoint: membership in both would require \(y_u\ge1-\delta\) and \(y_u\le\delta\), whereas \(\delta<1/2\).

Moreover, both sets contain at most \(m/2\) vertices. Indeed, balance gives
\[ \frac m2=\sum_v y_v \ge |S_R|(1-\delta), \]
hence
\[ |S_R|\le\frac m2+|S_R|\delta \le\frac m2+m\delta =\frac m2+\frac18. \]
Since \(m/2\) and \(|S_R|\) are integers, \(|S_R|\le m/2\). Applying the same argument to \(1-y_v\) gives \(|S_B|\le m/2\).

We now force the required neighbors to be pure. Define \(q^0\) by
\[ q^0_u= \begin{cases} 1,&u\in S_R,\\ 0,&u\in S_B,\\ y_u,&u\notin S_R\cup S_B. \end{cases} \]
Its total modification satisfies
\[ D:=\sum_u|q^0_u-y_u| \le(|S_R|+|S_B|)\delta \le m\delta=\frac18. \]
Write \(\sum_u q^0_u=m/2+t\). Then \(|t|\le D\).

We can restore balance by modifying only coordinates in
\[ T=V\setminus(S_R\cup S_B). \]
Their required total is
\[ k=\frac m2-|S_R|. \]
The established cardinality bounds imply \(0\le k\le|T|\). Thus, if \(t>0\), free coordinates can be decreased by a total of \(t\); if \(t<0\), they can be increased by a total of \(-t\). Distributing the change until the required total is reached gives a vector \(q\) satisfying
\[ q_{S_R}=1,\qquad q_{S_B}=0,\qquad \sum_u q_u=\frac m2,\qquad \sum_u|q_u-y_u|\le2D\le\frac14. \]

Consider the linear function
\[ \ell(w)=\sum_{v\in A}w_v+\sum_{v\in B}(1-w_v). \]
By definition, \(\ell(y)=H_\theta(y)\). Since \(A\cap B=\varnothing\), every coordinate coefficient in \(\ell\) has absolute value at most one. Therefore
\[ \ell(q)\ge H_\theta(y)-\sum_u|q_u-y_u| \ge H_\theta(y)-\frac14. \]

Finally, maximize \(\ell\) over the polytope
\[ P=\left\{ w\in[0,1]^V: w_{S_R}=1,\ w_{S_B}=0,\ \sum_u w_u=\frac m2 \right\}. \]
This polytope is nonempty because \(q\in P\), and it is compact. It has an integral maximizer. To see this directly, start with any maximizer. If two free coordinates are fractional, transfer mass between them in the direction that does not decrease \(\ell\), until one becomes integral. Repeat. The remaining free-coordinate sum is the integer \(k\), so exactly one fractional coordinate cannot remain. The resulting maximizer \(z\) is pure and balanced, with \(\ell(z)\ge\ell(q)\).

Every vertex counted by \(\ell(z)\) is content: a red vertex in \(A\) has all neighbors in \(S_R\), hence all red; a blue vertex in \(B\) has all neighbors in \(S_B\), hence all blue. Thus the content count of \(z\) is at least \(\ell(z)\), proving the lemma. \(\square\)

3. Recovering the discrete optimum

Let
\[ H^*(G,\theta)=\max_y H_\theta(y). \]
Existence of this maximum also follows from the finite linear-program formulation below.

The rounding lemma gives
\[ H^*(G,\theta)\le C(G)+\frac14. \]
Conversely, a pure assignment achieving \(C(G)\) is feasible for the divisible problem. Each of its monochromatic-neighborhood vertices contributes one to \(H_\theta\), so
\[ H^*(G,\theta)\ge C(G). \]
Consequently,
\[ C(G)\le H^*(G,\theta)\le C(G)+\frac14, \qquad C(G)=\left\lfloor H^*(G,\theta)\right\rfloor. \]
Equivalently,
\[ C(G)=\left\lfloor m\max_x F(x)\right\rfloor. \]

This argument does not assert that a divisible optimum is pure; it only bounds its advantage sufficiently to recover the discrete optimum.

4. Polynomial reduction and threshold verification

Given a discrete instance \((G,K)\), retain the graph, use the prescribed two masses \(1/2\), and set
\[ \theta=1-\frac1{8m\Delta}, \qquad q=\frac Km. \]
The chosen threshold satisfies the input promise because
\[ 8m\Delta>3\Delta+1, \]
and therefore
\[ \frac{3\Delta}{3\Delta+1}<\theta<1. \]

The preceding bounds show
\[ C(G)\ge K \quad\Longleftrightarrow\quad \max_x F(x)\ge\frac Km. \]
For the reverse implication, if \(C(G)<K\), integrality gives \(C(G)\le K-1\), and hence
\[ m\max_x F(x)\le K-\frac34<K. \]

Because \(1\le\Delta\le m-1\), the threshold has binary encoding length \(O(\log m)\). The graph is unchanged, and computing the new numerical data takes polynomial time in the binary input length. This is a polynomial many-one reduction to the divisible decision problem.

Thus exact maximization is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\), already for \(\tau=2\).

5. Exact finite formulation and running time

For completeness, exact optimization has a finite linear-program formulation, despite the discontinuous objective.

For each labeling
\[ \sigma:V\longrightarrow\{\varnothing,R,B\}, \]
use the normalized feasibility constraints and impose
\[ \sum_{u\in N(v)}y_u\ge d_v\theta \quad\text{if }\sigma(v)=R, \]
and
\[ \sum_{u\in N(v)}y_u\le d_v(1-\theta) \quad\text{if }\sigma(v)=B. \]
Maximize the linear objective
\[ \ell_\sigma(y)= \sum_{\sigma(v)=R}y_v+ \sum_{\sigma(v)=B}(1-y_v). \]
Discard infeasible programs.

Every feasible point of a labeled program satisfies its selected content conditions, so \(\ell_\sigma(y)\le H_\theta(y)\). Conversely, every feasible allocation belongs to the program labeling all its satisfied content conditions, and that program's objective equals \(H_\theta(y)\). Taking the maximum over the finitely many programs therefore gives exactly \(H^*(G,\theta)\). Each feasible program is compact, so this also proves attainment.

There are \(3^m\) programs, each with \(m\) variables, \(O(m)\) constraints, and polynomial encoding length. Rational linear programming therefore gives an exact algorithm in
\[ 3^m\,\operatorname{poly}(m,\tau,L), \qquad \tau=2. \]
For the decision version, guessing a labeling and solving its linear program is a polynomial-time nondeterministic procedure. Combined with the reduction, the decision problem is \(\mathrm{NP}\)-complete.

⟨structured verdict parsed — rendered above⟩

The output resolves the task. The rounding lemma is valid, the reduction preserves the input promises, and the finite linear-program formulation correctly establishes attainment and the stated exponential running time. I found no mathematical gaps requiring repair.

1. Normalization and discrete hardness

The substitution \(y_v=mx_{v,R}\) correctly transforms the allocation constraints into
\[ 0\le y_v\le 1,\qquad \sum_v y_v=\frac m2. \]
The neighborhood denominator is \(d_v/m\). Connectedness and \(m\ge2\) ensure \(d_v>0\), so both neighborhood-fraction formulas are valid. Multiplying the objective by \(m\) gives exactly the stated \(H_\theta\).

For pure assignments, an opposite-colored neighbor implies
\[ r_{v,i}\le 1-\frac1{d_v}\le 1-\frac1\Delta <\frac{3\Delta}{3\Delta+1}<\theta. \]
The strict middle inequality holds for every \(\Delta\ge1\). Conversely, a monochromatic neighborhood has same-color fraction \(1\). Thus the stated definition of \(C(G)\) agrees exactly with discrete content in this regime.

The discrete hardness invocation matches the cited source. Section 1.2 specifies connected, unweighted, undirected networks; Theorem 14’s construction uses two equally numerous types with full occupancy and relates optimal placement cost to the minimum balanced cut value. Its clique replacement preserves connectedness and simplicity and produces even order from an even-order source graph. Thus the required value-decision hardness for balanced pure assignments is supported. [Echzell et al., Sections 1.2 and 4.1, Theorem 14](https://hpi.de/friedrich/docs/publications/2019/WINE.pdf).

2. Rounding lemma

Every step of the lemma checks out.

• Parameters and disjointness. The chosen values satisfy

\[ \delta=\Delta\varepsilon=\frac1{8m}<\frac12. \]
Also \(\theta>1/2\), so a vertex cannot satisfy both neighborhood content conditions. Hence \(A\cap B=\varnothing\).

• Forced-neighbor bounds. For \(v\in A\), the nonnegative deficits satisfy

\[ \sum_{u\in N(v)}(1-y_u)\le d_v\varepsilon. \]
Each individual deficit is therefore at most \(d_v\varepsilon\le\delta\). The corresponding blue bound follows identically. Consequently, membership in both \(S_R\) and \(S_B\) would require incompatible inequalities \(y_u\ge1-\delta\) and \(y_u\le\delta\).

• Cardinality bounds. Balance gives

\[ |S_R|(1-\delta)\le\frac m2, \]
and therefore
\[ |S_R|\le\frac m2+|S_R|\delta\le\frac m2+\frac18. \]
Since \(m\) is even, integrality yields \(|S_R|\le m/2\). Applying the same calculation to \(1-y_v\) proves the blue bound. The even-order hypothesis is used correctly here.

• Purification cost. Every forced coordinate changes by at most \(\delta\). Disjointness gives

\[ D\le(|S_R|+|S_B|)\delta\le\frac18. \]
The total imbalance satisfies \(|t|\le D\) by the triangle inequality.

• Restoring balance. The required free-coordinate total is the integer

\[ k=\frac m2-|S_R|. \]
The two cardinality bounds imply \(0\le k\le|T|\). The existing free-coordinate sum is \(k+t\), so the required increase or decrease is available within the coordinate bounds. A monotone adjustment changes the free coordinates by total absolute amount \(|t|\). Thus
\[ \sum_u|q_u-y_u|\le D+|t|\le2D\le\frac14. \]
This also covers \(T=\varnothing\): feasibility of the required total then forces \(k=t=0\).

• Objective control. The identity \(\ell(y)=H_\theta(y)\) follows directly from the definitions of \(A\) and \(B\), including threshold equality. Because these sets are disjoint, each coordinate coefficient has absolute value at most one. The resulting loss bound is valid.

• Integral maximizer. The polytope is nonempty and compact. The proposed transfer between two fractional free coordinates preserves feasibility and can be chosen not to decrease the linear objective. Starting from a maximizer, it remains at the maximum and makes at least one additional coordinate integral. A single fractional coordinate cannot remain because the free-coordinate sum is the integer \(k\). This proves the claimed integral maximizer without an unstated integrality theorem.

• Content after rounding. A red vertex in \(A\) has all neighbors forced red; a blue vertex in \(B\) has all neighbors forced blue. For integral \(z\), \(\ell(z)\) counts precisely these selected vertices, each of which is content. Other content vertices can only increase the count.

The lemma therefore establishes the asserted loss bound of \(1/4\).

3. Recovery of the discrete optimum

The lemma implies
\[ H^*(G,\theta)\le C(G)+\frac14. \]
A balanced pure optimum is feasible for the divisible problem and contributes \(C(G)\), giving the reverse bound
\[ H^*(G,\theta)\ge C(G). \]
Because \(C(G)\) is an integer and the upper error is strictly less than one,
\[ \left\lfloor H^*(G,\theta)\right\rfloor=C(G). \]

The argument correctly bounds the advantage of divisibility; it does not incorrectly claim that a divisible optimum must be pure.

4. Reduction and input promises

For \(m\ge2\) and \(\Delta\ge1\),
\[ 8m\Delta>3\Delta+1. \]
Thus the selected rational threshold satisfies the required strict promise. Its numerator and denominator have \(O(\log m)\) bits because \(\Delta\le m-1\).

For integer \(K\), the decision equivalence is correct. If \(C(G)\ge K\), the divisible optimum reaches \(K/m\). If \(C(G)<K\), then
\[ H^*(G,\theta)\le K-1+\frac14=K-\frac34<K. \]
Hence no divisible allocation reaches \(K/m\).

The construction retains the graph and sets the prescribed two equal masses. It is polynomial in the binary input length. Hardness on this even-order subclass suffices for the task, which also permits odd-order graphs. Likewise, selecting one valid threshold per reduction instance suffices because \(\theta\) is part of the input; hardness for every fixed threshold is not needed.

5. Finite formulation, attainment, and complexity

The labeled linear programs are correct:

• Every selected label enforces its corresponding content inequality, including equality.
• Their objectives never exceed the actual objective because omitted contributions are nonnegative.
• Since \(\theta>1/2\), every allocation’s satisfied conditions can be represented by a single label from \(\{\varnothing,R,B\}\) at each vertex.
• For that labeling, the linear objective equals the allocation’s actual objective.

Consequently, the maximum over these programs equals \(H^*\). Each feasible program has a compact feasible region, and there are finitely many programs, so the optimum is attained.

There are \(3^m\) programs. Each has \(m\) variables, \(O(m)\) constraints, and polynomial binary encoding length, even though neighborhood constraints can contain \(O(m^2)\) coefficients in total. Exact rational linear programming therefore supports the stated bound
\[ 3^m\,\operatorname{poly}(m,\tau,L),\qquad \tau=2. \]
The formulation also applies when \(m\) is odd.

For the rational-threshold decision problem, guessing a labeling and checking its linear-program optimum is a polynomial-time nondeterministic procedure. Together with the reduction, this establishes NP-completeness of that decision problem and NP-hardness of exact maximization.

No corrective feedback is required.

⟨structured verdict parsed — rendered above⟩