d4-conf-wine-2017-0007 (d4-conf-wine-2017-0007)

Given a finite type set \(\mathcal{T}\), rational masses \(\mu_t\) summing to \(1\), rational contact weights \(W_{tu}\), nondecreasing piecewise-linear response functions \(\phi_t\), a seed share \(\alpha\), and an accuracy \(\varepsilon\), compute seed masses \(s_t\in[0,\mu_t]\) with \(\sum_t s_t=\alpha\) whose final infected mass is within additive \(\varepsilon\) of optimal. Define \(q_t^{(0)}=s_t\) and \(q_t^{(r+1)}=s_t+(\mu_t-s_t)\phi_t\!\left(\frac{\sum_u W_{tu}q_u^{(r)}}{\sum_u W_{tu}\mu_u}\right)\), using exposure \(0\) for a zero denominator and requiring \(\phi_t(0)=0\); maximize \(\sum_t q_t^{\infty}\). What is the exact or approximation complexity in \(|\mathcal{T}|\), the response descriptions, input bit length, and \(\varepsilon\)?

A society is given by its support: a nonempty list \(\mathcal T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Input also consists of nonnegative rational directed contact weights \(W_{tu}\), continuous nondecreasing piecewise-linear functions \(\phi_t:[0,1]\to[0,1]\) with \(\phi_t(0)=0\), and rational parameters \(0<\alpha\leq1\) and \(0<\varepsilon<1\). Each response is specified by rational breakpoint coordinates, including both endpoints, with linear interpolation.
Let \(m=|\{(t,u):W_{tu}>0\}|\), let \(B\) be the total number of response breakpoints, and let \(L\) be the total binary input length; within-type contacts are allowed.
For feasible seed masses \(0\leq s_t\leq\mu_t\) with \(\sum_t s_t=\alpha\), define \(q_t^{(0)}=s_t\), \(d_t=\sum_u W_{tu}\mu_u\), and \(x_t^{(r)}=(\sum_u W_{tu}q_u^{(r)})/d_t\) when \(d_t>0\), otherwise \(x_t^{(r)}=0\).
Update synchronously by \(q_t^{(r+1)}=s_t+(\mu_t-s_t)\phi_t(x_t^{(r)})\), and define \(q_t^\infty(s)=\lim_{r\to\infty}q_t^{(r)}\).
Set \(F(s)=\sum_t q_t^\infty(s)\) and \(\mathrm{OPT}=\sup\{F(s):0\leq s_t\leq\mu_t,\ \sum_t s_t=\alpha\}\). The computational problem is to return feasible binary rational seed masses satisfying \(F(s)\geq\mathrm{OPT}-\varepsilon\).

Is this additive approximation problem solvable in time polynomial in \(m,\tau,B,L,1/\varepsilon\), or is it NP-hard even when \(1/\varepsilon\) is polynomially bounded in \(L\)?

Known discrete result: given a hierarchical decomposition, the DPIM heuristic uses \(O(nk^2)\) expected-influence oracle calls for \(n\) vertices and \(k\) seeds; this is an oracle complexity bound without a general optimality guarantee. [Source](https://arxiv.org/pdf/1609.06520).
A different continuous discount-allocation model with independently randomized seeds has NP-hard exact optimization; its objective is expected influence on a finite graph, rather than the mass recurrence above. [Source](https://www.cs.sfu.ca/~jpei/publications/CIM%20SIGMOD16.pdf). No result settling this precise mass problem was located.

Result. The additive approximation problem is \(\mathrm{NP}\)-hard, even when \(1/\varepsilon=O(L)\). This holds with all response functions identical, each having four fixed breakpoints, and all nonzero contact weights equal to \(1\). Consequently, the proposed polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).

1. Convergence and an exact activation threshold

For a fixed feasible allocation \(s\), let \(H_s\) denote the update map. Nonnegative contact weights and nondecreasing responses make \(H_s\) coordinatewise nondecreasing. Moreover, \(H_s\) maps the box \(\prod_t[s_t,\mu_t]\) into itself. Since \(q^{(0)}=s\) and \(q^{(1)}\geq s\), induction shows that \(q^{(r)}\) increases coordinatewise and remains bounded above by \(\mu\). Thus its limit exists. Continuity of the responses gives
\[ q^\infty=H_s(q^\infty). \]

Use the following fixed response function:
\[ g(x)= \begin{cases} 0,&0\leq x\leq 1/4,\\ 4x-1,&1/4\leq x\leq 1/2,\\ 1,&1/2\leq x\leq 1. \end{cases} \]
Its breakpoint coordinates are \((0,0),(1/4,0),(1/2,1),(1,1)\).

Consider a type of mass \(\nu\), with response \(g\), whose only contact is with itself. Put \(z=s/\nu\) and \(y_r=q^{(r)}/\nu\). Its recurrence is
\[ y_0=z,\qquad y_{r+1}=z+(1-z)g(y_r). \]
We claim that
\[ q^\infty= \begin{cases} s,&s\leq \nu/4,\\ \nu,&s>\nu/4. \end{cases} \]

If \(z\leq 1/4\), the initial value is fixed. If \(z\geq 1/2\), the next value is \(1\). Finally, suppose \(1/4<z<1/2\). Monotonicity gives \(y_r\geq z\). Whenever \(y_r<1/2\),
\[ y_{r+1}-y_r =(1-z)(4z-1)+(3-4z)(y_r-z) \geq (1-z)(4z-1)>0. \]
The positive lower bound is independent of \(r\), so the sequence reaches \(1/2\) in finitely many steps. Its next value is \(1\), proving the claim.

In particular, equality at the seed threshold does not activate the type.

2. Reduction from Vertex Cover

We use the standard \(\mathrm{NP}\)-complete Vertex Cover problem: given a finite simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether some set of at most \(k\) vertices meets every edge. This is Karp’s “Node Cover” problem. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Write \(n=|V|\) and \(M=|E|\). We may restrict attention to
\[ M\geq1,\qquad 1\leq k\leq n-1, \]
because the excluded cases are decidable directly.

Let \(N\) and \(H\) be the smallest powers of two satisfying \(N\geq n\) and \(H\geq M\). Define
\[ \eta=\frac1{2H},\qquad \nu=\frac{\eta}{4N},\qquad \delta=n\nu. \]

Construct one type for each vertex, one for each edge, and one additional type \(\ast\), with masses
\[ \mu_v=\nu,\qquad \mu_e=\eta,\qquad \mu_\ast=1-\delta-M\eta. \]
These are positive dyadic rationals summing to \(1\). Indeed,
\[ M\eta\leq\frac12,\qquad \delta\leq\frac{\eta}{4},\qquad \eta\leq\frac12, \]
so \(\mu_\ast\geq3/8\).

Every type has response \(g\). Set the contact weights as follows:

• Each vertex type has \(W_{vv}=1\).
• For each edge \(e=\{u,v\}\), set \(W_{eu}=W_{ev}=1\).
• All other weights are zero.

Finally, set
\[ \alpha=\frac{(2k+1)\nu}{8}, \qquad \varepsilon=\frac{\eta}{4}. \]
These satisfy the required parameter bounds. Since \(k<n\),
\[ \alpha<\frac{\delta}{4}, \qquad \delta+\alpha<\frac{5\eta}{16}<\frac{\eta}{2}. \]

3. Exact interpretation of arbitrary fractional allocations

For any feasible allocation \(s\), define
\[ A(s)=\{v\in V:s_v>\nu/4\}. \]
By the activation lemma, precisely these vertex types activate fully. The budget bounds their number:
\[ |A(s)|\,\frac{\nu}{4} \leq\sum_{v\in A(s)}s_v \leq\alpha =\left(k+\frac12\right)\frac{\nu}{4}. \]
Since \(|A(s)|\) is an integer, \(|A(s)|\leq k\).

For an edge type \(e=\{u,v\}\), its normalized contact input is
\[ x_e^{(r)}=\frac{q_u^{(r)}+q_v^{(r)}}{2\nu}. \]

If neither endpoint lies in \(A(s)\), both endpoint trajectories remain at their seed masses, each at most \(\nu/4\). Hence \(x_e^{(r)}\leq1/4\) at every round, and \(q_e^\infty=s_e\).

If at least one endpoint lies in \(A(s)\), that endpoint eventually reaches mass \(\nu\). From then onward \(x_e^{(r)}\geq1/2\), and the edge type reaches its full mass \(\eta\).

The additional type has zero contact input, so \(q_\ast^\infty=s_\ast\). Therefore
\[ q_e^\infty= \begin{cases} \eta,&e\text{ meets }A(s),\\ s_e,&e\text{ does not meet }A(s). \end{cases} \]
This characterization holds for every feasible fractional allocation, including allocations that directly seed edge types.

4. A uniform loss whenever an edge is uncovered

Suppose \(A(s)\) fails to cover some edge. At most \(M-1\) edge types activate fully. All vertex types together contribute at most \(\delta\), and the combined seed mass assigned to uncovered edges and the additional type is at most \(\alpha\). Consequently,
\[ F(s)\leq(M-1)\eta+\delta+\alpha <M\eta-\frac{\eta}{2}. \]

Thus an uncovered edge causes a loss exceeding \(\eta/2\), even after allowing arbitrary direct seeds and counting all vertex mass.

5. A feasible allocation when a cover exists

Suppose \(G\) has a vertex cover of size at most \(k\). Extend it to a set \(S\subseteq V\) of exactly \(k\) vertices. Allocate
\[ s_v=\frac{\nu}{4}+\frac{\nu}{8N}\quad(v\in S), \qquad s_v=0\quad(v\notin S), \]
and set every edge seed to zero. Allocate the remaining mass to the additional type:
\[ s_\ast=\frac{\nu(N-k)}{8N}. \]

All these seeds are dyadic rationals. Each vertex seed is below \(\nu\), and \(0<s_\ast\leq\nu/8<\mu_\ast\). Their sum is exactly
\[ k\left(\frac{\nu}{4}+\frac{\nu}{8N}\right) +\frac{\nu(N-k)}{8N} =\frac{k\nu}{4}+\frac{\nu}{8} =\alpha. \]
Thus the allocation is feasible.

Its activated vertex set is \(S\), which covers every edge. Every edge type therefore activates fully, giving
\[ F(s)\geq M\eta,\qquad \mathrm{OPT}\geq M\eta. \]

6. Extracting a decision from the approximate output

Suppose an algorithm returns feasible binary rational seeds satisfying the required additive guarantee. Run it on the constructed instance and inspect \(A(s)\), using exact rational comparisons.

If the graph has a vertex cover of size at most \(k\), the guarantee implies
\[ F(s)\geq\mathrm{OPT}-\varepsilon \geq M\eta-\frac{\eta}{4}. \]
Section 4 shows that this is impossible unless \(A(s)\) covers every edge.

If the graph has no such cover, \(A(s)\) cannot cover every edge because \(|A(s)|\leq k\).

Hence checking whether the returned set \(A(s)\) covers the graph decides Vertex Cover. This requires no simulation of the recurrence and no numerical evaluation of its limit.

The constructed instance has
\[ \tau=n+M+1,\qquad m=n+2M,\qquad B=4\tau. \]
All numerical data have binary length \(O(\log(n+M))\), so the construction has polynomial input length. Moreover,
\[ \frac1\varepsilon=8H<16M\leq16L. \]
Therefore an algorithm polynomial in \(m,\tau,B,L,1/\varepsilon\) would decide Vertex Cover in polynomial time. This proves the claimed hardness with an inverse-linear approximation tolerance.

⟨structured verdict parsed — rendered above⟩

The proof resolves the assigned problem. Its threshold calculation, treatment of arbitrary fractional allocations, separation gap, and encoding bounds are correct. I found no major or minor mathematical issues.

• Convergence and fixed-point identity

For every feasible allocation, the contact inputs lie in \([0,1]\): whenever \(d_t>0\), the bounds \(0\leq q_u^{(r)}\leq\mu_u\) imply
\[ 0\leq\sum_u W_{tu}q_u^{(r)}\leq d_t. \]
The prescribed zero-input convention handles \(d_t=0\).

The update map is coordinatewise nondecreasing and maps the stated box into itself. Starting from \(s\), the iterates therefore increase coordinatewise and are bounded. Continuity justifies passing to the limit in the update equation. These assertions hold for all responses allowed by the task.

• Exact activation threshold

The function \(g\) satisfies every response requirement: it is continuous, nondecreasing, maps \([0,1]\) into \([0,1]\), and has the four stated rational breakpoints.

For a self-contacting vertex type, the normalization and scalar recurrence are correct. The cases \(z\leq1/4\) and \(z\geq1/2\) are handled correctly, including equality at both boundaries.

In the remaining interval, the displayed increment identity is algebraically correct:
\[ y_{r+1}-y_r =(1-z)(4z-1)+(3-4z)(y_r-z). \]
Here \(3-4z>0\), \(y_r\geq z\), and \((1-z)(4z-1)>0\). Thus, while the trajectory remains below \(1/2\), each increment has a fixed positive lower bound. The claimed finite crossing and subsequent full activation follow. The strict seed threshold is established exactly as stated.

• Source problem and restricted instances

The cited source establishes the NP-completeness of Node Cover, the Vertex Cover decision problem used here. Its formulation is compatible with the prover’s source problem. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Restricting to \(M\geq1\) and \(1\leq k\leq n-1\) is legitimate: the omitted cases have immediate decisions. In particular, the retained instances have \(n\geq2\), so all subsequent parameter definitions are valid.

• Validity of the constructed instance

The masses are positive dyadic rationals and sum to one. The stated estimates
\[ M\eta\leq\frac12,\qquad \delta\leq\frac{\eta}{4},\qquad \eta\leq\frac12 \]
correctly imply \(\mu_\ast\geq3/8\).

The contact structure is permitted by the task, including vertex self-contact. Every nonzero weight is one.

The parameter bounds also check out. Since \(k\leq n-1\),
\[ \alpha=\frac{(2k+1)\nu}{8}<\frac{n\nu}{4}=\frac{\delta}{4}. \]
Consequently,
\[ \delta+\alpha<\frac{5\eta}{16}<\frac{\eta}{2}. \]
Both \(\alpha\) and \(\varepsilon\) satisfy their required domains.

• Interpretation of every feasible fractional allocation

The activation lemma applies independently to every vertex because each vertex’s sole contact is with itself. Hence the stated characterization of \(A(s)\) is exact.

The budget inequality implies \(|A(s)|\leq k\). The weak inequality written in the proof is sufficient; strict activation thresholds introduce no problem.

For an edge, the denominator is exactly \(2\nu\), since the graph is simple and its two endpoints are distinct. Thus its normalized contact input is correctly stated.

If neither endpoint activates, both endpoint masses stay at their seeds, giving input at most \(1/4\) and edge mass exactly \(s_e\). If an endpoint activates, it reaches its full mass in finite time, after which the edge input is at least \(1/2\) and the edge reaches \(\eta\).

Direct edge seeds do not invalidate either conclusion: edge types have no self-contact and do not influence vertex trajectories. The additional type likewise remains at its seed mass because its contact input is zero.

• Uniform upper bound for an uncovered edge

The bound correctly separates covered-edge mass, all vertex mass, and seeds on uncovered edges and the additional type:
\[ F(s)\leq(M-1)\eta+\delta+\alpha <M\eta-\frac{\eta}{2}. \]
There is no omitted contribution or double counting. Arbitrary fractional allocations, including direct edge seeding, are covered by this estimate.

• Feasible allocation from a vertex cover

A cover of size at most \(k\) can be extended to exactly \(k\) vertices because \(k<n\). All specified seeds are rational and satisfy their individual capacity constraints.

In particular, \(N-k>0\), so the additional seed is positive, and its stated upper bound is valid. The budget calculation is exact:
\[ \sum_t s_t=\frac{k\nu}{4}+\frac{\nu}{8}=\alpha. \]
Every selected vertex lies strictly above its activation threshold. Therefore every edge activates, establishing the claimed lower bound \(\mathrm{OPT}\geq M\eta\).

• Extraction from approximate output

On a yes-instance, the required guarantee yields
\[ F(s)\geq M\eta-\frac{\eta}{4}, \]
which contradicts the uncovered-edge upper bound unless \(A(s)\) covers every edge.

On a no-instance, no extracted set can cover every edge because its size is at most \(k\). The decision procedure therefore works in both directions.

Exact comparisons of binary rational seeds and an ordinary coverage check suffice. No evaluation of the infinite-time objective is required. The use of a supremum causes no gap: the yes-instance bound comes from an explicitly feasible allocation.

• Polynomial construction and approximation scale

The counts \(\tau=n+M+1\), \(m=n+2M\), and \(B=4\tau\) are correct. Each numerical datum has the claimed logarithmic encoding length, and even an explicit dense contact matrix would have polynomial size.

Since \(H<2M\),
\[ \frac1\varepsilon=8H<16M\leq16L. \]
The final inequality is justified by the explicit input listing, which includes a positive mass for every edge type. Thus all parameters of the hypothetical running-time bound are polynomially bounded in the source-instance size.

The reduction establishes the claimed hardness of returning approximate seeds. It does not require, or claim, an NP-membership result.

Repair feedback: None required. The argument is rigorous as written and establishes the stated restricted hardness result.

⟨structured verdict parsed — rendered above⟩