d4-journals-jair-2017-0057 (d4-journals-jair-2017-0057)

Given \(m\) candidates, fixed \(p\), approval types \(A_1,\ldots,A_\tau\subseteq C\) with \(|A_i|\le p\), positive binary-rational masses \(\mu_i\) summing to \(1\), a committee limit \(K\), and a rational threshold \(\theta\), decide whether some \(W\subseteq C\), \(|W|\le K\), satisfies \(\sum_{i:A_i\cap W\ne\varnothing}\mu_i\ge\theta\). Classify this problem parameterized by \(K\), with input size measured in \(m,\tau\), and the mass bit length \(L\).

Fix an integer \(p\ge 2\). Let \(C\) be a set of \(m\ge 1\) candidates.
A society is given by its support: distinct approval types \(A_1,\ldots,A_\tau\subseteq C\), each with \(|A_i|\le p\), and positive binary-rational masses \(\mu_i\) satisfying \(\sum_i\mu_i=1\). Empty approval types are allowed. The quantity \(\tau\) is the support size, not the number of possible approval sets.
The input also contains a nonnegative integer committee limit \(K\) and a binary-rational threshold \(\theta\). Let \(L\) be the total bit length of the numerical input.
A committee is a subset \(W\subseteq C\) with \(|W|\le K\); its represented mass is \(\sum_{i:A_i\cap W\ne\varnothing}\mu_i\). Decide whether some committee has represented mass at least \(\theta\).
State running times in \(m,\tau,L,K\), treating \(p\) as fixed.

Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
If it is \(\mathrm{NP}\)-hard, can it nevertheless be solved in FPT time parameterized by \(K\)?

For every fixed \(p\ge2\), the discrete version counting explicitly listed voters is \(\mathrm{W}[1]\)-complete parameterized by \(K\) and \(\mathrm{NP}\)-complete. [Skowron–Faliszewski](https://www.jair.org/index.php/jair/article/view/11095), [NP-completeness source](https://arxiv.org/html/1309.4405).
Positive-weight bounded-frequency maximum coverage admits an FPT approximation scheme under even matroid constraints; this does not settle the exact decision question above. [Sellier](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.94).

Classification

For every fixed \(p\ge 2\), the problem is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[1]\)-hard parameterized by \(K\). Consequently, an exact algorithm with running time \(f(K)\operatorname{poly}(m,\tau,L)\) would imply \(\mathrm{FPT}=\mathrm{W}[1]\).

The hardness holds even when every approval type has size at most \(2\) and every mass is a dyadic rational.

Membership in \(\mathrm{NP}\) and an exact enumeration algorithm

Write each mass as \(\mu_i=a_i/b_i\), and write \(\theta=a_\theta/b_\theta\), with positive denominators. Set

\(D=b_\theta\prod_{i=1}^{\tau}b_i,\qquad w_i=a_i(D/b_i),\qquad H=a_\theta(D/b_\theta).\)

Then a committee \(W\) satisfies the threshold exactly when

\(\displaystyle \sum_{i:A_i\cap W\ne\varnothing}w_i\ge H.\)

These are integer computations. Since \(L\) is the total numerical bit length, \(D\), the \(w_i\), and \(H\) have \(\mathrm{O}(L)\) bits. Moreover, every represented-mass sum is at most \(D\), because the masses are positive and sum to \(1\). Constructing these integers takes \(\mathrm{O}((\tau+1)L^2)\) bit operations using elementary arithmetic.

A certificate lists the selected candidates. Its size is polynomial in the input length, since at most \(m\) candidates can be selected. Checking its cardinality, scanning the approval types, and computing the integer sum all take polynomial time in \(m,\tau,L\). Thus the problem belongs to \(\mathrm{NP}\).

For completeness, let \(k=\min\{K,m\}\). Represented mass is monotone under adding candidates: any type intersecting \(W\) also intersects every superset of \(W\). Therefore every feasible committee can be extended to size exactly \(k\) without decreasing its represented mass.

Enumerating all size-\(k\) committees consequently gives an exact algorithm with running time

\(\displaystyle \mathrm{O}\!\left(\binom{m}{k}\operatorname{poly}(m,\tau,L)\right).\)

In particular, this is an XP algorithm parameterized by \(K\), with running time bounded by \((m+1)^K\operatorname{poly}(m,\tau,L)\). It does not establish FPT tractability.

A reduction preserving \(K\)

We use the supplied result that explicitly listed, unweighted voters with approval sets of size at most \(p\) give an \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard decision problem parameterized by committee size, including the case \(p=2\). This is the bounded-frequency maximum-coverage problem studied by [Skowron–Faliszewski](https://arxiv.org/html/1309.4405).

Consider such a discrete instance with candidates \(C\), explicitly listed voters \(B_1,\ldots,B_n\), committee limit \(K\), and integer target \(t\). Its question is whether some committee represents at least \(t\) voters.

We may restrict to \(n\ge1\) and \(0\le t\le n\): other cases are immediately decidable and can be mapped to fixed yes- or no-instances with committee limit \(0\).

Aggregate identical ballots. For each distinct approval type \(A\), define

\(\displaystyle d_A=\bigl|\{j:B_j=A\}\bigr|.\)

Choose the power of two

\(\displaystyle Q=2^{\lceil\log_2(n+1)\rceil}.\)

Thus \(n<Q\le2n\). Construct the support-and-mass instance as follows:

• For each occurring nonempty type \(A\), assign mass \(\mu_A=d_A/Q\).
• Include exactly one empty type, assigning it mass \(\mu_{\varnothing}=(d_{\varnothing}+Q-n)/Q\), where \(d_{\varnothing}=0\) if no original voter has an empty ballot.
• Set \(\theta=t/Q\), and retain the same candidates and committee limit \(K\).

Every included mass is positive. In particular, the empty type has positive mass because \(Q>n\). The masses sum to

\(\displaystyle \frac{\sum_{A\ne\varnothing}d_A+d_{\varnothing}+Q-n}{Q}=1.\)

All approval types are distinct and have size at most \(p\). Every mass is dyadic, and the output support size is at most \(n+1\).

For every committee \(W\), the empty type contributes no represented mass. Hence

\(\displaystyle \sum_{A:A\cap W\ne\varnothing}\mu_A =\frac{|\{j:B_j\cap W\ne\varnothing\}|}{Q}.\)

Therefore,

\(\displaystyle \sum_{A:A\cap W\ne\varnothing}\mu_A\ge\theta \quad\Longleftrightarrow\quad |\{j:B_j\cap W\ne\varnothing\}|\ge t.\)

This proves both directions of the reduction.

Because the voters are explicitly listed, aggregating their types takes polynomial time in the source input length. The new numerators and denominators have \(\mathrm{O}(\log(n+1))\) bits, so the output also has polynomial size. Crucially, the parameter remains exactly \(K\).

Applying this reduction to the hard discrete instances with approval size at most \(2\) proves hardness for every fixed \(p\ge2\). Together with membership in \(\mathrm{NP}\), it proves \(\mathrm{NP}\)-completeness.

Consequence for exact FPT algorithms

Suppose the weighted support problem admitted an exact algorithm running in

\(\displaystyle f(K)(m+\tau+L)^c,\)

where \(f\) is computable and \(c\) is independent of \(K\). Composing it with the polynomial-time reduction above would give an FPT algorithm for the supplied \(\mathrm{W}[1]\)-hard discrete problem, because the output size is polynomial and \(K\) is preserved. This would imply \(\mathrm{FPT}=\mathrm{W}[1]\).

Thus, under the standard assumption \(\mathrm{FPT}\ne\mathrm{W}[1]\), the answer to the exact FPT question is no.

This argument establishes \(\mathrm{W}[1]\)-hardness; it does not assert \(\mathrm{W}[1]\)-membership for arbitrary binary-rational weights. Such membership is unnecessary for the stated obstruction to exact FPT time.

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned question correctly: it proves \(\mathrm{NP}\)-completeness and \(\mathrm{W}[1]\)-hardness parameterized by \(K\), including for dyadic masses and approval types of size at most \(2\). No mathematical gaps or false steps were found.

1. Use of the supplied hardness result

The prover states the source result with the necessary restrictions: explicitly listed unweighted voters, approval size bounded by a fixed \(p\), and parameter equal to the committee limit \(K\). This is precisely the result supplied in USER_TASK, so invoking it is justified.

The cited paper also supports the crucial size-\(2\) hardness through MaxVertexCover, where each covered element belongs to exactly two candidate sets. Although its displayed Theorem 1 says \(p>2\), the surrounding discussion and hardness argument explicitly identify the size-\(2\) case. Thus that wording does not undermine the prover’s reliance on the supplied result. [Skowron–Faliszewski](https://arxiv.org/html/1309.4405)

2. Exact arithmetic and membership in \(\mathrm{NP}\)

The denominator-clearing construction is valid:

• \(D\) is positive and divisible by every mass denominator and the threshold denominator.
• Consequently, every \(w_i\) and \(H\) is an integer.
• Multiplication by \(D>0\) preserves the threshold inequality, including when \(\theta\) is negative.
• The product defining \(D\) has bit length bounded by the sum of the denominator bit lengths, hence \(\mathrm{O}(L)\).
• The numerators defining \(w_i\) and \(H\) also give \(\mathrm{O}(L)\)-bit integers.
• Positivity and normalization imply every represented integer sum lies between \(0\) and \(D\).

The stated construction bound \(\mathrm{O}((\tau+1)L^2)\) is a valid elementary-arithmetic upper bound.

A committee certificate has polynomial length. Cardinality, candidate membership, intersections with the listed approval types, and the exact threshold comparison are all polynomial-time checks. Membership in \(\mathrm{NP}\) follows.

3. Enumeration algorithm and boundary cases

With \(k=\min\{K,m\}\), every permitted committee extends to a size-\(k\) committee. Representation is monotone under this extension, so enumerating only size-\(k\) committees is sufficient.

This also handles \(K=0\) and \(K\ge m\). Empty approval types do not affect monotonicity. Thresholds outside \([0,1]\) cause no problem for the exact comparison.

Both the stated enumeration bound and the XP bound are valid. Neither is presented as an FPT algorithm.

4. Reduction to positive normalized dyadic masses

For \(n\ge1\), the chosen power of two satisfies \(n<Q\le2n\). Thus every occurring nonempty type receives positive mass, and the single empty type receives strictly positive mass even when no original empty ballot exists.

The normalization calculation is correct. The construction preserves distinctness of support types and the approval-size bound, and every mass is dyadic.

For every committee, the empty type contributes zero. Each other type contributes its original multiplicity divided by \(Q\). Therefore represented mass equals the original represented-voter count divided by \(Q\). Comparing against \(t/Q\) gives exactly the original decision condition in both directions.

Aggregation and numerical encoding require polynomial time and output size because the original voters are explicitly listed. The nontrivial instances retain \(K\) exactly. The separately mentioned trivial-instance mappings with parameter \(0\) are also compatible with parameterized reductions.

5. Complexity conclusions

Using size-\(2\) source instances proves hardness for every fixed \(p\ge2\). Together with membership, this establishes \(\mathrm{NP}\)-completeness.

Composing the reduction with an assumed \(f(K)\operatorname{poly}(m,\tau,L)\) algorithm would yield an FPT algorithm for the supplied \(\mathrm{W}[1]\)-hard problem. The conditional conclusion concerning \(\mathrm{FPT}=\mathrm{W}[1]\) is therefore valid.

The prover appropriately does not claim \(\mathrm{W}[1]\)-membership for arbitrary rational weights. No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩