PaperlayerView exact revision on arXiv

Source-linked AI summary

Ulam Rank Aggregation Is Hard to Approximate for Four Rankings

Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Mursalin Habib, Tien Long Nguyen

arXiv:2609.05874v1cs.CC

TL;DR

The paper asks whether Ulam rank aggregation remains approximable when only a few rankings are given, motivated by the contrast between Ulam and Kendall-tau median. It develops a Boolean-CSP reduction framework and proves constant-factor inapproximability for Ulam median and center with four inputs.

  • Problem

    The paper investigates whether Ulam median has approximation guarantees comparable to Kendall-tau median, which admits a PTAS despite being NP-hard for three rankings.

  • Method

    The paper introduces a reduction framework from Boolean CSPs to Ulam median, using clause and consistency scores to encode satisfying assignments, and transfers hardness to Ulam center.

  • Results

    Constant-factor inapproximability holds for both Ulam median and Ulam center with four input permutations, ruling out PTASs unless P = NP.

  • Takeaways & Limitations

    Four inputs mark a sharp boundary: Ulam aggregation is exactly polynomial-time solvable with three inputs but becomes constant-factor inapproximable with four.

  • Takeaways & Limitations

    The current reduction does not optimize the inapproximability factor, leaving stronger bounds and extensions to non-Boolean CSPs as open directions.

Abstract

from arXiv · show

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ulam distances to the input rankings, while in the \emph{Ulam center} problem, the objective is to minimize the maximum such distance. We prove that, for every $0<\varepsilon< 1/34$, it is $\mathrm{NP}$-hard to approximate either Ulam median or Ulam center within a factor of $35/34-\varepsilon$, even when the input consists of only four rankings. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. Prior to our work, only the exact versions of both problems were known to be $\mathrm{NP}$-hard, and that too only when the number of input rankings is unbounded [Fischer et al., ESA'25 and Bachmaier et al., J. of Discrete Algorithms'15]. Furthermore, our inapproximability results are optimal in terms of the number of input rankings since for three inputs it is already known to be polynomial-time solvable [Chakraborty, Das, Krauthgamer, SODA'21]. En route, we introduce a new general framework for reducing Boolean constraint satisfaction problems (CSP) to the Ulam median with only four inputs. As a specific instantiation of the reduction framework, we obtain our hardness-of-approximation results. The corresponding hardness for the Ulam center follows from a reduction from the Ulam median.

1 Introduction

The paper studies rank aggregation under Ulam distance and establishes that four inputs suffice for strong inapproximability, contrasting with exact polynomial-time solvability for three inputs. It develops a four-permutation CSP reduction framework and transfers the resulting hardness from Ulam median to Ulam center.

  • Problem setting: Ulam rank aggregation seeks a consensus permutation, with median minimizing total distance and center minimizing the maximum distance to the inputs.Ulam distance equals the number of moves between permutations, equivalently the alphabet size minus their LCS length.
  • Prior gap: Prior work established NP-hardness for Ulam median only with an unbounded number of inputs, while three-input Ulam median is solvable exactly in polynomial time.The fixed-input complexity gap motivated the paper’s hardness results for four inputs.
  • Main results: Four input permutations suffice for constant-factor inapproximability: Ulam median and Ulam center are NP-hard to approximate within 35/34 − ε for every fixed 0 < ε < 1/34.The same bound is stated separately for both objectives under exactly four inputs.
  • Main results: Unless P = NP, neither Ulam median nor Ulam center admits a polynomial-time additive approximation scheme, even with four inputs.The additive gaps are linear in the total input length for median and in the alphabet size for center.
  • Implications: The results establish a sharp transition from exact polynomial-time solvability with three inputs to constant-factor inapproximability with four.This contrasts with edit-distance median, which is polynomial-time solvable for every fixed number of input strings, and with Kendall-tau median, which has a PTAS.
  • Technical approach: The reduction uses clause and consistency gadgets whose combined score encodes satisfiability, then reduces Ulam median to Ulam center while preserving the number of inputs.The general framework converts Boolean CSP gadgets into four-input Ulam median instances; the center reduction preserves optimum values and approximation hardness.

2 Preliminaries

The preliminaries define permutations, restrictions, LCS, Ulam distance, and the median and center objectives. They also specify approximation-scheme notions and the Boolean CSP source problem used in the reductions.

  • Permutations and Ulam distance: For a permutation π and subset S, π|S preserves the relative order of symbols in S; LCS measures the longest common subsequence of two sequences.These operations support the reduction’s clause and consistency scores.
  • Permutations and Ulam distance: Ulam distance between permutations is expressed through their LCS, linking move distance to common ordered subsequences.The paper repeatedly uses this identity to convert permutation distances into LCS scores.
  • Optimization objectives: Ulam median minimizes the sum of distances from a candidate permutation to all input permutations.Its optimum is denoted OPTmed(Π).
  • Optimization objectives: Ulam center minimizes the maximum distance from a candidate permutation to any input permutation.Its optimum is denoted OPTctr(Π).
  • Approximation schemes: A PTAS achieves cost at most (1 + ε)OPT, while additive schemes allow εkd error for median and εd error for center.Here k is the number of input permutations and d is the alphabet size.
  • Source CSP: Max-E3-Lin-2 is a Boolean CSP whose constraints are three-variable equations over F2, with the objective of maximizing satisfied equations.The reduction uses its gap-hardness formulation as a source problem.

3 The Basic 3-SAT Reduction

The reduction encodes a balanced 3-SAT instance into four permutations whose Ulam median reflects clause satisfaction and variable consistency. An anchor block enforces canonical medians, yielding explicit four-permutation hardness results.

  • Instance encoding: The construction uses one distinct symbol per literal occurrence, with N = 3m symbols and balanced positive and negative occurrences for every variable.Each occurrence receives a label indicating the variable value that makes its literal true.
  • Truth partitions: A truth partition divides literal occurrences into proposed true and false sides, and consistency requires each variable’s positive and negative occurrences to occupy opposite sides.Assignments induce consistent partitions whose true side contains exactly the satisfied literal occurrences.
  • Gadgets: The clause-witness gadget contributes one LCS symbol per clause containing a selected occurrence, so its score equals the number of represented clauses.Reversing each clause’s three-symbol order limits any common subsequence to one symbol per clause, while preserving the common clause order permits one choice whenever available.
  • Gadgets: The variable-consistency gadget orders the two label classes oppositely, limiting its LCS contribution to at most N/2 and rewarding consistent selections.For each variable, a common subsequence can use symbols from at most one label class.
  • Anchor block: The anchor block lets every candidate median be transformed into the canonical form τLZτR without decreasing any of its four LCS scores.The induced partition determines the proposed true and false sides, after which the fixed-partition optimum combines clause and consistency scores.

4 A General Framework for Boolean CSPs

The framework replaces the 3-SAT-specific clause gadget with local gadgets for arbitrary Boolean CSP constraints while retaining the consistency and anchor machinery. A source CSP gap then transfers to a four-permutation Ulam-median gap under explicit gadget parameters.

  • Framework: The framework isolates the clause-witness gadget as the only 3-SAT-specific component and replaces it with local constraint gadgets.A suitable gadget scores agreement sets highly exactly when the corresponding constraint is satisfied, while shared consistency and balance assumptions remain unchanged.
  • Local gadgets: Each constraint receives a disjoint alphabet of B symbols and two permutations whose agreement-set score has baseline A and gap Δ.The parameters are fixed independently of the constraint index and quantify gadget size and efficiency.
  • Balance: Global balance makes the numbers of symbols agreeing and disagreeing with any assignment independent of the assignment.This preserves the consistency calculation used in the basic reduction.
  • Score composition: Constraint blocks are placed in the same order in both gadget permutations, so their local LCS scores add across constraints.The global score decomposes into the sum of the blockwise longest common subsequence scores.
  • Canonical medians: The anchor construction again restricts attention to medians of the form τLZτR, interpreting the two sides as agreement and disagreement sets.The fixed-partition analysis combines the constraint and consistency scores as in the 3-SAT proof.
  • Gap transfer: A source CSP gap transfers to four-permutation Ulam-median hardness, with input length 3Bm + 1 and approximation factor governed by A, B, Δ, and the completeness and soundness values.The framework emphasizes that stronger source gaps do not automatically yield stronger Ulam hardness; gadget efficiency relative to the fixed overhead matters.

5 An Instantiation for Max-E3-Lin-2

The paper instantiates its four-permutation CSP-to-Ulam-median framework with Max-E3-Lin-2 using balanced local gadgets whose LCS distinguishes satisfied from violated equations. This yields a 35/34−ε hardness factor and additive inapproximability for four inputs.

  • Motivation: Max-E3-Lin-2 supplies a larger gap than 3-SAT and enables efficient local gadgets, leading to a 35/34 hardness factor for Ulam median.The paper contrasts this with the 53/52 factor obtained from its 3-SAT instantiation.
  • Local gadget: The construction uses an eight-symbol local gadget for each equation over three distinct Boolean variables.The gadget is incorporated into the general four-permutation framework.
  • Local gadget: For each local assignment, the gadget's restricted LCS is 3 when the parity equation is satisfied and 2 otherwise.Each variable also has equally many symbols with labels 0 and 1 in the gadget.
  • Global construction: The resulting four permutations have length 24m+1, where m is the number of Max-E3-Lin-2 equations.The length follows from the gadget parameters B=8, A=2, and Δ=1.
  • Hardness result: For every fixed 0<ε<1/34, approximating Ulam median within 35/34−ε is NP-hard with exactly four input permutations.The proof combines the local gadget with a CSP gap theorem.
  • Additive hardness: For every fixed 0<ε≤1/200, an additive εkd-factor approximation is NP-hard even with k=4.The reduction uses four permutations over an alphabet of size d=24m+1.

6 Hardness of Approximation for Ulam Center

The paper transfers Ulam-median hardness to Ulam center through a polynomial-time, cost-preserving reduction that keeps the number of permutations unchanged. Consequently, Ulam center inherits the same multiplicative and additive hardness for four inputs.

  • Multiplicative hardness: For every fixed 0<ε<1/34, approximating Ulam center within 35/34−ε is NP-hard with exactly four input permutations.A better approximation for center would yield the forbidden approximation for median.
  • Reduction: The reduction is approximation-factor preserving and applies to Ulam center while maintaining the number of input permutations.The paper provides a detailed proof of the cost-preservation guarantees.
  • Reduction: The median-to-center reduction maps k permutations over an alphabet of size d to k center permutations over an alphabet of size kd.It preserves the optimum value and converts any center solution of radius R into a median solution of cost at most R.
  • Additive hardness: For every fixed 0<ε≤1/200, an additive εd-factor approximation for Ulam center is NP-hard with k=4.The reduction constructs a center instance with alphabet size d=4ℓ from a median instance of permutation length ℓ.

7 Conclusion

The paper establishes constant-factor inapproximability for Ulam rank aggregation with four inputs, ruling out PTASs and transferring the result from median to center. It leaves stronger-factor bounds and broader CSP extensions as open directions.

  • Contributions: The paper introduces a general reduction framework from Boolean CSPs to Ulam median using only four input permutations.The reported hardness factor is not optimized by the current instantiation.
  • Contributions: Unless P=NP, neither Ulam median nor Ulam center admits a PTAS with only four input permutations.The result is an explicit constant-factor inapproximability statement.
  • Open directions: The paper identifies narrowing the gap between its lower bounds and the best known approximation algorithms as a next step.Extending the framework to non-Boolean CSPs is suggested as one possible route.
  • Open directions: The paper also leaves open whether Ulam center can beat factor 2 when the number of inputs is part of the input.This is stated as a separate open direction for the center problem.

A Balanced Max-3-SAT Hardness

This appendix establishes balanced hardness for 3-SAT and Max-3-SAT by equalizing positive and negative variable occurrences while preserving satisfiability and controlling formula size. The resulting restrictions support the later Ulam reductions.

  • Balanced 3-SAT: A polynomial-time transformation converts a 3-CNF formula into one whose clauses have exactly three literal occurrences and whose variables have balanced signs.The transformed formula has a number of clauses linear in the original.
  • Balanced 3-SAT: 3-SAT remains NP-hard under the restrictions of exactly three literal occurrences per clause and equally many positive and negative occurrences per variable.The balanced transformation establishes these restricted hardness conditions.
  • Balanced 3-SAT: Adding tautological clauses preserves satisfiability while making the resulting formula balanced.The construction therefore retains the original satisfiability status.
  • Balanced Max-3-SAT: For every fixed 0<η<1/16, it is NP-hard to distinguish Max-3-SAT instances with optimum at least (1−η)m from those with optimum at most the stated soundness threshold.The hardness applies even when clauses contain three distinct variables and variable signs are balanced.
  • Balanced Max-3-SAT: The Max-3-SAT construction replaces each violated assignment of a three-variable equation with a clause false precisely on that assignment.A satisfying equation satisfies all four clauses, whereas a violating assignment satisfies exactly three.

B Approximation for a Fixed Number of Inputs

For every fixed number k of inputs, the paper gives a deterministic Ulam-median approximation algorithm that rounds an optimal edit-median string into a permutation. Its running time is O(2k+1dk+1), and for k = 4 it yields a 5/4-approximation.

  • Approximation guarantee: 5/4-approximation is obtained when k = 4.
  • Algorithm: For every fixed k ≥2, the algorithm returns a permutation with a provable approximation guarantee in O(2k+1dk+1) time.It first computes an optimal length-d string using dynamic programming, then removes duplicate symbols and inserts missing symbols.
  • Algorithm: The rounding starts from an optimal edit-median string, retains the most widely aligned occurrence of each repeated symbol, and inserts missing symbols in the order of a reference input.
  • Analysis: E ≤2 OPT and M ≤E/2k bound the edit-median cost and the number of missing symbols used in the rounding analysis.
  • Analysis: The duplicate-removal and insertion steps preserve enough common-subsequence structure to bound the final permutation's total edit distance by E + (k −2 − 12∤k)M.
  • Analysis: The analysis combines the rounding lemmas with the edit-to-Ulam relation ED(x, πi) = 2U(x, πi) to derive the approximation factor.

C Reduction from the Ulam Median to the Ulam Center

The median-to-center reduction cyclically places copies of the input permutations into ordered blocks, preserving the optimum value. Any center solution can then be converted into a median solution of no greater cost.

  • Reduction construction: For k inputs, cyclic shifts place one copy of every original permutation in each center input while preserving the block structure.
  • Reduction analysis: Stable sorting any center candidate into the common block order does not increase its distance to the center inputs.
  • Reduction analysis: The center candidate's LCS decomposes across alphabet blocks, allowing each block to define a permutation candidate for the original median instance.
  • Optimum preservation: Every center candidate has radius at least OPTmed(Π), while an optimal median placed in every block attains the same value.
  • Optimum preservation: At least one extracted block has median cost no larger than the center radius, yielding lossless recovery of a median solution.
Loading 2609.05874v1…