Answer: NP-hard, even for \(m=3\) and \(h=1\) with guaranteed feasibility and strictly positive optimum. An exact algorithm runs in \(2^\tau\operatorname{poly}(m,\tau,L)\) time.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSDSQ is NP-hard and inapproximable within any factor unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given channels \(C\), a weighted diversity graph \((D,W)\), viewer types \(T\) with rational masses \(\mu_t\) summing to \(1\) and preference sets \(P_t\), a block social graph \(H\), a hop bound \(h\), and a population-share threshold \(\rho\), choose a nonempty channel set \(K\) and selected masses \(x_t\in[0,\mu_t]\). Require \(\sum_{t:q\in P_t}x_t\ge\rho\) for every \(q\in K\), require \(P_t\cap K\ne\varnothing\) whenever \(x_t>0\), and require every pair of types with positive selected mass to be at distance at most \(h\) in \(H\). Find a feasible pair \((x,K)\) maximizing \(\sum_{[q,r]\in D(K)}W[q,r]/|K|\), or report that none exists.
Let \(C\) be a set of \(m\ge 1\) channels. Its diversity graph \((C,D)\) is simple and undirected, with binary rational weights \(W[q,r]\in[0,1]\); absent edges contribute zero.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\) summing to \(1\), each with a preference set \(P_t\subseteq C\). Here \(\tau\) is the support size, not the number of possible types.
The block social graph \(H\) is a simple undirected unweighted graph on \(T\). Distances are shortest hop distances in the full graph, allowing unselected intermediate types; disconnected pairs have distance \(\infty\), and \(d_H(t,t)=0\). Input also includes a positive integer \(h\) and a binary rational threshold \(\rho\in(0,1]\), measured against the entire society.
Choose \(\varnothing\ne K\subseteq C\) and real selected masses \(0\le x_t\le\mu_t\), satisfying \(\sum_{t:q\in P_t}x_t\ge\rho\) for every \(q\in K\), \(P_t\cap K\ne\varnothing\) whenever \(x_t>0\), and \(d_H(t,u)\le h\) whenever \(x_t,x_u>0\).
Find a feasible pair maximizing \(\omega(K)=\frac{\sum_{\{q,r\}\in D(K)}W[q,r]}{|K|}\), where \(D(K)\) consists of diversity edges with both endpoints in \(K\), each counted once, or report infeasibility. Any maximizer is acceptable.
Is this exact continuous optimization problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,L,h\), where \(L\) is the total binary input length.
The discrete counterpart, selecting individual viewers with a positive minimum viewer count per channel, is NP-hard and inapproximable within any finite factor unless \(\mathrm{P}=\mathrm{NP}\). [Source](https://cdn.aaai.org/ojs/11310/11310-13-14838-1-2-20201228.pdf)
A later discrete study reiterates these hardness claims. [Source](https://pure.psu.edu/en/publications/on-efficient-processing-of-queries-for-live-multi-streaming-soire/) No result settling exactly the mass formulation above was found in the literature search.
The problem is NP-hard, even when \(m=3\), \(h=1\), and every constructed instance has a feasible solution with strictly positive objective value. Its threshold decision version is NP-complete.
An exact algorithm runs in \(2^\tau\operatorname{poly}(m,\tau,L)\) time, including polynomial preprocessing of distances. Thus it is polynomial-time solvable for fixed support size \(\tau\), but fixing the number of channels does not remove the hardness.
For a feasible solution \((K,x)\), define its positive support by
\[
S=\{t\in T:x_t>0\}.
\]
Replace its masses by \(x'_t=\mu_t\) for \(t\in S\), and \(x'_t=0\) otherwise.
This preserves feasibility:
Consequently, a feasible solution always has a representative whose coordinates belong to \(\{0,\mu_t\}\). Its objective is unchanged because the objective depends only on \(K\).
Call \(S\subseteq T\) compatible if \(d_H(t,u)\le h\) for every \(t,u\in S\). Define
\[
A(S)=\left\{q\in C:\sum_{\substack{t\in S\\q\in P_t}}\mu_t\ge\rho\right\}.
\]
For every compatible \(S\), every nonempty \(K\subseteq A(S)\) is feasible. Indeed, select full mass precisely from
\[
S_K=\{t\in S:P_t\cap K\ne\varnothing\}.
\]
This subset remains compatible. For every \(q\in K\), all types in \(S\) preferring \(q\) belong to \(S_K\), so removing the other types does not reduce coverage of \(q\).
Conversely, the positive support of any feasible solution is compatible and satisfies \(K\subseteq A(S)\). Therefore the optimization problem is exactly
\[
\max_{\substack{S\subseteq T\\S\text{ compatible}\\A(S)\ne\varnothing}}
\ \max_{\varnothing\ne K\subseteq A(S)}
\frac{\sum_{\{q,r\}\in D(K)}W[q,r]}{|K|}.
\]
Reduce from CLIQUE: given a simple graph \(G=(V,E)\), with \(n=|V|\), and an integer \(1\le k\le n\), determine whether \(G\) has a clique of size at least \(k\). This restricted range retains NP-completeness.
Construct the following instance:
\[ \mu_{t_v}=\frac1{n+k},\qquad \mu_z=\frac{k}{n+k},\qquad \rho=\frac{k}{n+k}. \]
All masses are positive and sum to \(1\). The construction has \(\tau=n+1\), uses rationals of polynomial binary length, and takes polynomial time.
Selecting \(K=\{a,b\}\) and mass \(\mu_z=\rho\) is always feasible. Its objective is
\[
\omega(\{a,b\})=\frac{1/2}{2}=\frac14.
\]
We now classify every feasible solution.
If \(z\) has positive selected mass, no original type can have positive selected mass, because \(z\) is disconnected from all of them. Coverage then forces \(K\subseteq\{a,b\}\), so the objective is at most \(1/4\).
If \(z\) has zero selected mass, all selected types are original types. Coverage forces \(K\subseteq\{b,c\}\). Since \(h=1\), distinct selected types must correspond to adjacent vertices of \(G\); hence their support is a clique.
For \(K=\{b,c\}\), a support \(S\subseteq V\) can provide at most \(|S|/(n+k)\) mass to either channel. Thus feasibility implies
\[
\frac{|S|}{n+k}\ge\frac{k}{n+k},
\]
and therefore \(|S|\ge k\). Conversely, any clique of size at least \(k\), selected at full mass, makes \(\{b,c\}\) feasible. Its objective is \(1/2\). Singleton channel sets have objective zero.
It follows that
\[
\operatorname{OPT}=
\begin{cases}
1/2,&\text{if }G\text{ has a clique of size at least }k,\\
1/4,&\text{otherwise}.
\end{cases}
\]
Hence an exact optimizer decides CLIQUE on instances that are always feasible and always have positive optimum. This proves the claimed NP-hardness without relying on infeasibility or a zero optimum.
For a binary rational target \(\lambda\), consider the decision question: does a feasible solution with \(\omega(K)\ge\lambda\) exist?
By the saturation result, a certificate consists only of \(K\) and a support \(S\); its masses are determined as \(\mu_t\) on \(S\) and zero elsewhere. Distances, preference conditions, rational coverage sums, and the objective comparison can all be checked in polynomial time. Thus this decision problem belongs to NP. Section 2 proves NP-hardness with \(\lambda=1/2\), so it is NP-complete.
Feasibility alone is already NP-complete for \(m=1\): use \(H=G\), \(h=1\), let every type prefer the sole channel, and set \(\mu_t=1/n\) and \(\rho=k/n\). Feasibility is equivalent to having a clique of size at least \(k\).
The mass formulation also inherits a direct finite-factor obstruction. To verify this independently, construct two channels \(a,b\) with \(W[a,b]=1\). Give every original type preference \(\{a,b\}\) and mass \(1/(n+2k)\). Add two isolated types, preferring only \(a\) and only \(b\), respectively, each of mass \(k/(n+2k)\). Set \(\rho=k/(n+2k)\) and \(h=1\).
Each singleton channel is feasible using its isolated type. The pair \(\{a,b\}\) is feasible exactly when the original graph has a clique of size at least \(k\): isolated types cannot join any other selected type, and neither alone covers both channels. Therefore the optimum is \(1/2\) in yes-instances and zero in no-instances.
Any polynomial-time multiplicative approximation with a finite factor, returning a feasible solution on these always-feasible instances, must return positive value in every yes-instance. Testing whether its output value is positive would decide CLIQUE. Thus such an approximation is impossible unless \(\mathrm P=\mathrm{NP}\).
Compute shortest-hop distances in the full graph \(H\), as stipulated. Running breadth-first search from every type takes
\[
O\!\left(\tau\bigl(\tau+|E(H)|\bigr)\right)
\]
graph operations, at most \(O(\tau^3)\).
For distinct types, every finite shortest-path distance is at most \(\tau-1\). Consequently, the numerical magnitude of \(h\) causes no additional search cost: comparisons may use \(\min\{h,\tau-1\}\), while disconnected pairs remain incompatible.
Enumerate the \(2^\tau\) subsets \(S\), retaining the compatible ones. For each, calculate \(A(S)\) by exact rational arithmetic. It remains to solve the weighted densest-subgraph problem on \(A(S)\), which has a polynomial-time exact solution. Here is a justification.
For a nonempty eligible channel set \(A\), introduce variables \(z_q\ge0\) and \(y_{qr}\ge0\), with the linear program
\[
\max \sum_{\{q,r\}\in D(A)}W[q,r]y_{qr},
\qquad
\sum_{q\in A}z_q=1,
\qquad
y_{qr}\le z_q,\quad y_{qr}\le z_r.
\]
Every nonempty \(K\subseteq A\) gives a feasible point by setting \(z_q=1/|K|\) on \(K\), zero elsewhere, and \(y_{qr}=1/|K|\) for edges inside \(K\), zero elsewhere. Its LP objective is \(\omega(K)\).
For the reverse direction, take any feasible LP point. Let the distinct positive values of its \(z_q\) be
\[
0=a_0<a_1<\cdots<a_s,
\]
and define \(K_i=\{q:z_q\ge a_i\}\). Then
\[
\sum_{i=1}^s(a_i-a_{i-1})|K_i|=\sum_qz_q=1,
\]
and
\[
\sum_{\{q,r\}\in D(A)}W[q,r]y_{qr}
\le
\sum_{i=1}^s(a_i-a_{i-1})
\sum_{\{q,r\}\in D(K_i)}W[q,r].
\]
The expression on the right is a weighted average of the densities \(\omega(K_i)\), with weights \((a_i-a_{i-1})|K_i|\) summing to \(1\). Hence some \(K_i\) has density at least the LP objective. At an optimal LP point, such a set is an optimal channel set.
This rational LP has \(O(m^2)\) variables and constraints and polynomial encoding length, so polynomial-time rational linear programming applies. The level sets also give an explicit optimal channel set.
The resulting exact algorithm therefore takes
\[
2^\tau\operatorname{poly}(m,\tau,L)
\]
bit operations, including distance preprocessing, and uses polynomial space when subsets are processed sequentially. It reports infeasibility if every compatible support has empty \(A(S)\); otherwise it returns an optimal channel set and full masses on the corresponding \(S_K\).
The reduction shows that a running time polynomial jointly in the input parameters is impossible unless \(\mathrm P=\mathrm{NP}\), already for constant \(m=3\) and \(h=1\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The continuous problem is NP-hard, even with three channels, distance bound \(h=1\), guaranteed feasibility, and strictly positive optimum. The decision classification and the exact exponential-time algorithm are also justified.
No major or minor mathematical issues were found.
The saturation argument is correct. Replacing each positive \(x_t\) by \(\mu_t\):
Thus real-valued selected masses do not require real-valued certificates.
The characterization using compatible supports and \(A(S)\) is also exact. For any nonempty \(K\subseteq A(S)\), removing types whose preferences do not intersect \(K\) preserves compatibility and removes no contribution to any channel in \(K\). Conversely, a feasible solution’s support is compatible, and its full masses provide at least its original coverage, so \(K\subseteq A(S)\).
The empty support causes no exception: because \(\rho>0\), it has \(A(S)=\varnothing\).
The reduction satisfies every input restriction. In particular,
\[ n\frac{1}{n+k}+\frac{k}{n+k}=1, \]
all masses are positive, the threshold belongs to \((0,1]\), and the constructed social and diversity graphs are simple and undirected. The encoding length is polynomial in the CLIQUE input size.
The guaranteed feasible solution is valid: selecting only \(z\) at full mass covers both \(a\) and \(b\), and its objective is \(1/4\).
The classification of feasible solutions is exhaustive:
For the pair \(\{b,c\}\), each selected original type contributes at most \(1/(n+k)\). Therefore feasibility requires at least \(k\) such types. Conversely, a clique of size at least \(k\), selected at full mass, meets the threshold for both channels.
The diversity objectives are correctly calculated: \(1/4\) for \(\{a,b\}\), \(1/2\) for \(\{b,c\}\), and zero for singletons. Consequently, the asserted optimum gap is correct, and an exact optimizer decides CLIQUE. The restricted source range \(1\le k\le n\) retains the usual NP-completeness of CLIQUE.
The NP-membership argument is valid. A certificate specifies \(K\) and a support \(S\), with full selected masses on \(S\). Its length is polynomial, and all feasibility conditions and the rational objective comparison can be checked in polynomial time.
Distances are computed in the full social graph, so verification respects the task’s allowance of unselected intermediate types. Exact rational sums and comparisons have polynomial bit complexity. For the decision problem, the input length also includes the encoding of \(\lambda\).
The hardness reduction uses the fixed threshold \(\lambda=1/2\), establishing NP-completeness.
The separate feasibility reduction with one channel is correct: compatibility requires a clique, and coverage requires its support to contain at least \(k\) vertices.
The additional construction is valid. Its masses sum to one because
\[ \frac{n}{n+2k}+2\frac{k}{n+2k}=1. \]
Each singleton channel is feasible using its corresponding isolated type.
A solution covering both channels cannot select either isolated type: each is incompatible with every other type and alone fails to cover the other channel. Hence the pair is feasible exactly when the original types contain a clique of size at least \(k\).
The optimum is therefore \(1/2\) in yes-instances and zero in no-instances. Under the stated multiplicative guarantee with a finite factor and a feasible returned solution, yes-instances require positive output value. No-instances admit no positive-value feasible solution. The claimed approximation obstruction follows.
The distance preprocessing bound is correct. Breadth-first search from every type uses
\[ O\!\left(\tau(\tau+|E(H)|)\right) \]
graph operations. Every finite distance between distinct types is at most \(\tau-1\). Capping \(h\) at that value is valid provided disconnected pairs remain incompatible, as expressly stated. The case \(\tau=1\) also causes no difficulty.
Enumerating compatible supports and calculating \(A(S)\) correctly reduces the remaining optimization to weighted densest subgraph on an eligible channel set.
The LP justification is complete:
Together, these statements establish equality between the LP optimum and the best channel-set density.
The LP is rational, feasible, and bounded: the nonnegative \(z_q\) sum to one, and every \(y_{qr}\) is bounded by its endpoint variables. Its size and encoding length are polynomial, satisfying the hypotheses for polynomial-time exact rational linear programming. The finitely many level sets allow extraction of an optimal channel set.
Thus the stated bound
\[ 2^\tau\operatorname{poly}(m,\tau,L) \]
in bit operations is justified. The binary encoding of \(h\) is included in \(L\), and its numerical magnitude adds no enumeration factor. Sequential processing requires only polynomial space. The infeasibility test and reconstruction of the selected masses are correct.
No repair or additional clarification is needed to establish the claimed result.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.