d4-conf-ijcai-2021-0456 (d4-conf-ijcai-2021-0456)

Given candidates C, a finite support T of partial-order types with binary-rational masses mu_t>0 summing to 1, and integers r,d,s, compute or decide whether there are r linear orders that each minimize K_mu(pi)=sum_{t in T} mu_t KT-dist(pi,t), have total pairwise Kendall–Tau diversity at least d, and have pairwise distance at least s.

Let \(C\) contain \(m\geq 1\) candidates. A society is given by its support: an explicit list \(T\) of \(\tau\geq 1\) distinct partial orders on \(C\), each with a positive binary-rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total binary input length.
For partial orders \(\alpha,\beta\), define \(\operatorname{KT}(\alpha,\beta)=|\{(x,y)\in C^2:x<_\alpha y\text{ and }y<_\beta x\}|\); incomparable pairs contribute zero. For a linear order \(\pi\), set \(K_\mu(\pi)=\sum_{t\in T}\mu_t\operatorname{KT}(\pi,t)\).
Given binary-encoded integers \(r\geq1\) and \(d,s\geq0\), decide whether there are \(r\) distinct linear orders \(\pi_1,\ldots,\pi_r\), each globally minimizing \(K_\mu\), such that \(\sum_{1\leq i<j\leq r}\operatorname{KT}(\pi_i,\pi_j)\geq d\) and \(\operatorname{KT}(\pi_i,\pi_j)\geq s\) for every \(i<j\). All minimizing orders are eligible, without tie-breaking.
Let \(\rho=\bigcap_{t\in T}t\), and let \(w\) be the pathwidth of the graph on \(C\) whose edges join distinct candidates incomparable in \(\rho\). State running times in \(m,\tau,L,r,d,s,w\).

Is this decision problem in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it fixed-parameter tractable parameterized by \((w,r,s)\)?

For explicit lists of partial votes, the diverse aggregation problem is FPT parameterized by unanimity width, number of solutions, solution imperfection, and scatteredness; this includes exact optima. The score-threshold version is NP-hard, including its single-solution restriction. [Arrighi et al.](https://arxiv.org/abs/2105.09413)
Computing a single optimal Kemeny order is NP-hard even for four complete votes. [Dwork et al.](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/rank_www10.html) No verified classification was found for the exact mass-based diversity decision problem stated here.

Classification

The problem is \(\mathrm{NP}\)-hard, even when \(\tau=1\), \(r=2\), \(s=1\), and the minimum score is zero. Nevertheless, it is fixed-parameter tractable parameterized by \((w,r,s)\), including with binary-rational masses and binary-encoded \(d\).

For \(r=1\), the answer is simply yes if and only if \(d=0\): an optimal order always exists, and both diversity conditions involve empty collections of pairs.

1. Hardness for one partial vote

We use the following established result: given a finite poset \(P\) and an integer \(k\), deciding whether two linear extensions of \(P\) disagree on at least \(k\) unordered pairs is \(\mathrm{NP}\)-complete. This is Theorem 5 of [Brightwell and Massow, *Diametral Pairs of Linear Extensions*](https://arxiv.org/html/0809.1828). We may restrict to \(k\geq1\): instances with \(k=0\) are always yes-instances and can be replaced by a fixed positive-threshold yes-instance.

Given such an instance \((P,k)\), construct a society on the ground set of \(P\) by setting
\[ T=\{P\},\qquad \mu_P=1,\qquad r=2,\qquad d=k,\qquad s=1. \]
Here and below, displayed formulas use the requested delimiters:
\(T=\{P\},\ \mu_P=1,\ r=2,\ d=k,\ s=1\).

For every linear order \(\pi\), its score is \(\operatorname{KT}(\pi,P)\). A linear extension of \(P\) has score zero. Conversely, score zero means that no comparable pair of \(P\) is reversed, so \(\pi\) is a linear extension. Thus the globally minimizing orders are exactly all linear extensions of \(P\).

For two linear orders, the specified Kendall distance counts each disagreeing unordered pair exactly once. Consequently, the constructed instance is yes precisely when \(P\) has two linear extensions at distance at least \(k\). Since \(k\geq1\), these orders are distinct and satisfy scatteredness at least one.

The construction is polynomial-time and proves the claimed hardness.

2. Every optimum respects unanimity

We first justify restricting the parameterized algorithm to linear extensions of \(\rho\).

Lemma. Every globally minimizing order extends \(\rho=\bigcap_{t\in T}t\).

Proof. Suppose \(a<_\rho b\), but a linear order \(\pi\) puts \(b\) before \(a\). Obtain \(\pi'\) by exchanging their positions.

Fix a vote \(t\). Because \(a<_\rho b\), we have \(a<_t b\). Reordering the pair \(\{a,b\}\) decreases its contribution by one.

For a candidate \(z\) between \(b\) and \(a\) in \(\pi\), the decrease from the two pairs involving \(z\) is

\( [\ z<_t b\ ]-[\ z<_t a\ ]+ [\ a<_t z\ ]-[\ b<_t z\ ], \)

where brackets denote indicator values. Both differences are nonnegative: transitivity gives \(z<_t a\Rightarrow z<_t b\) and \(b<_t z\Rightarrow a<_t z\). All remaining pair contributions are unchanged. Therefore

\( \operatorname{KT}(\pi,t)-\operatorname{KT}(\pi',t)\geq1. \)

Weighting and summing yields \(K_\mu(\pi)-K_\mu(\pi')\geq\sum_t\mu_t=1\). Hence \(\pi\) cannot be optimal. Applying this argument to every violated relation proves the lemma. \(\square\)

3. Polynomial-size integer encoding of the masses

Write each input mass as \(\mu_t=a_t/b_t\), with positive integers encoded in binary. Define

\( D=\prod_{t\in T}b_t,\qquad W_t=a_t(D/b_t). \)

These are positive integers satisfying \(\sum_tW_t=D\). Furthermore,

\( \log_2D=\sum_t\log_2b_t=O(L). \)

Thus their binary encodings have polynomial length; no voter replication is required.

Define a nonnegative integer pair cost by

\( c(x,y)=\sum_{t\in T}W_t[\ y<_t x\ ]. \)

For every linear order \(\pi\),

\( \sum_{x<_\pi y}c(x,y) =\sum_tW_t\operatorname{KT}(\pi,t) =D K_\mu(\pi). \)

Also, \(c(x,y)=0\) whenever \(x<_\rho y\), because every vote puts \(x\) before \(y\). Consequently, for a linear extension \(\pi\) of \(\rho\), its completion cost is

\( c(\pi\setminus\rho) =\sum_{x<_\pi y}c(x,y) =D K_\mu(\pi). \)

By the lemma, every global optimum belongs to this restricted domain. Positive scaling preserves all score comparisons and ties. Therefore the minimum-cost completions of \((\rho,c)\) are exactly the globally minimizing orders in the original problem.

The construction takes \(\operatorname{poly}(m,\tau,L)\) bit operations, including computing transitive closures if needed. Every cost is at most \(D\).

4. Applying the parameterized completion theorem

We use the integer-cost version of the cited result, rather than an algorithm requiring an explicitly replicated vote list.

A zero-safe consequence of Theorem 14 and the state count in Remark 5 of [Arrighi et al., *Diversity in Kemeny Rank Aggregation*](https://arxiv.org/html/2105.09413v1) is the following: for a poset on \(n\) elements, incomparability-graph pathwidth \(p\), and integer pair costs bounded by \(M\), exact-optimum diversity with \(r\) orders, scatteredness \(h\), and total threshold \(q\) is decidable in time

\( 2^{O(r(p+1)\log(p+2))} (h+1)^{O(r^2)} (q+1)\, \operatorname{poly}(n,\log(M+2),\text{threshold encoding lengths}). \)

This uses solution imperfection zero. The factors remain positive at zero thresholds: Remark 5 counts \(\delta+1\) cost values per structural state. The theorem constructs the required decomposition; one need not supply it.

All hypotheses hold here:

• \(\rho\) is a partial order, being an intersection of partial orders.
• Its incomparability graph has the specified pathwidth \(w\).
• The costs are nonnegative integers bounded by \(D\), whose bit length is \(O(L)\).
• Section 3 proves exact correspondence of all optimal solutions.

For \(r\geq2\), replace scatteredness by \(h=\max\{s,1\}\). This is equivalent to combining the original scatteredness requirement with distinctness, because two linear orders have distance zero exactly when they are identical.

Applying the theorem therefore gives the running-time bound

\( 2^{O(r(w+1)\log(w+2))} (s+2)^{O(r^2)} (d+1)\operatorname{poly}(m,\tau,L). \)

5. Removing numeric dependence on the binary threshold

The preceding dependence on \(d\) must be bounded to establish FPT for the stated binary encoding.

Let \(N=\binom m2\). Every pair of linear orders has distance at most \(N\), so every collection of \(r\) orders has total diversity at most

\( H=\binom r2 N. \)

For \(r\geq2\), reject immediately if \(d>H\) or \(s>N\). These comparisons use polynomial-time binary arithmetic. One may also reject if \(r>m!\).

On every remaining instance, \(d+1\leq1+\binom r2\binom m2\). Hence a valid overall bound is

\( 2^{O(r(w+1)\log(w+2))} (s+2)^{O(r^2)} \left(1+\binom r2\binom m2\right) \operatorname{poly}(m,\tau,L). \)

Absorbing the factors depending only on \(r\) into the parameter function, this is \(f(w,r,s)\operatorname{poly}(m,\tau,L)\), with a polynomial exponent independent of the parameters. This proves fixed-parameter tractability for the exact mass-based problem.

⟨structured verdict parsed — rendered above⟩

The claimed classification is proved: the problem is \(\mathrm{NP}\)-hard under the stated restrictions and fixed-parameter tractable parameterized by \((w,r,s)\). I found no major or minor mathematical issues.

• Single-solution case. For \(r=1\), the total diversity is zero and the scatteredness condition is vacuous. Since the finite, nonempty set of linear orders contains an optimum, the answer is exactly \(d=0\), regardless of \(s\). This is correct.

• Hardness reduction. The cited Theorem 5 states that deciding whether a poset has two linear extensions at distance at least \(k\) is \(\mathrm{NP}\)-complete, with precisely the disagreement distance used here. The theorem is accurately invoked. [Brightwell and Massow, Theorem 5](https://arxiv.org/html/0809.1828)

Restricting to \(k\geq1\) preserves hardness: zero-threshold instances are affirmative and can be replaced by a fixed affirmative positive-threshold instance.

With the sole vote \(P\) and mass one, scores are nonnegative, and every linear extension has score zero. Conversely, zero score forbids reversing any strict relation of \(P\), so the minimizing orders are exactly its linear extensions.

For two linear orders, each disagreeing unordered pair contributes exactly one ordered pair to the specified distance. Thus \(d=k\) reproduces the source condition. Because \(k\geq1\), distinctness and \(s=1\) follow automatically. The construction has polynomial size and proves the claimed restricted hardness.

• Unanimity lemma. The exchange calculation is correct. Before the exchange, an intervening candidate \(z\) appears in the order \(b,z,a\); afterward it appears as \(a,z,b\). The change in its two pair contributions is exactly the displayed indicator expression.

Transitivity of each vote gives both implications used to make the two differences nonnegative. The pair \(\{a,b\}\) contributes an additional decrease of one. Candidates outside the exchanged interval have unchanged relative positions with both endpoints.

Consequently, every vote’s score decreases by at least one, and the weighted score decreases by at least \(\sum_t\mu_t=1\). A globally minimizing order therefore cannot violate unanimity. No completeness assumption on individual votes is used.

• Mass encoding and completion costs. The denominator product \(D\) has binary length \(O(L)\). Each \(W_t\) is a positive integer, and normalization gives \(\sum_tW_t=D\). Hence every pair cost lies between zero and \(D\), with polynomial binary length.

The identity between the integer objective and \(D K_\mu\) follows by interchanging the finite sums. For an extension of \(\rho\), relations already in \(\rho\) contribute zero, so removing them gives exactly the completion objective. The unanimity lemma then establishes correspondence with all original global optima, including ties.

The claimed polynomial preprocessing bound is valid for exact binary arithmetic; it does not require replication of votes.

• Parameterized theorem application. Theorem 14 applies to general nonnegative integer pair costs and near-optimal linear extensions, with logarithmic dependence on the maximum cost. Setting imperfection to zero selects exact optima. Lemma 3 supplies the consistent decomposition without requiring it as input. [Arrighi et al., Lemma 3 and Theorem 14](https://arxiv.org/html/2105.09413v1)

The zero-safe restatement is justified. Remark 5 explicitly counts \(\delta+1\) cost values; Definition 10 gives finite capped diversity and scatteredness registers even when their thresholds are zero. The prover’s shifted factors correctly avoid the vanishing factors in the printed asymptotic bound. The factorial structural dependence fits the stated exponential bound. [Arrighi et al., Remark 5 and Definition 10](https://arxiv.org/html/2105.09413v1)

All required hypotheses are satisfied: \(\rho\) is a partial order, its incomparability graph has pathwidth \(w\), and the constructed costs have the required domain and encoding length.

For \(r\geq2\), replacing \(s\) by \(\max\{s,1\}\) is exactly equivalent to enforcing both scatteredness and distinctness. Its contribution is bounded by the displayed \((s+2)^{O(r^2)}\) factor.

• Binary thresholds and final running time. The bounds \(N=\binom m2\) and \(H=\binom r2N\) are correct. Rejecting \(d>H\) or \(s>N\) is valid for \(r\geq2\). The optional rejection \(r>m!\) is also valid.

On remaining instances, replacing \(d+1\) by \(1+\binom r2\binom m2\) bounds its numeric dependence by a parameter-dependent factor times a polynomial in \(m\). Threshold parsing and comparisons are covered by the total input length \(L\).

The final running time consequently has the asserted form \(f(w,r,s)\operatorname{poly}(m,\tau,L)\), with parameter-independent polynomial exponent. The cases \(m=1\), \(w=0\), and zero thresholds introduce no uncovered exception.

No repair or additional mathematical clarification is required. The proof establishes hardness without claiming membership of the unrestricted problem in \(\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩