d4-conf-ijcai-2022-0484 (d4-conf-ijcai-2022-0484)

Given a finite role set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a symmetric regular interaction kernel \(W\), a seed-mass budget \(\kappa\), and a rational threshold \(b\), decide whether there are masses \(z_t\in[0,\mu_t]\) with \(\sum_t z_t=\kappa\) and \(-\operatorname{Cut}_W(z)/(2\delta)\ge b\), where \(\operatorname{Cut}_W(z)=\sum_{t,u\in T}W_{tu}z_t(\mu_u-z_u)\) and \(\sum_u\mu_uW_{tu}=\delta\).

A society is specified by its support \(T\): the list of its \(\tau=|T|\ge2\) roles with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) counts supported types, not all possible types.
The interaction kernel is an explicitly encoded symmetric matrix \(W\in\mathbb{Q}_{\ge0}^{T\times T}\), with \(W_{tt}=0\), connected positive-weight support, and \(\sum_u\mu_uW_{tu}=\delta>0\) for every \(t\). Let \(m\) count unordered positive-weight role pairs and \(L\) be the total binary input length.
Given a binary-rational budget \(\kappa\in[0,1]\) and threshold \(b\in\mathbb{Q}\), feasible seed masses are real numbers \(z_t\in[0,\mu_t]\) with \(\sum_tz_t=\kappa\). Define \(\operatorname{Cut}_W(z)=\sum_{t,u\in T}W_{tu}z_t(\mu_u-z_u)\).
The decision problem asks whether a feasible \(z\) satisfies \(-\operatorname{Cut}_W(z)/(2\delta)\ge b\).

Is this decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

Discrete fixation maximization with favorable bias is NP-hard even on connected regular undirected graphs; its weak-selection objective differs from the negative seed cut by a term constant at fixed seed cardinality. [Durocher et al.](https://arxiv.org/pdf/2201.08207)
Continuous quadratic formulations of graph partitioning are known, but the verified formulation adds a diagonal term to the cut objective; it does not settle the exact kernel problem above. [Hager, Phan, and Zhang](https://www.math.lsu.edu/~hozhang/papers/graph.pdf) No result settling this exact mass problem was located.

Result

The decision problem is \(\mathrm{NP}\)-hard, even when all masses are equal dyadic rationals, every off-diagonal kernel entry is a positive integer, and the positive-weight support is complete.

The reduction uses two roles for each auxiliary graph vertex. Equalizing the seed masses within each pair creates an effective diagonal quadratic term. A rounding argument then proves that fractional seeds cannot improve upon selecting whole pairs.

1. Source problem and padding

We reduce from minimum bisection on simple cubic graphs: given a graph \(G=(V,E)\) with \(n=|V|\) and an integer \(q\), decide whether some \(S\subseteq V\), with \(|S|=n/2\), has at most \(q\) crossing edges. This problem is \(\mathrm{NP}\)-hard; the cited [Durocher et al. paper, Theorem 2](https://arxiv.org/pdf/2201.08207), explicitly invokes this hardness result.

Because \(G\) is cubic, \(n\) is even. We may restrict to \(0\le q\le |E|\): thresholds outside this interval have an immediate answer. Write \(k=n/2\).

Choose the smallest power of two \(N\) satisfying \(N\ge 2n\). Thus \(2n\le N<4n\). Add a set \(R\) of \(r=N-n\) auxiliary vertices, so \(r\ge n>k\), and put \(I=V\cup R\).

Let \(H=|E|+1\). Define symmetric weights \(c_{ij}\), for distinct \(i,j\in I\), by

\( c_{ij}=1+\mathbf{1}_{\{\{i,j\}\in E\}}+ H\mathbf{1}_{\{i,j\in R\}}, \qquad c_{ii}=0. \)

Here original edges belong to \(V\); consequently the two indicator terms never overlap.

For \(A\subseteq I\), define its weighted cut by

\( C(A)=\sum_{\substack{i\in A\\j\in I\setminus A}}c_{ij}. \)

If \(|A|=k\), put \(p=|A\cap R|\) and \(S=A\cap V\). The complete-graph contribution is \(k(N-k)\), the original-edge contribution is the number \(\operatorname{cut}_G(S)\) of crossing edges in \(G\), and the auxiliary-clique contribution is \(Hp(r-p)\). Hence

\( C(A)=k(N-k)+\operatorname{cut}_G(S)+Hp(r-p). \)

Define \(B=k(N-k)+q\). If \(p\ge1\), then \(p\le k<r\), so \(p(r-p)\ge1\). Since \(\operatorname{cut}_G(S)\ge0\) and \(H>q\), this implies \(C(A)>B\).

Therefore

\( \exists A\subseteq I:\ |A|=k,\ C(A)\le B \quad\Longleftrightarrow\quad \exists S\subseteq V:\ |S|=n/2,\ \operatorname{cut}_G(S)\le q. \)

The padding makes the eventual masses dyadic without changing the answer.

2. Constructing the society

Define

\( d_i=\sum_{j\ne i}c_{ij},\qquad d_*=\max_{i\in I}d_i,\qquad D=4d_*,\qquad M_i=D-2d_i. \)

Since \(c_{ij}\ge1\) for distinct vertices, \(d_*>0\). Moreover, \(M_i\ge2d_*>0\).

Create two roles \((i,0),(i,1)\) for each \(i\in I\). Set

\( T=I\times\{0,1\},\qquad \mu_{(i,a)}=\frac1{2N},\qquad \kappa=\frac{k}{N}. \)

Both the masses and the budget are dyadic rationals because \(N\) is a power of two.

Define the kernel by

\( W_{(i,0),(i,1)}=W_{(i,1),(i,0)}=M_i, \)

and, whenever \(i\ne j\), by

\( W_{(i,a),(j,b)}=c_{ij} \quad\text{for all }a,b\in\{0,1\}. \)

Set every diagonal entry to zero.

This kernel is symmetric, and every off-diagonal entry is positive. Its support is therefore connected. Each role has weighted row sum

\( \sum_{u\in T}\mu_uW_{(i,a),u} =\frac{M_i+2d_i}{2N} =\frac{D}{2N}. \)

Thus the required common value is \(\delta=D/(2N)>0\). All society hypotheses hold.

For every feasible \(z\), regularity gives the identity

\( \operatorname{Cut}_W(z) =\sum_t z_t\sum_u\mu_uW_{tu}-z^{\mathsf T}Wz =\delta\kappa-z^{\mathsf T}Wz. \)

Consequently, minimizing the cut is equivalent to maximizing \(z^{\mathsf T}Wz\).

3. Fractional seeds can be rounded to whole pairs

We prove that every feasible \(z\) can be replaced by a feasible vector selecting exactly \(k\) whole pairs, with no larger cut.

Equalization within pairs

Let \(s_i=z_{(i,0)}+z_{(i,1)}\). The quadratic objective is

\( z^{\mathsf T}Wz =2\sum_i M_i z_{(i,0)}z_{(i,1)} +2\sum_{i<j}c_{ij}s_is_j. \)

For fixed \(s_i\), replacing both coordinates of pair \(i\) by \(s_i/2\) is feasible: \(0\le s_i\le1/N\). This replacement preserves the total seed mass and all terms involving other pairs. It does not decrease the internal term, because

\( z_{(i,0)}z_{(i,1)} \le \frac{s_i^2}{4}, \)

which follows from \((z_{(i,0)}-z_{(i,1)})^2\ge0\).

After equalizing all pairs, define \(x_i=Ns_i\). Then

\( 0\le x_i\le1,\qquad \sum_i x_i=k, \)

and

\( z^{\mathsf T}Wz=\frac{Q(x)}{N^2}, \qquad Q(x)=\frac12\sum_iM_ix_i^2+ 2\sum_{i<j}c_{ij}x_ix_j. \)

Rounding the pair totals

Suppose \(x\) has a fractional coordinate. Since \(\sum_i x_i=k\) is an integer, it must have at least two fractional coordinates, say \(x_i,x_j\).

Vary these coordinates as \(x_i+t,x_j-t\), preserving their sum. The feasible interval is

\( \max\{-x_i,x_j-1\}\le t\le \min\{1-x_i,x_j\}. \)

Because both coordinates are fractional, zero lies strictly between the endpoints. At either endpoint, at least one coordinate becomes zero or one.

Along this interval, \(Q\) is a quadratic polynomial in \(t\). Its quadratic coefficient is

\( \frac{M_i+M_j}{2}-2c_{ij}. \)

Since \(M_i,M_j\ge2d_*\) and \(c_{ij}\le d_*\), this coefficient is nonnegative. Thus the polynomial is convex. Its value at zero cannot exceed the larger of its endpoint values, by the defining convexity inequality.

Choose an endpoint with value at least \(Q(x)\). This reduces the number of fractional coordinates and does not decrease the objective. Repeating finitely many times yields \(y\in\{0,1\}^I\) satisfying

\( \sum_i y_i=k,\qquad Q(y)\ge Q(x). \)

The corresponding seed vector is

\( z'_{(i,0)}=z'_{(i,1)}=\frac{y_i}{2N}. \)

Combining equalization, rounding, and the identity from Section 2 proves

\( \operatorname{Cut}_W(z')\le\operatorname{Cut}_W(z). \)

This establishes the required equivalence for all feasible real seed vectors.

4. Threshold equivalence

For a whole-pair seed vector, let \(A=\{i:y_i=1\}\). Internal pair edges contribute nothing to the cut. For each auxiliary graph pair crossing between \(A\) and its complement, the four role pairs contribute a total of \(c_{ij}/N^2\). Hence

\( \operatorname{Cut}_W(z')=\frac{C(A)}{N^2}. \)

Because \(2\delta=D/N\), it follows that

\( -\frac{\operatorname{Cut}_W(z')}{2\delta} =-\frac{C(A)}{DN}. \)

Set the input threshold to

\( b=-\frac{B}{DN} =-\frac{k(N-k)+q}{DN}. \)

If the original graph has a bisection of cut at most \(q\), selecting its corresponding whole pairs achieves the threshold.

Conversely, if any feasible real seed vector achieves the threshold, Section 3 replaces it by a whole-pair vector whose score is at least as large. Its selected set \(A\) satisfies \(C(A)\le B\). Section 1 then forces \(A\cap R=\varnothing\) and gives a bisection of \(G\) with cut at most \(q\).

Thus the original and constructed decision instances have exactly the same answer.

5. Polynomial encoding and conclusion

There are \(\tau=2N=O(n)\) supported roles and \(m=\binom{2N}{2}=O(n^2)\) positive unordered role pairs.

Since \(G\) is cubic, \(H=O(n)\), \(d_*=O(n^2)\), and \(D,M_i=O(n^2)\). Every kernel entry, mass, budget, and threshold has \(O(\log n)\) bits. The total output length is \(L=O(n^2\log n)\), and the construction takes polynomial time.

This is a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness. In particular, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the task: the decision problem is \(\mathrm{NP}\)-hard under all the stated society constraints. No major or minor mathematical gaps were found.

• Source problem and cited hardness

The source problem is stated precisely: minimum bisection on simple cubic graphs, with an integer cut threshold. The proof of Theorem 2 in the cited [Durocher et al. paper](https://arxiv.org/pdf/2201.08207) explicitly invokes NP-hardness of minimum bisection on 3-regular graphs, citing Bui et al.

Cubicity implies that \(n\) is even by the degree-sum identity \(3n=2|E|\), so \(k=n/2\) is an integer. Restricting the source thresholds to \(0\le q\le |E|\) is legitimate: excluded thresholds have immediate answers. No connectedness assumption on the source graph is needed, since the constructed kernel has complete positive support.

• Padding and preservation of the discrete answer

The chosen power of two satisfies \(2n\le N<4n\). Therefore \(r=N-n\ge n>k\).

The cut decomposition
\[ C(A)=k(N-k)+\operatorname{cut}_G(A\cap V)+Hp(r-p) \]
is correct for every \(A\subseteq I\) with \(|A|=k\):

• The unit complete-graph weights contribute \(k(N-k)\).
• The original-edge increments contribute precisely the edges of \(G\) crossing \(A\cap V\).
• The auxiliary-clique increments contribute \(Hp(r-p)\).

If \(p\ge1\), then \(1\le p\le k<r\), so \(p(r-p)\ge1\). Since \(H=|E|+1>q\), such a set has \(C(A)>B\). If \(p=0\), the threshold condition is exactly the original bisection condition. Both directions of the asserted equivalence follow.

• Admissibility of the constructed society

Every constructed mass is positive, and the \(2N\) masses sum to one. The masses and budget are dyadic because \(N\) is a power of two. Also, \(0<k/N<1\), so the budget is admissible.

The bounds
\[ M_i=4d_*-2d_i\ge2d_*>0 \]
hold because \(d_i\le d_*\) and the complete positive auxiliary weights imply \(d_*>0\).

The kernel is symmetric, has zero diagonal, and has positive integer entries everywhere off the diagonal. Its support is complete and connected.

Each role has the required common weighted row sum:
\[ \frac{M_i+2d_i}{2N}=\frac{D}{2N}=\delta>0. \]
Thus every hypothesis in the task is satisfied.

Expanding the cut and using regularity and the budget gives
\[ \operatorname{Cut}_W(z)=\delta\kappa-z^{\mathsf T}Wz. \]
Consequently, the objective comparison used throughout the proof has the correct direction.

• Equalization within pairs

The quadratic expansion has the correct factors:
\[ z^{\mathsf T}Wz =2\sum_iM_i z_{(i,0)}z_{(i,1)} +2\sum_{i<j}c_{ij}s_is_j. \]

For fixed \(s_i\), replacing the two coordinates by \(s_i/2\) respects their individual capacities because \(s_i\le1/N\). It preserves the total budget and every contribution involving other pairs.

The product inequality is valid, and \(M_i>0\), so equalization cannot decrease the quadratic objective. After equalization, the substitution \(x_i=Ns_i\) gives precisely
\[ Q(x)=\frac12\sum_iM_ix_i^2+ 2\sum_{i<j}c_{ij}x_ix_j, \qquad z^{\mathsf T}Wz=\frac{Q(x)}{N^2}. \]

• Rounding all real feasible vectors

An integer coordinate sum rules out exactly one fractional coordinate. Thus, whenever rounding is needed, two fractional coordinates exist.

The stated interval for \(t\) exactly describes the simultaneous constraints on \(x_i+t\) and \(x_j-t\). Zero is strictly inside this interval when both coordinates are fractional.

Direct expansion confirms that the quadratic coefficient is
\[ \frac{M_i+M_j}{2}-2c_{ij}. \]
Since \(M_i,M_j\ge2d_*\) and \(c_{ij}\le d_i\le d_*\), this coefficient is nonnegative.

The polynomial is therefore convex on the interval, so its value at zero is at most the larger endpoint value. Moving to such an endpoint preserves feasibility and the objective comparison. At least one fractional coordinate becomes integral; previously integral coordinates are untouched. The procedure consequently terminates after finitely many steps.

The resulting whole-pair vector has exactly \(k\) selected pairs and no larger cut. This argument covers arbitrary real coordinates; no rationality assumption on feasible seeds is introduced.

• Threshold translation and encoding

For whole-pair seeds, internal pair edges contribute zero. Across each selected–unselected auxiliary pair, exactly four ordered terms have a nonzero seeded first coordinate and an unseeded second coordinate. Their total is \(c_{ij}/N^2\). Hence
\[ \operatorname{Cut}_W(z')=\frac{C(A)}{N^2}, \qquad -\frac{\operatorname{Cut}_W(z')}{2\delta} =-\frac{C(A)}{DN}. \]
There is no missing factor of two.

Since \(DN>0\), the chosen threshold makes the score condition equivalent to \(C(A)\le B\). Rounding preserves threshold satisfaction, and padding then forces the selected set to be an original bisection. The reduction preserves both yes-instances and no-instances.

Finally, \(N=O(n)\), \(H=O(n)\), and \(d_*,D,M_i=O(n^2)\). The threshold numerator is \(O(n^2)\), and its denominator is \(O(n^3)\). Thus all numerical entries have \(O(\log n)\) bits, and the explicitly encoded matrix has total length \(O(n^2\log n)\). The construction is polynomial in the source input length.

No repair or additional clarification is required. The proof establishes NP-hardness; its final qualification that a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\) is appropriate.

⟨structured verdict parsed — rendered above⟩