Answer: When \(C\) is part of the input, the problem is \(\mathrm{NP\text{-}complete}\). For every fixed \(C\ge 1\), it is polynomial-time solvable. With variable binary-encoded \(C\), it is \(\mathrm{FPT}\) parameterized by \(\operatorname{twc}(H)\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateC-CFw can be solved in time vcO(vc)nO(1). Next, we prove that both of the above algorithms are asymptotically optimal, i.e., we do not expect a drastic im- provement in their running times.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\) summing to one, symmetric pair utilities \(w_{tu}\), and coalition capacity \(C\), choose nonnegative densities \(y_q\) for every integer type composition \(q\) with \(1 \le |q| \le C\), satisfying \(\sum_q q_t y_q = \mu_t\), to maximize \(\sum_q v(q)y_q\), where \(v(q) = \sum_{t<u} w_{tu} q_t q_u + \sum_t w_{tt} \binom{q_t}{2}\); decide whether the optimum is at least a rational threshold \(B\).
Definitions. Let \(T\) be a finite set of types, with rational masses \(\mu_t\ge 0\) satisfying \(\sum_{t\in T}\mu_t=1\), capacity \(C\in\mathbb N\), and symmetric compatibilities \(a_{tu}\in\{0,1\}\). A pattern is \(q\in\mathbb Z_{\ge0}^{T}\) with \(1\le\sum_tq_t\le C\).
A fractional formation assigns each pattern a rate \(z_q\ge0\) such that \(\sum_q q_tz_q=\mu_t\) for every \(t\). Its value is \(\sum_qz_q\left[\sum_ta_{tt}\binom{q_t}{2}+\sum_{t<u}a_{tu}q_tq_u\right]\). Given rational \(K\), decide whether the value is at least \(K\).
Let \(H\) be the loopless compatibility graph on \(T\), where \(tu\in E(H)\) exactly when \(a_{tu}=1\); the structural parameter is \(\operatorname{twc}(H)\).
Target.
Is this fractional coalition-formation problem polynomial-time solvable or NP-hard when \(C\) is part of the input, and what is its complexity for each fixed \(C\)?
If it is NP-hard, is it FPT parameterized by \(\operatorname{twc}(H)\)?
Nearest known results.
The discrete unweighted bounded-coalition problem is NP-complete for every fixed capacity \(C\ge3\).
It is W[1]-hard when parameterized by the twin-cover number of its compatibility graph.
Let \(\operatorname{OPT}(T,\mu,C,a)\) denote the maximum value of a fractional formation.
Theorem.
The last statement contrasts with the stated \(\mathrm{W[1]}\)-hardness of the discrete problem: fractional pattern rates permit an LP with an FPT pricing oracle.
For a pattern \(q\), write
\[ w(q)=\sum_t a_{tt}\binom{q_t}{2}+\sum_{t<u}a_{tu}q_tq_u. \]
The optimization problem is the rational linear program
\[ \max \sum_q w(q)z_q \]
subject to
\[ \sum_q q_tz_q=\mu_t \quad\text{for every }t\in T, \qquad z_q\ge 0. \]
It is always feasible because singleton patterns suffice. Moreover,
\[ \sum_q |q|z_q =\sum_q\sum_tq_tz_q =\sum_t\mu_t =1, \]
so its feasible region is bounded.
There is therefore an optimal basic feasible solution. Since there are \(|T|\) equality constraints, such a solution uses at most \(|T|\) patterns. Every coordinate of every pattern is at most \(C\), and Cramer’s rule gives polynomial encoding length for the corresponding rates \(z_q\): the relevant determinants involve matrices of dimension at most \(|T|\) with entries bounded by \(C\), together with the rational masses.
Thus a certificate consists of at most \(|T|\) patterns and their rational rates. Feasibility and value can be checked in polynomial time. Consequently, the variable-\(C\) problem belongs to \(\mathrm{NP}\).
The number of patterns of size at most \(C\) is
\[ \sum_{r=1}^{C}\binom{|T|+r-1}{r} =\binom{|T|+C}{C}-1. \]
For fixed \(C\), this is \(O(|T|^C)\). We can enumerate all patterns, calculate their values, and solve the resulting explicit rational LP in polynomial time.
In particular:
We reduce from \(\mathrm{CLIQUE}\). Let \(G=(V,E)\) and \(k\) be an instance, where \(2\le k\le |V|\). Set
\[ C=k+1. \]
For every pattern \(q\), each unordered pair of positions in the pattern contributes at most \(1\). Hence
\[ w(q)\le \binom{|q|}{2} \le \frac{C-1}{2}|q|. \]
Every fractional formation therefore satisfies
\[ \sum_qw(q)z_q \le \frac{C-1}{2}\sum_q|q|z_q =\frac{C-1}{2}. \]
Equality holds only if every positive-rate pattern has size exactly \(C\) and every unordered pair of its positions is compatible. For repeated copies of a type \(t\), this requires \(a_{tt}=1\).
Introduce one special type \(s\). For each \(v\in V\), introduce:
The loopless compatibility graph contains:
There are no other inter-type compatibilities.
For diagonal compatibilities, set
\[ a_{x_vx_v}=1 \]
for every \(v\), and set all other diagonal bits to \(0\).
Let \(n=|V|\), let
\[ D=1+2Cn, \qquad \varepsilon=\frac1D, \]
and assign masses
\[ \mu_s=\varepsilon,\qquad \mu_v=\varepsilon,\qquad \mu_{f_v^j}=\varepsilon,\qquad \mu_{x_v}=C\varepsilon. \]
Indeed,
\[ \mu_s+\sum_{v\in V} \left(\mu_v+\sum_{j=1}^{k}\mu_{f_v^j}+\mu_{x_v}\right) = \varepsilon+n\bigl(\varepsilon+(C-1)\varepsilon+C\varepsilon\bigr) =1. \]
Set the threshold to
\[ K=\frac{C-1}{2}. \]
Suppose \(S\subseteq V\) is a clique of size \(k=C-1\).
Use the pattern \(\{s\}\cup S\) at rate \(\varepsilon\). For every \(v\notin S\), use \(\{v\}\cup F_v\) at rate \(\varepsilon\). For every \(v\in S\), use \(\{x_v\}\cup F_v\) at rate \(\varepsilon\).
Finally, use the pattern consisting of \(C\) copies of \(x_v\):
The mass equations hold:
\(\varepsilon+(C-1)\varepsilon=C\varepsilon\);
Every used pattern has size \(C\) and all its position-pairs are compatible. For the repeated \(x_v\)-pattern, this uses \(a_{x_vx_v}=1\). The formation therefore reaches the upper bound \(K=(C-1)/2\).
Conversely, suppose a formation has value at least \(K\). By the universal upper bound, its value equals \(K\). Therefore every positive-rate pattern has size \(C\) and all its position-pairs are compatible.
Because \(\mu_s=\varepsilon>0\), some positive-rate pattern contains \(s\). Since \(a_{ss}=0\), it contains \(s\) exactly once. The only neighbors of \(s\) are original types, so its other \(C-1=k\) positions contain original types.
No original type can be repeated because its diagonal compatibility is \(0\). The \(k\) original types are therefore distinct. Since every pair of positions must be compatible, they induce a \(k\)-clique in \(G\).
Thus the constructed instance reaches \(K\) if and only if \(G\) has a clique of size \(k\). The construction is polynomial, proving NP-hardness. Together with membership in \(\mathrm{NP}\), the variable-\(C\) problem is \(\mathrm{NP\text{-}complete}\).
Types of zero mass can be deleted: their mass equations imply that no positive-rate pattern can contain them. Hence assume \(\mu_t>0\) for every remaining type.
The dual LP is
\[ \min \sum_t\mu_ty_t \]
subject to
\[ \sum_tq_ty_t\ge w(q) \quad\text{for every pattern }q. \]
Separation amounts to computing
\[ \max_{\substack{q\in\mathbb Z_{\ge0}^{T}\\1\le |q|\le C}} \left(w(q)-\sum_tq_ty_t\right). \]
A violated constraint exists exactly when this maximum is positive.
Singleton constraints imply \(y_t\ge0\). The vector with every coordinate equal to \((C-1)/2\) is dual feasible by the universal upper bound. Consequently, an optimal dual solution can be sought in the rational box
\[ 0\le y_t\le \frac{C-1}{2\mu_t}. \]
It therefore suffices to give an FPT exact separation oracle.
For every price vector \(y\), there is an optimal pricing pattern whose positive support is a clique of the loopless graph \(H\).
Let \(i\) and \(j\) be nonadjacent types occurring positively in a pattern. Fix all other coordinates and fix \(s=q_i+q_j\). Put \(q_i=x\) and \(q_j=s-x\).
Because \(a_{ij}=0\), the part of the reduced value depending on \(x\) has the form
\[ a_{ii}\binom{x}{2} +a_{jj}\binom{s-x}{2} +b_ix+b_j(s-x) \]
for constants \(b_i,b_j\). Its quadratic coefficient is
\[ \frac{a_{ii}+a_{jj}}2\ge0. \]
It is therefore convex in \(x\), so its maximum on the integer interval \(0\le x\le s\) occurs at \(x=0\) or \(x=s\). Thus all copies can be moved to one of \(i,j\) without decreasing the reduced value.
Repeatedly applying this operation eliminates every nonadjacent pair from the support. The resulting support is a clique. \(\square\)
Fix a clique \(A\subseteq T\). Among patterns supported in \(A\), the best reduced value with size between \(1\) and \(C\) is attained at size \(1\) or size \(C\).
Let \(d_i=a_{ii}\). If a pattern supported in \(A\) has total size \(r\), then all inter-type pairs are compatible, so
\[ w(q) =\binom r2-\sum_{i\in A:d_i=0}\binom{q_i}{2}. \]
For each \(i\in A\), define its successive marginal terms by
\[ \gamma_{i,j}=-y_i-(1-d_i)(j-1), \qquad j=1,2,\ldots. \]
For a fixed \(r\), maximizing the reduced value apart from \(\binom r2\) is equivalent to choosing the \(r\) largest terms from all the sequences \((\gamma_{i,j})_{j\ge1}\). Let these selected values, in nonincreasing order, be
\[ \delta_1\ge\delta_2\ge\cdots. \]
Prefix feasibility is automatic: if \(\gamma_{i,j}\) is selected, then every preceding term of its nonincreasing sequence can also be selected.
Thus the optimum for total size \(r\) is
\[ \Phi_A(r)=\binom r2+\sum_{\ell=1}^{r}\delta_\ell. \]
Every sequence is either constant or decreases by exactly \(1\). Therefore
\[ \delta_{r+1}\ge\delta_r-1. \]
Indeed, a successor of a term realizing \(\delta_r\) is still available and has value at least \(\delta_r-1\). Hence
\[ \bigl(\Phi_A(r+1)-\Phi_A(r)\bigr) - \bigl(\Phi_A(r)-\Phi_A(r-1)\bigr) = 1+\delta_{r+1}-\delta_r \ge0. \]
Thus \(\Phi_A\) is discretely convex. A convex sequence on \(\{1,\ldots,C\}\) attains its maximum at an endpoint, proving the lemma. \(\square\)
For size \(C\), only the first \(C\) terms of each marginal sequence matter. The \(C\) largest terms among these implicit arithmetic progressions can be found in time polynomial in
\[ |A|,\quad \log C,\quad\text{and the encoding length of }y. \]
For a rational threshold \(\theta\), the number of terms larger than \(\theta\) in each sequence is computable directly by integer division. This gives a rank oracle. The candidate values are of the form \(-y_i-j\), with \(0\le j<C\), or the constant value \(-y_i\). Their encoding lengths are polynomial, and distinct candidates have inverse-exponentially bounded separation in the input length. Exact binary search using the rank oracle therefore identifies the \(C\)-th largest value in polynomially many steps. Arithmetic-series formulas then give both the optimum value and an optimizing multiplicity vector.
Thus binary encoding of \(C\) causes no pseudo-polynomial dependence on \(C\).
Let \(X\) be a twin cover of \(H\), with \(|X|=k\). Under the standard twin-cover decomposition, every component \(B\) of \(H-X\) is a clique, and all vertices of \(B\) have the same neighborhood \(N_X(B)\) in \(X\). This is the standard characterization from [Ganian’s twin-cover paper](https://doi.org/10.46298/dmtcs.2136).
Every clique of \(H\):
Enumerate every subset \(S\subseteq X\). If \(S\) is a clique, examine:
Every clique support is contained in one of these pools. Conversely, every such pool is a clique. Allowing zero multiplicities means it is unnecessary to enumerate subsets of \(B\).
There are at most
\[ 2^k\bigl(1+\text{number of components of }H-X\bigr) \]
candidate pools. For each one, Lemma 2 and the exact marginal-selection algorithm compute the best reduced value in polynomial time. Singleton patterns are checked separately.
Hence pricing runs in time
\[ 2^{O(k)}\,|I|^{O(1)}, \]
where \(|I|\) is the binary input length, including \(\log C\).
A twin cover of size \(k\) can itself be found in FPT time. One direct method forms the graph of edges whose endpoints are not true twins. Every twin cover must cover each such edge, so the usual bounded-search-tree algorithm for vertex cover runs in \(2^{O(k)}|T|^{O(1)}\) time.
The preceding algorithm is an exact strong separation oracle for the bounded dual polyhedron. The standard rational ellipsoid optimization–separation theorem therefore computes its optimum in
\[ 2^{O(\operatorname{twc}(H))}\,|I|^{O(1)} \]
time. Strong LP duality then gives the primal fractional optimum, which can be compared exactly with \(K\).
Thus the problem is FPT parameterized by \(\operatorname{twc}(H)\), even when \(C\) is binary-encoded and unbounded.
The fractional and discrete problems have different fixed-capacity behavior. The discrete problem retains an integral partition constraint and is NP-complete for fixed \(C\ge3\). The fractional problem is an explicit polynomial-size LP for every fixed \(C\). When \(C\) varies, the exponentially large pattern family restores NP-hardness, but twin cover makes its pricing problem fixed-parameter tractable.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes all three requested classifications:
No false central step or counterexample was found. The FPT argument has minor presentation gaps concerning ties in the marginal-selection lemma and the exact ellipsoid implementation, but these require clarification rather than new mathematics.
This part is correct.
Thus a polynomial-size certificate exists and can be checked exactly. The NP-membership claim is rigorous.
The stars-and-bars count
\(\sum_{r=1}^{C}\binom{|T|+r-1}{r}=\binom{|T|+C}{C}-1\)
is correct. For fixed \(C\), this is polynomial in \(|T|\), so explicit pattern enumeration followed by rational LP optimization is polynomial time.
The special cases \(C=1\) and \(C=2\) are also correctly described.
The reduction from CLIQUE is correct.
For every pattern, \(w(q)\le\binom{|q|}{2}\le (C-1)|q|/2\). Summing against \(z_q\) and using \(\sum_q|q|z_q=1\) gives the claimed global bound \((C-1)/2\).
Because both inequalities have nonnegative slack, equality in the total value forces every positive-rate pattern to have size \(C\) and every positional pair in it to be compatible.
The mass calculation is correct:
\(\varepsilon+n(\varepsilon+(C-1)\varepsilon+C\varepsilon)=\varepsilon(1+2Cn)=1\).
Since \(C=k+1\le |V|+1\), the \(O(|V|k)\) introduced types and the compatibility description have polynomial size.
All listed patterns have size \(C\). Their compatibility claims and mass contributions check out:
Thus the upper bound is attained.
If the upper bound is attained, a positive-rate pattern containing \(s\) must exist. Because \(a_{ss}=0\), it contains one copy of \(s\). Its remaining \(C-1=k\) positions must be original types, since those are the only neighbors of \(s\). Their diagonal bits are zero, so they are distinct. Pairwise compatibility then makes them a \(k\)-clique in the original graph.
The reduction therefore proves NP-hardness.
The dual is derived correctly. Deleting zero-mass types is valid because their primal mass equations prohibit their occurrence in every positive-rate pattern.
Singleton constraints imply \(y_t\ge0\). The uniform vector \(y_t=(C-1)/2\) is dual feasible. Consequently, some optimal solution has objective at most \((C-1)/2\), and nonnegativity then yields \(y_t\le(C-1)/(2\mu_t)\) for every remaining type.
The pricing objective and the criterion that a violation exists exactly when its maximum is positive are correct.
The pairwise consolidation argument is valid. For two nonadjacent supported types, holding their total multiplicity fixed produces a convex univariate quadratic. An endpoint therefore eliminates one of the two types without decreasing the reduced value. Each application strictly reduces support size, so the process terminates with clique support.
The identity
\(w(q)=\binom r2-\sum_{i:a_{ii}=0}\binom{q_i}{2}\)
is correct for clique-supported patterns. The marginal sequences correctly represent the remaining objective, and the inequality \(\delta_{r+1}\ge\delta_r-1\) implies discrete convexity of \(\Phi_A\). Hence a maximum occurs at \(r=1\) or \(r=C\).
There are two minor rigor problems in the written proof:
These are expositional gaps, not failures of the lemma.
The proposed rank-oracle method is plausible and polynomial in \(\log C\), but the exactness discussion is compressed. To make it fully verifiable, the prover should explicitly state:
These are routine bit-complexity details and do not require a new algorithmic idea.
The structural claims agree with the original definition and properties of twin cover: after deleting a twin cover, the remaining components are cliques of true twins, and deleting all non-twin edges reduces computation of twin cover to vertex cover. This is confirmed in [Ganian’s paper](https://dmtcs.episciences.org/2136/pdf).
The clique enumeration is correct:
The claimed \(2^{O(k)}|I|^{O(1)}\) pricing time follows.
The conclusion is substantively correct, but the implementation is slightly underspecified. The bounded polyhedron is the dual intersected with the displayed coordinate box, so a complete strong-separation oracle must also separate violations of those box constraints. The prover should additionally record the polynomial encoding bounds for returned pattern inequalities and invoke the exact rational optimization–separation theorem with those hypotheses.
These are standard and easy additions, but they are necessary for a fully formal exact-FPT claim.
The NP-completeness reduction and fixed-\(C\) algorithm are fully rigorous. The FPT direction is sound in substance; its remaining issues are limited to exact tie handling and standard bit-complexity details. The output therefore resolves the target with minor gaps.
⟨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.