| paper | d4-conf-ijcai-2022-0484 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
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 population has role types \(t\in T\) with masses \(\mu_t\); \(W\) specifies symmetric regular interaction intensities between roles. Choose the initial mutant mass \(z_t\) in each role, subject to total budget \(\kappa\), to minimize cross-trait interaction mass, equivalently maximize the weak-selection coefficient’s seed-dependent term.
The paper’s hard instances are bounded-degree graphs, whose ordinary dense graphon limits are zero; the proposed nonzero role kernel uses a different weighted or dense interaction regime, and the case does not derive that regime as a limit of those hard instances.
fatal: False
The mirror covers Theorem 2’s regular-graph hardness mechanism through weak-selection sensitivity; it leaves the fixation-probability FPRAS, the favorable-bias submodular approximation, and the unfavorable-bias inapproximability result without continuous mirrors.
My strongest positive case is narrow: a weak-selection fixation-sensitivity mirror of the paper’s regular-graph hardness result. It continuizes the population and preserves the paper’s seed-placement question at the level its hardness proof actually uses: how seeding changes the first-order chance of fixation.
The lead problem is this. Let \(T\) be a finite set of social or network roles, with rational masses \(\mu_t>0\) summing to \(1\). A symmetric step kernel \(W_{tu}\ge 0\) gives the interaction intensity between roles \(t\) and \(u\). Require it to be regular: \(\sum_u \mu_u W_{tu}=\delta\) for every \(t\). Given a seed-mass budget \(\kappa\), choose masses \(z_t\in[0,\mu_t]\) with \(\sum_t z_t=\kappa\). These masses describe which fraction of each role starts with mutant trait \(A\).
Define the cross-trait interaction mass by
\[
\operatorname{Cut}_W(z)=\sum_{t,u\in T}W_{tu}z_t(\mu_u-z_u).
\]
The problem, Graphon Weak-Selection Fixation Sensitivity Maximization, is to find a feasible \(z\) minimizing \(\operatorname{Cut}_W(z)\), equivalently maximizing
\[
\Phi_W(z)=-\frac{\operatorname{Cut}_W(z)}{2\delta}.
\]
A solution is a globally optimal seed-mass vector; its threshold version asks whether some feasible \(z\) has \(\Phi_W(z)\ge b\), for a given rational \(b\).
The anchor is Theorem 2, proved in this paper: given a regular undirected graph, a budget \(k\), and bias \(r>1\), selecting \(k\) vertices to maximize fixation probability is NP-hard, even on regular undirected graphs. The proof examines weak bias \(r=1+\epsilon\). On a \(d\)-regular graph, it expresses the seed-dependent part of the first-order coefficient as \(-a(S)/(2dn)\), where \(a(S)\) is the number of edges crossing between seeded and unseeded vertices. At budget \(k=n/2\), maximizing that coefficient amounts to minimum bisection, which is NP-hard even on 3-regular graphs.
That cut term has a direct continuum form. For finite regular graph approximants whose graphons converge to \(W\), the normalized crossing-edge term \(a(S)/(d n)\) converges to \(\operatorname{Cut}_W(z)/\delta\). Thus \(\Phi_W\) is the continuum limit of the seed-placement-dependent part of the weak-selection coefficient, after removing a term shared by all equal-mass seed choices. This is a computational question about allocating initial mutants across a continuous population, not about fractional outcomes or a continuous time axis.
There is a concrete many-agent regime for it. Imagine \(\tau\) large organizational or community roles, each containing \(M\) agents, with \(M\gg1\). Agents in a role have the same fitness parameters and the same interaction profile by role; within-role contacts are dense, while cross-role contacts follow a regular role network. Then \(n=M\tau\), the type support is \(\tau\), and the decision variable is a mass per role. This matches the authors’ networked population setting while making the population itself continuous.
The mirror remains hard even though it permits fractional seeding within a role. Given a 3-regular graph \(H\) on an even number \(\tau\) of roles, set \(\mu_t=1/\tau\), \(W_{tt}=1\), and \(W_{tu}=1/4\) when \(t,u\) are adjacent in \(H\), with other entries zero. This kernel is regular, with \(\delta=(1+3/4)/\tau\). Write \(z_t=\mu_t s_t\), so \(s_t\in[0,1]\), and set \(\kappa=1/2\). The cut objective, up to the positive factor \(\mu_t^2\), is
\[
\sum_t s_t(1-s_t)+\frac14\sum_{\{t,u\}\in E(H)}
(s_t+s_u-2s_ts_u).
\]
Its Hessian is proportional to \(-2(I+\tfrac14 A_H)\), which is negative definite because every eigenvalue of the 3-regular adjacency matrix \(A_H\) is at least \(-3\). The objective is therefore strictly concave on the feasible set \(\sum_t s_t=\tau/2\), so a minimum occurs at a vertex of that set: \(s_t\in\{0,1\}\). There, minimizing the cut is exactly minimum bisection in \(H\). I expect this mirror to be hard in Class B: the hard combinatorics remain in the role interaction structure, even when each role has high multiplicity.
The scope is deliberately limited to Theorem 2’s regular-graph, weak-selection mechanism. The question it generates is whether more general kernels admit useful exact, approximation, or parameterized algorithms, and whether a graphon model of the voter process yields this same sensitivity objective.
The weak point is also the central qualification: this is a mirror of the paper’s *first-order weak-selection subproblem*, not an established continuum limit of its fixation-maximization problem at fixed \(r>1\). The paper does not show that this limit controls fixation probabilities uniformly as the population grows; at fixed bias, a large-population stochastic process might instead become deterministic and lose the optimization signal. I think the authors could recognize the proposed problem as the continuous form of the cut mechanism in their hardness proof, but I would not claim that it settles the continuous analogue of their full fixed-bias objective.
The sole anchor is Theorem 2: NP-hardness of maximizing the fixation probability for a specified \(r>1\). The proposed mirror instead optimizes a derivative at neutrality, after removing a seed-independent term. On a \(d\)-regular graph,
\[
c(G,S)=\frac{k(n-k)}{2n}-\frac{a(S)}{2dn}.
\]
For \(k=\Theta(n)\), the shared term grows with \(n\), while the seed-dependent cut term stays bounded. The paper’s lemma only says that, for each finite graph, some sufficiently small \(\epsilon\) makes the derivative’s ranking relevant; it gives no uniform choice as multiplicity grows. Thus the cut objective does not establish that maximizing fixation at fixed positive bias has this continuum limit. It is a sensitivity problem suggested by the proof, rather than a mirror of the theorem’s stated optimization problem.
A more direct mirror would define fixation probabilities in a non-atomic population. But a death-birth update to one sampled individual changes zero mass there. In a standard large-population limit, demographic randomness disappears and fixation becomes a deterministic long-run or basin question. Preserving nontrivial fixation probabilities requires retaining finite-population noise or taking a diffusion limit with a specified scaling of selection and time. That could be a worthwhile study, but it makes the limit delicate: the order of those scalings may determine whether seed placement still matters.
There is also a gap in the proposed derivation: the paper’s hardness result uses bounded-degree graphs, whose ordinary dense graphon limits are zero. A nonzero role kernel such as the proposed \(W\) comes from a different, dense or weighted interaction regime. That does not invalidate the kernel problem, but the claimed passage from the paper’s hard instances to that continuum model needs justification.
These points weaken the claim that the cut problem is a continuous mirror of Theorem 2. They do not show that the cut problem is uninteresting: minimizing it over role masses is well-posed, and its minimum-bisection reduction is a legitimate hardness result. So the honest negative case is limited. The proposed problem may be a worthwhile weak-selection sensitivity question; the material here does not establish that it is the paper’s fixation-maximization problem in continuous form, and it does not support the universal claim that no worthwhile mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.