Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(k\); no FPT algorithm unless \(\mathrm{FPT}=\mathrm{W}[1]\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatek-IR-Invitation is W[1]-complete if β is not bounded above by any function f(k).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), and a rival relation \(E\) on types, choose invited masses \(x_t\in[0,\mu_t]\) to maximize \(\sum_t x_t\), subject to \(x_t=0\) or \(x_u=0\) for every \(\{t,u\}\in E\). Equivalently, given a rational threshold \(q\), decide whether an individually rational invitation of mass at least \(q\) exists.
A society is given by its support: the list of \(\tau\geq1\) types with positive masses \(\mu_t\), each encoded as a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains an explicitly listed simple undirected rival graph \(E\) on these types, with unrestricted degrees, and a binary rational threshold \(q\in(0,1]\). Types have no friends and accept every positive attendance mass.
An invitation chooses real masses \(x_t\in[0,\mu_t]\). It is individually rational precisely when \(x_t=0\) or \(x_u=0\) for every \(\{t,u\}\in E\); decide whether such an invitation satisfies \(\sum_t x_t\geq q\).
Let \(L\) be the total input bit length and define the integer parameter \(k=\lceil q/\min_t\mu_t\rceil\). State running times in \(\tau,|E|,L,k\); this model has no separate \(m\) parameter.
Is this continuous invitation decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
If it is \(\mathrm{NP}\)-hard, does it admit an \(\mathrm{FPT}\) algorithm parameterized by \(k\), despite the discrete problem being \(\mathrm{W}[1]\)-hard parameterized by invitation cardinality?
For finite agents, deciding whether an individually rational invitation of cardinality \(k\) exists is \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-complete when enemy degrees are unrestricted, including instances with no friends and symmetric enemy relations. [Verified discrete results](https://ojs.aaai.org/index.php/AAAI/article/download/10562/10421).
No result for exactly this continuous formulation was located in the literature search.
The existence problem is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[1]\)-hard parameterized by \(k=\lceil q/\min_t\mu_t\rceil\). Consequently, it admits no FPT algorithm in \(k\) unless \(\mathrm{FPT}=\mathrm{W}[1]\).
These hardness results hold even when all masses are equal and have finite binary expansions. An unconditional exclusion of FPT algorithms is not asserted.
Write \(G=(T,E)\), where \(T=\{1,\ldots,\tau\}\). An independent set is a subset containing no endpoints of the same edge.
For an invitation \(x\), define its positive support by \(S(x)=\{t:x_t>0\}\). The stated individual rationality condition says precisely that \(S(x)\) is independent.
If \(x\) is individually rational, then
\(\displaystyle \sum_t x_t\leq\sum_{t\in S(x)}\mu_t.\)
Conversely, for any independent set \(S\), the invitation defined by \(x_t=\mu_t\) for \(t\in S\) and \(x_t=0\) otherwise is individually rational.
Therefore,
\(\displaystyle \text{a qualifying invitation exists}\quad\Longleftrightarrow\quad \text{an independent set }S\subseteq T\text{ satisfies }\sum_{t\in S}\mu_t\geq q.\)
Thus allowing partial masses does not change the decision problem: every feasible invitation can be replaced by one taking the full mass of each type in its support.
A certificate is the subset \(S\), encoded by \(\tau\) bits. Verify that no edge has both endpoints in \(S\), and compare \(\sum_{t\in S}\mu_t\) with \(q\) using exact rational arithmetic.
Here is an explicit bound on the arithmetic. Write \(\mu_t=a_t/b_t\) and \(q=c/d\), with positive denominators. Set
\(\displaystyle D=d\prod_{t=1}^{\tau}b_t,\qquad W_t=a_t(D/b_t),\qquad Q=c(D/d).\)
The sum of the input denominator bit lengths is at most \(L\), so \(D\) has \(O(L)\) bits. Since all masses and the threshold are at most one, \(W_t\) and \(Q\) also have \(O(L)\) bits. The comparison becomes the integer comparison \(\sum_{t\in S}W_t\geq Q\).
Schoolbook arithmetic constructs these integers in \(O(L^3)\) bit operations. A conservative verification bound is
\(\displaystyle O\!\left(L^3+(\tau+|E|+1)L^2\right).\)
The equivalence proved above guarantees such a certificate for every yes-instance, despite the original variables being real. Hence the problem belongs to \(\mathrm{NP}\).
Use the standard result that Independent Set is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[1]\)-complete parameterized by its requested cardinality \(r\). The supplied invitation paper also explicitly uses parameterized Independent Set in its hardness reduction. [Lee and Williams, Theorem 4](https://cdn.aaai.org/ojs/10562/10562-13-14090-1-2-20201228.pdf).
Take an Independent Set instance \(H=(V,F)\), with \(n=|V|\geq1\) and \(1\leq r\leq n\). These restrictions lose no hardness: inputs outside them are decidable directly.
To ensure that even the masses have finite binary expansions, let \(N\) be the smallest power of two satisfying \(N\geq n\). Thus \(n\leq N<2n\). Form \(H'\) by adding \(N-n\) vertices, making every new vertex adjacent to every other vertex.
Every independent set containing a new vertex has size one. Since \(H\) is nonempty and already has an independent singleton, the maximum independent-set cardinality is unchanged by this padding.
Construct the continuous instance as follows:
All masses are positive and sum to one, and \(q\in(0,1]\). Both masses and threshold have finite binary expansions.
By Section 1, this instance is a yes-instance exactly when \(H'\) has an independent set \(S\) with
\(\displaystyle \frac{|S|}{N}\geq\frac rN,\)
equivalently, \(|S|\geq r\). By the padding argument, this holds exactly when the original instance is a yes-instance.
Moreover, the resulting parameter is exactly
\(\displaystyle k=\left\lceil\frac{r/N}{1/N}\right\rceil=r.\)
The construction has \(\tau<2n\), \(|E|=O(n^2)\), and \(L=O(n^2\log(n+1))\), and can be performed in polynomial time. It is therefore both a polynomial-time reduction and a parameterized reduction preserving the parameter.
Combined with Section 2, this proves \(\mathrm{NP}\)-completeness. It also proves \(\mathrm{W}[1]\)-hardness in \(k\).
In particular, an algorithm with running time \(f(k)(\tau+|E|+L)^C\), for computable \(f\) and constant \(C\) independent of \(k\), would give an FPT algorithm for parameterized Independent Set. This would imply \(\mathrm{FPT}=\mathrm{W}[1]\).
There is nevertheless a useful consequence of the chosen parameter.
Claim. Every yes-instance has a qualifying invitation supported on at most \(\min\{k,\tau\}\) types.
Proof. Let \(\mu_{\min}=\min_t\mu_t\). By definition,
\(\displaystyle k\mu_{\min}\geq q.\)
Section 1 provides an independent set \(S\) whose full mass is at least \(q\). If \(|S|\leq k\), use \(S\). Otherwise, choose any \(k\) vertices from \(S\). Their subset remains independent, and its mass is at least \(k\mu_{\min}\geq q\). This proves the claim.
Consequently, enumerate all subsets of size at most \(s=\min\{k,\tau\}\), checking independence and total mass. Using the integer preprocessing from Section 2 gives the conservative running time
\(\displaystyle O\!\left(L^3+(\tau+|E|+1)L^2\sum_{i=0}^{s}\binom{\tau}{i}\right).\)
To bound the enumeration count, encode each subset by its increasing list of labels, padded with zeros to length \(s\). This is an injection into the length-\(s\) sequences over \(\{0,\ldots,\tau\}\). Hence
\(\displaystyle \sum_{i=0}^{s}\binom{\tau}{i}\leq(\tau+1)^s\leq(\tau+1)^k.\)
The algorithm is therefore XP in \(k\): its running time is polynomial for every fixed \(k\). Its exponent depends on \(k\), so this bound does not establish fixed-parameter tractability.
⟨structured verdict parsed — rendered above⟩
The prover resolves both questions correctly: the continuous problem is \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard for the specified parameter \(k\). Its exclusion of an FPT algorithm is appropriately conditional on \(\mathrm{FPT}\ne\mathrm{W}[1]\). I found no mathematical gaps or false steps.
The positive support \(S(x)\) is independent precisely because each rival edge requires at least one endpoint to receive zero mass.
For a feasible invitation, the bounds \(x_t\leq\mu_t\) imply
\[
\sum_t x_t\leq\sum_{t\in S(x)}\mu_t.
\]
Thus a qualifying invitation gives an independent set with sufficient total mass.
Conversely, assigning full masses to an independent set respects every capacity bound and every rival constraint. This proves both directions of the equivalence.
Replacing a feasible invitation by full masses on its support preserves individual rationality and cannot decrease attendance. The argument correctly uses the task’s assumption that every positive attendance mass is acceptable.
The proposed certificate is sufficient: independence can be checked against the explicitly listed edges, and its mass can be compared exactly with the threshold.
The denominator construction is valid. Each denominator divides \(D\), so every \(W_t\) and \(Q\) is an integer. The total denominator bit length bounds the bit length of their product by \(O(L)\). Since \(\mu_t,q\leq1\), the scaled integers also have \(O(L)\) bits.
There is no hidden growth problem in summing certificate weights: positivity and normalization imply that every subset’s scaled total is at most \(D\).
The claimed preprocessing and verification bounds are conservative polynomial bounds under schoolbook arithmetic. The real invitation variables therefore create no certificate issue.
The source problem is correctly specified as Independent Set on an unrestricted graph, parameterized by the requested cardinality \(r\). The cited paper’s Theorem 4 indeed uses parameterized Independent Set to establish invitation hardness. The present output supplies its own reduction to the continuous formulation, so it does not improperly transfer the discrete theorem directly. [Lee and Williams, Theorem 4](https://cdn.aaai.org/ojs/10562/10562-13-14090-1-2-20201228.pdf).
Every part of the construction checks out:
The independent-set threshold becomes exactly \(|S|\geq r\). Padding therefore preserves the answer, including the boundary case \(r=1\).
The parameter calculation is exact:
\[
k=\left\lceil\frac{r/N}{1/N}\right\rceil=r.
\]
The output-size bounds are polynomial and account for the explicitly listed graph. This establishes both ordinary \(\mathrm{NP}\)-hardness and parameterized \(\mathrm{W}[1]\)-hardness.
The proposed hypothetical running time has the required FPT form, with a constant polynomial exponent independent of \(k\).
Because the reduction preserves the parameter and has polynomial output size, such an algorithm would yield an FPT algorithm for parameterized Independent Set. Its stated consequence, \(\mathrm{FPT}=\mathrm{W}[1]\), is correct. The prover makes no unconditional claim that FPT algorithms are impossible.
The witness bound is valid. If a qualifying independent set has more than \(k\) vertices, any \(k\)-vertex subset remains independent and has mass at least \(k\mu_{\min}\geq q\). Otherwise, the original set already satisfies the support-size bound.
Enumeration through size \(\min\{k,\tau\}\) is therefore complete. The padded increasing-list encoding is injective, including for the empty subset, and proves the stated enumeration bound.
The running time explicitly uses \(\tau,|E|,L,k\), as requested. It establishes XP membership without claiming FPT membership.
No additional clarification or repair is needed.
⟨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.