d4-conf-atal-2016-0057 (d4-conf-atal-2016-0057)

Given a finite type set (\Theta), rational masses (\mu_i) summing to \(1\), nonnegative rational contact intensities (a_{ij}), and a rational intervention budget (\beta), choose rational intervention masses (x_i\in[0,\mu_i]) with (\sum_i x_i\le\beta). Set (y_j^{(0)}=x_j) and (y_j^{(1)}=y_j^{(0)}+(\mu_j-y_j^{(0)})(1-\exp(-\sum_i a_{ij}y_i^{(0)}))). For rational (\varepsilon>0), compute a feasible allocation whose total influenced mass (\sum_j y_j^{(1)}) is within (\varepsilon) of the maximum.

A society is given by its support \(\Theta=\{1,\ldots,\tau\}\): the list of types with positive binary-rational masses \(\mu_i\), with \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
Directed contact intensities \(a_{ij}\ge0\) are binary rationals; within-type contacts \(a_{ii}\) are allowed. Let \(m\) count positive contact intensities and \(L\) be the total input bit length, including the rational budget \(0<\beta\le1\) and tolerance \(\varepsilon>0\).
All mass is initially uninfluenced. One intervention chooses rational masses \(0\le x_i\le\mu_i\), with \(\sum_i x_i\le\beta\), which become influenced with certainty.
After exactly one propagation step, \(y_j^{(0)}=x_j\) and \(y_j^{(1)}=x_j+(\mu_j-x_j)(1-\exp(-\sum_i a_{ij}x_i))\). Define \(F(x)=\sum_j y_j^{(1)}\) and \(\mathrm{OPT}=\max\{F(z):z\in\mathbb R^\tau,\ 0\le z_i\le\mu_i,\ \sum_i z_i\le\beta\}\).
The computational problem is to return a feasible rational \(x\) satisfying \(F(x)\ge\mathrm{OPT}-\varepsilon\).

Is this additive-\(\varepsilon\) optimization problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

Finite-agent dynamic influence maximization is NP-hard, already with one intervention, one propagation step, known edges, and propagation probabilities equal to \(1\). [Source](https://arxiv.org/pdf/1602.00165)
Continuous discount allocation with probabilistic seed selection is also NP-hard in general, but uses a different objective. [Source](https://www.cs.sfu.ca/~jpei/publications/CIM%20SIGMOD16.pdf) No result settling the exact mass objective above was identified in the search.

Result

The additive-\(\varepsilon\) optimization problem is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

This holds even when all masses are equal dyadic rationals, contacts are symmetric, every type has exactly three positive outgoing contacts, all positive intensities equal \(1/16\), and there are no within-type contacts. The reduction uses \(\varepsilon=1/(64\tau^2)\).

1. Source problem and binary-rational masses

We reduce from Independent Set on simple cubic graphs: given a graph \(G\) in which every vertex has degree three and an integer \(k\), decide whether its independence number satisfies \(\alpha(G)\ge k\). This problem is \(\mathrm{NP}\)-complete; the reduction in the proof of [Mohar’s Theorem 4.1(a)](https://www.sfu.ca/~mohar/Papers/ApexGenus.pdf) establishes hardness even for planar cubic graphs.

We may assume \(1\le k\le n\), where \(n=|V(G)|\), because other values are trivial. Since \(3n=2|E(G)|\), the integer \(n\) is even.

To obtain equal masses that are dyadic rationals, let \(N\) be the least power of two satisfying \(N\ge 2n\). Form a graph \(H\) from two disjoint copies of \(G\) and \(r=(N-2n)/4\) disjoint copies of the complete graph on four vertices. The number \(r\) is a nonnegative integer because \(2n\) and \(N\) are divisible by four.

The graph \(H\) is simple and cubic, has \(N<4n\) vertices, and satisfies

\( \displaystyle \alpha(H)=2\alpha(G)+r. \)

Set \(K=2k+r\). Consequently,

\( \displaystyle \alpha(H)\ge K \quad\Longleftrightarrow\quad \alpha(G)\ge k. \)

Also \(1\le K\le N\). Thus this padding preserves the decision problem and increases its size only linearly.

2. A rounding lemma that controls fractional allocations

For any simple graph \(H\), define

\( \displaystyle Q(u)=\sum_{\{i,j\}\in E(H)}u_i u_j. \)

Lemma. If \(u\in[0,1]^N\) and \(\sum_i u_i=K\), where \(K\) is an integer, there exists \(v\in\{0,1\}^N\) satisfying \(\sum_i v_i=K\) and \(Q(v)\le Q(u)\).

Proof. Suppose two coordinates \(u_p,u_q\) are strictly between zero and one. Change them to \(u_p+t,u_q-t\), keeping all other coordinates fixed. The feasible interval is

\( \displaystyle -\min\{u_p,1-u_q\}\le t\le\min\{1-u_p,u_q\}. \)

At either endpoint, at least one of these coordinates becomes zero or one. As a function of \(t\), the objective has the form

\( \displaystyle Q(u+t e_p-t e_q)=Q(u)+ct-\mathbf{1}_{\{\{p,q\}\in E(H)\}}t^2 \)

for some real coefficient \(c\). Indeed, edges incident to only one of \(p,q\) contribute linear terms, while their mutual edge, if present, contributes \((u_p+t)(u_q-t)\).

This function is concave, so at least one endpoint has objective value no greater than its value at zero. Move to that endpoint. The sum remains \(K\), the objective does not increase, and the number of fractional coordinates decreases.

Repeating this operation leaves at most one fractional coordinate. Exactly one is impossible because the coordinate sum is an integer. The resulting vector proves the lemma. \(\square\)

In particular, if \(\alpha(H)<K\), every integral vector selecting \(K\) vertices contains an edge. Therefore the lemma implies

\( \displaystyle Q(u)\ge 1\qquad\text{for every }u\in[0,1]^N\text{ with }\sum_i u_i=K. \)

Thus fractional allocation cannot eliminate the required graph penalty.

3. Constructing the society

Write \(b=1/N\) and \(a=1/16\). Create one type for each vertex of \(H\), with

\( \displaystyle \tau=N,\qquad \mu_i=b,\qquad \beta=Kb,\qquad \varepsilon=\frac{b^2}{64}. \)

For distinct vertices, set \(a_{ij}=a\) when \(\{i,j\}\in E(H)\), and set all other contact intensities to zero.

All masses are positive and sum to one. All input numbers are dyadic rationals because \(N\) is a power of two. Moreover, \(0<\beta\le1\), and there are exactly \(m=3N\) positive directed intensities.

For a feasible allocation \(x\), write \(u_i=x_i/b\), let \(t=\sum_i x_i\), and define

\( \displaystyle s_j=a\sum_{i:\{i,j\}\in E(H)}x_i. \)

Since every vertex has three neighbors and \(0\le x_i\le b\),

\( \displaystyle 0\le s_j\le 3ab. \)

The objective is exactly

\( \displaystyle F(x)=t+\sum_j(b-x_j)(1-e^{-s_j}). \)

4. A uniform bound for the exact exponential objective

For every \(s\ge0\),

\( \displaystyle 0\le s-(1-e^{-s})\le\frac{s^2}{2}. \)

To verify this, observe that

\( \displaystyle s-(1-e^{-s})=\int_0^s(1-e^{-z})\,dz, \)

and \(0\le1-e^{-z}\le z\) for \(z\ge0\).

Define

\( \displaystyle P(x)=t+\sum_j(b-x_j)s_j. \)

Applying the preceding inequality, using \(b-x_j\ge0\) and \(\sum_j(b-x_j)\le1\), gives

\( \displaystyle 0\le P(x)-F(x)\le\frac12\sum_j(b-x_j)s_j^2\le\frac92a^2b^2=\frac{9b^2}{512}. \)

We now compute \(P\) exactly. Cubic regularity gives \(\sum_j s_j=3at\). Symmetry gives

\( \displaystyle \sum_j x_j s_j=2a\sum_{\{i,j\}\in E(H)}x_i x_j=2ab^2Q(u). \)

Hence

\( \displaystyle P(x)=(1+3ab)t-2ab^2Q(u). \)

For allocations using the full budget, let \(T=(1+3ab)\beta\). Since \(2a=1/8\), the resulting uniform bounds are

\( \displaystyle T-\frac{b^2}{8}Q(u)-\frac{9b^2}{512}\le F(x)\le T-\frac{b^2}{8}Q(u),\qquad \sum_i u_i=K. \)

These inequalities bound the given exponential objective itself.

5. Using an approximate solution to decide Independent Set

Assume an algorithm returns a feasible rational \(x\) satisfying \(F(x)\ge\mathrm{OPT}-\varepsilon\).

First extend its allocation, if necessary, to a rational vector \(\widehat{x}\) using the full budget. This can be done greedily within the coordinate capacities because their sum is one and \(\beta\le1\).

This extension cannot decrease \(F\). In fact, writing \(s_j=\sum_i a_{ij}x_i\), differentiation yields

\( \displaystyle \frac{\partial F}{\partial x_\ell}=e^{-s_\ell}+\sum_j(\mu_j-x_j)a_{\ell j}e^{-s_j}>0. \)

Every summand in the sum is nonnegative, and the first term is positive.

Set \(\widehat{u}=\widehat{x}/b\).

Yes case. Suppose \(\alpha(H)\ge K\). Choose an independent set of exactly \(K\) vertices and allocate mass \(b\) to each selected vertex. Its normalized vector has \(Q=0\). Section 4 therefore gives

\( \displaystyle \mathrm{OPT}\ge T-\frac{9b^2}{512}. \)

Because \(\varepsilon=b^2/64=8b^2/512\),

\( \displaystyle F(\widehat{x})\ge T-\frac{17b^2}{512}. \)

Combining this with the upper bound from Section 4 gives

\( \displaystyle T-\frac{b^2}{8}Q(\widehat{u})\ge T-\frac{17b^2}{512}, \)

so

\( \displaystyle Q(\widehat{u})\le\frac{17}{64}<1. \)

No case. Suppose \(\alpha(H)<K\). The rounding lemma gives

\( \displaystyle Q(\widehat{u})\ge1 \)

for every feasible allocation using the full budget, regardless of its approximation quality.

Thus one call to the presumed optimization algorithm decides the source instance: compute \(Q(\widehat{u})\) exactly and answer yes precisely when \(Q(\widehat{u})<1\). This requires only rational arithmetic; no numerical evaluation of exponentials is needed.

6. Complexity conclusion

The construction has \(N<4n\), \(m=3N\), and polynomial input length. The tolerance \(\varepsilon=1/(64N^2)\) requires only logarithmically many bits.

If the optimization algorithm ran in time polynomial in \(m,\tau,L\), its rational output would have polynomial length. Extending that output to the full budget and computing the rational quadratic \(Q\) would also take polynomial time. We would therefore obtain a polynomial-time algorithm for an \(\mathrm{NP}\)-complete problem.

This proves the claimed \(\mathrm{NP}\)-hardness for the exact mass objective. Because \(1/\varepsilon=64N^2\) in the reduction, even a running-time guarantee polynomial in \(m,\tau,L,1/\varepsilon\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The reduction addresses the exact objective in USER_TASK, controls all feasible fractional allocations, and establishes the claimed hardness with the stated tolerance. No major or minor mathematical issues were found.

1. Source problem and padding

The cited source supports the required hardness assumption. [Mohar’s Theorem 4.1(a)](https://www.sfu.ca/~mohar/Papers/ApexGenus.pdf) states hardness of Maximum Independent Set on 2-connected cubic planar graphs, and its proof supplies a satisfiability reduction with an explicit cardinality threshold. Thus it supports the decision problem used by the prover. No connectivity or planarity assumption is needed in the subsequent construction.

The restriction \(1\le k\le n\) legitimately removes trivial decision instances. For a nonempty simple cubic graph, \(n\ge4\), and the identity \(3n=2|E(G)|\) makes \(n\) even.

The padding calculations are correct:

• Since \(2n\) is divisible by four and \(N\ge2n\) is a power of two, \(r=(N-2n)/4\) is a nonnegative integer.
• The padded graph has \(2n+4r=N\) vertices and remains simple and cubic.
• Minimality of \(N\) gives \(N<4n\).
• Independence numbers add over disjoint components, and each complete graph on four vertices contributes one. Therefore \(\alpha(H)=2\alpha(G)+r\).
• With \(K=2k+r\), the claimed equivalence follows exactly. Also \(1\le K\le N\).

The construction therefore preserves the source decision problem and has polynomial size.

2. Rounding lemma

The lemma is correct for every simple graph under its stated hypotheses.

The interval for \(t\) enforces precisely the two coordinate constraints. When both coordinates are fractional, zero lies strictly between the interval endpoints, and either endpoint makes at least one coordinate integral.

The displayed quadratic expression is correct. Only an edge between the two changed coordinates can contribute a quadratic term, and its coefficient is negative. All other affected terms are linear. Consequently, the function is concave, including the affine case when the mutual edge is absent.

Concavity guarantees that at least one endpoint has value no greater than the value at zero. Each operation preserves the coordinate sum and decreases the number of fractional coordinates without increasing \(Q\). The process terminates after finitely many operations. A single remaining fractional coordinate is incompatible with an integer coordinate sum.

The consequence for no instances has the correct inequality direction. Every integral selection of \(K\) vertices has \(Q(v)\ge1\) when \(\alpha(H)<K\); the lemma provides such a vector with \(Q(v)\le Q(u)\). Hence every feasible fractional vector of total mass \(K\) also satisfies \(Q(u)\ge1\).

No algorithmic implementation of this lemma is required by the reduction.

3. Society construction

Every constructed input meets the task’s requirements.

There are exactly \(N\) types with positive masses \(b=1/N\), summing to one. Thus the support size is indeed \(\tau=N\).

The budget satisfies \(0<\beta=K/N\le1\), and the tolerance is positive. The masses, budget, tolerance, and contact intensities are all dyadic rationals.

Each undirected edge creates two directed positive contacts. Cubic regularity therefore gives exactly \(m=3N\) positive intensities, with three positive outgoing contacts per type. Symmetry and the absence of within-type contacts hold as claimed.

For every feasible allocation, each exposure satisfies \(0\le s_j\le3ab\). The expression for \(F(x)\) is exactly the objective specified in USER_TASK.

4. Exponential estimate and quadratic calculation

The exponential inequality is valid throughout the stated domain \(s\ge0\). Its integral justification correctly establishes both inequalities.

Multiplication by \(b-x_j\) preserves the inequalities because these quantities are nonnegative. Since their sum is at most one, the uniform error calculation gives
\[ 0\le P(x)-F(x)\le\frac92a^2b^2=\frac{9b^2}{512}. \]
The constant is correct for \(a=1/16\).

Both identities used to compute \(P\) are correct:

• Cubic regularity gives \(\sum_j s_j=3at\).
• Symmetry counts each undirected edge twice, giving \(\sum_jx_js_j=2ab^2Q(u)\).

Thus \(P(x)=(1+3ab)t-2ab^2Q(u)\). On the full-budget slice, \(t=\beta\) and \(\sum_i u_i=K\), so both displayed bounds involving \(T\) follow with the claimed constants.

The bounds apply to the exact exponential objective; the proof does not replace the task with optimization of a surrogate.

5. Extension to the full budget

The extension is feasible. The available capacity is \(1-t\), while the additional required allocation is \(\beta-t\le1-t\). Greedy filling preserves rationality and respects all coordinate capacities.

The derivative formula is correct:
\[ \frac{\partial F}{\partial x_\ell} =e^{-s_\ell}+\sum_j(\mu_j-x_j)a_{\ell j}e^{-s_j}. \]
All terms in the sum are nonnegative on the capacity box, and the first term is strictly positive. Therefore coordinatewise increases cannot decrease \(F\).

Consequently, the extended vector retains the approximation guarantee and satisfies the full-budget hypotheses needed for both the quadratic bound and the rounding lemma.

6. Decision separation

In the yes case, an independent set of size at least \(K\) contains one of size exactly \(K\). Its allocation is feasible and has \(Q=0\). The claimed lower bound on \(\mathrm{OPT}\) follows.

The tolerance calculation is correct: \(\varepsilon=8b^2/512\). Hence the approximate, extended output satisfies
\[ F(\widehat{x})\ge T-\frac{17b^2}{512}. \]
Combining this with the established upper bound gives
\[ Q(\widehat{u})\le\frac{17}{64}<1. \]

In the no case, every full-budget allocation satisfies \(Q(\widehat{u})\ge1\), independently of approximation quality.

Thus the exact rational comparison \(Q(\widehat{u})<1\) separates the two cases. There is no numerical evaluation of exponentials and no threshold ambiguity.

7. Computational conclusion

The construction has polynomial input length, including under an explicit dense encoding of the contact matrix. The tolerance requires only logarithmically many bits.

Under the claimed polynomial-time hypothesis, the rational output has polynomial length. Greedy extension, normalization, evaluation of the rational quadratic, and comparison with one all take polynomial time in that length.

The proof therefore establishes hardness in the operational sense requested: a polynomial-time solver for the additive optimization problem would yield a polynomial-time solver for an NP-complete decision problem. It also correctly establishes the stronger exclusion of a running-time bound polynomial in the listed parameters and \(1/\varepsilon\), unless \(\mathrm{P}=\mathrm{NP}\).

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩