Low-Distortion Clustering with Ordinal and Limited Cardinal Information (aaai24-28811)

Given finite location types \(T\) with rational positive masses \(\mu\) summing to \(1\), complete rankings \(\pi_t\), integers \(k\) and \(K\), and no distance queries, where an unknown metric \(d\) on \(T\) is consistent with all rankings, what is the minimum \(K\) such that a randomized algorithm outputs \(C \subseteq T\) with \(|C| \le K\) and, for every consistent \(d\), achieves \(\Pr[\max_{t \in T} \min_{c \in C} d(t,c) \le \alpha \min_{|C'|=k} \max_{t \in T} \min_{c \in C'} d(t,c)] \ge 2/3\)?

A society is given by its support: a list \(T\) of \(\tau\) location types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; all eligible center locations are \(T\), so \(m=\tau\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k,K\).
Each type supplies a complete ranking \(\pi_t\) of \(T\), including itself first. A consistent metric \(d:T\times T\to\mathbb R_{\ge0}\) satisfies \(d(t,\pi_t(i))\le d(t,\pi_t(j))\) whenever \(i<j\); equal distances may be ordered arbitrarily. Promise that at least one consistent metric exists.
The remaining inputs are integers \(1\le k,K\le\tau\) and a binary-rational distortion threshold \(\alpha\ge1\). Define \(r_d(C)=\max_{t\in T}\min_{c\in C}d(t,c)\) and \(\operatorname{OPT}_k(d)=\min_{C'\subseteq T,\ |C'|=k}r_d(C')\).
Call \(K\) feasible if there exists a probability distribution \(q\) over nonempty sets \(C\subseteq T\) with \(|C|\le K\), chosen using only the given input and no distance queries, such that for every consistent metric \(d\), \(\Pr_{C\sim q}[r_d(C)\le\alpha\operatorname{OPT}_k(d)]\ge2/3\). The same distribution must serve every consistent metric; the successful sets may depend on the metric.

Is deciding whether \(K\) is feasible polynomial-time solvable, or is it NP-hard?

For finite unweighted locations, any zero-query algorithm with fixed finite distortion and constant success probability requires \(\Omega(2^k)\) centers in the worst case; a deterministic zero-query algorithm achieves distortion \(2\) using at most \(2^{k-1}\) centers. [Source](https://arxiv.org/pdf/2402.04035)
No result settling the exact per-input feasibility problem above was identified in the literature search.

Result

Deciding whether \(K\) is feasible is \(\mathrm{NP}\)-hard. This holds even with the fixed threshold \(\alpha=\tfrac32\) and \(k=\tau-1\).

The proof gives a polynomial-time many-one reduction from satisfiability. On the constructed instances, a satisfying assignment yields a deterministic center set that succeeds for every consistent metric. An unsatisfiable instance yields one consistent metric on which every allowed center set fails.

1. Rankings that force graph-edge distances to be equal

Let \(H=(V,E)\) be a connected simple graph with \(N\) vertices, all of positive even degree. We construct rankings of \(V\) with the following properties:

• Every consistent metric assigns the same distance \(\delta\) to all edges of \(H\).
• Every distance between distinct vertices is at least \(\delta\).
• The metric assigning distance \(1\) to edges and distance \(2\) to nonedges is consistent.

Since \(H\) is connected and all degrees are even, Euler’s theorem supplies a circuit using every edge exactly once. Write it as
\(v_0,e_1,v_1,e_2,\ldots,e_M,v_M\), where \(v_M=v_0\), and interpret edge indices cyclically.

At each visit to a vertex, pair the incoming edge with the outgoing edge. At any fixed vertex, these pairs partition its incident edges: each incident edge is used exactly once at that endpoint.

Construct the ranking at a vertex \(v\) as follows:

• Put \(v\) first.
• List all graph neighbors, placing the incoming neighbor before the outgoing neighbor within each pair. The pairs themselves may appear in any order.
• List all nonneighbors afterward, in any order.

The pairs are disjoint, so these instructions define a complete ranking.

For a consistent metric \(d\), let \(x_i\) denote the length of edge \(e_i\). The comparison at the vertex between \(e_i\) and \(e_{i+1}\), together with symmetry of \(d\), gives \(x_i\le x_{i+1}\). Thus

\(x_1\le x_2\le\cdots\le x_M\le x_1\).

Consequently, every edge has a common length \(\delta\). Every vertex has a graph neighbor, and its graph neighbors precede its nonneighbors. Hence \(d(u,v)\ge\delta\) whenever \(u\ne v\).

For the promised consistent metric, define \(d_H(v,v)=0\), and, for distinct vertices, set \(d_H(u,v)=1\) if \(\{u,v\}\in E\), and \(d_H(u,v)=2\) otherwise.

This is a metric. For three distinct vertices, the sum of two distances is at least \(2\), while the third distance is at most \(2\); triangles involving repeated vertices also satisfy the triangle inequality. It is consistent with the rankings because graph neighbors precede nonneighbors, and ties may be ordered arbitrarily.

2. Feasibility becomes graph domination

A set \(D\subseteq V\) is a dominating set of \(H\) if every vertex outside \(D\) has a graph neighbor in \(D\).

Use the rankings above, set \(k=N-1\), and fix any threshold \(1\le\alpha<2\). We claim that

\(K\text{ is feasible}\quad\Longleftrightarrow\quad H\text{ has a dominating set of size at most }K.\)

First, consider any consistent metric \(d\), and let \(\delta\) be its common graph-edge length. A center set of size \(N-1\) omits exactly one vertex \(v\). Every graph neighbor of \(v\) is selected, so the distance from \(v\) to its nearest center is \(\delta\): an edge attains \(\delta\), and every distance to another vertex is at least \(\delta\). All selected vertices have distance zero to the center set. Therefore

\(\operatorname{OPT}_{N-1}(d)=\delta.\)

If \(D\) dominates \(H\), every vertex outside \(D\) has a selected neighbor at distance \(\delta\). Thus

\(r_d(D)\le\delta=\operatorname{OPT}_{N-1}(d)\le\alpha\operatorname{OPT}_{N-1}(d).\)

This holds for every consistent metric. The point-mass distribution on the fixed set \(D\) therefore succeeds with probability \(1\), using no distance information.

Conversely, consider the consistent metric \(d_H\). Its optimum with \(N-1\) centers is \(1\). If a nonempty center set \(C\) does not dominate \(H\), some vertex \(v\notin C\) has no graph neighbor in \(C\). Every distance from \(v\) to a center is then \(2\), so

\(r_{d_H}(C)=2>\alpha\operatorname{OPT}_{N-1}(d_H).\)

If \(H\) has no dominating set of size at most \(K\), every allowed center set fails on this one metric. Any distribution over those sets consequently has success probability zero. This proves the equivalence, including the randomized requirement.

3. A satisfiability reduction to the required graphs

We now construct connected graphs of positive even degree whose domination problem encodes satisfiability.

Start with a formula \(\varphi\) in conjunctive normal form, with at most three literals per clause. Satisfiability for this class is \(\mathrm{NP}\)-complete. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).

Let the formula have \(n\ge2\) variables and \(s\) nonempty clauses. These restrictions preserve hardness: one can add unused variables to ensure \(n\ge2\), and the usual three-literal satisfiability instances have nonempty clauses.

Construct a base graph \(G\) with:

• Two literal vertices \(\ell_i^+\) and \(\ell_i^-\) for each variable \(x_i\).
• A variable vertex \(a_i\) for each variable.
• A clause vertex \(b_j\) for each clause.

Make all \(2n\) literal vertices a clique. Join \(a_i\) precisely to \(\ell_i^+\) and \(\ell_i^-\). Join \(b_j\) precisely to the literal vertices representing literals in its clause. Add no other edges.

Set \(r=2(n+1)\). Replace every vertex \(v\) of \(G\) by an independent block \(B_v\) of \(r\) clones. For every edge \(\{u,v\}\) of \(G\), place all edges between \(B_u\) and \(B_v\). Call the resulting graph \(H\).

Its number of vertices is

\(N=r(3n+s)=2(n+1)(3n+s).\)

Every clone of \(v\) has degree \(r\deg_G(v)\), which is positive and even. The literal blocks form a connected complete multipartite graph, and every variable or clause block has a neighbor among the literal blocks. Thus \(H\) is connected and satisfies the hypotheses of Section 1.

We prove

\(\varphi\text{ is satisfiable}\quad\Longleftrightarrow\quad H\text{ has a dominating set of size at most }n.\)

A satisfying assignment gives a dominating set

Given a satisfying assignment, choose one clone from \(B_{\ell_i^+}\) if \(x_i\) is true, and one clone from \(B_{\ell_i^-}\) otherwise. Let \(D\) be the resulting set of \(n\) vertices.

Every variable block is adjacent to the selected literal for its variable. Every clause block is adjacent to a selected literal satisfying its clause.

Finally, every literal block is adjacent to a selected literal block belonging to a different variable. Such a variable exists because \(n\ge2\), and distinct literal vertices are adjacent in \(G\). Hence every vertex of every literal block is dominated as well.

Therefore \(D\) dominates \(H\).

A small dominating set gives a satisfying assignment

Suppose \(D\) dominates \(H\) and \(|D|\le n\).

Since each block contains \(r>n\) vertices, every block contains an unselected clone. In particular, an unselected clone in \(B_{a_i}\) must have a neighbor in \(D\). Its neighbors lie precisely in

\(B_{\ell_i^+}\cup B_{\ell_i^-}.\)

Thus \(D\) contains at least one vertex from this union for each variable. These \(n\) unions are pairwise disjoint. The budget \(|D|\le n\) therefore forces exactly one selected clone per variable’s literal-block pair, with no selected vertices elsewhere.

Assign \(x_i\) to be true precisely when the selected clone belongs to \(B_{\ell_i^+}\).

An unselected clone in any clause block \(B_{b_j}\) must also have a neighbor in \(D\). Its neighboring literal blocks represent precisely the literals appearing in that clause. The selected neighboring literal is true under the assignment just defined. Every clause is therefore satisfied.

This proves the equivalence.

4. Constructing the society and bounding its size

Apply Section 1 to \(H\), and make its vertices the support and the eligible center locations. Set

\(m=\tau=N,\qquad k=N-1,\qquad K=n,\qquad\alpha=\tfrac32.\)

All parameter restrictions hold.

For explicitly dyadic positive masses, label the vertices by \(1,\ldots,N\), put \(b=\lceil\log_2N\rceil\), and choose

\(\mu_i=2^{-b}\text{ for }1\le i<N,\qquad \mu_N=(2^b-N+1)/2^b.\)

These masses are positive, sum to \(1\), and each requires \(O(\log N)\) bits. The masses do not affect the radius, which takes a maximum over the support.

The consistent metric \(d_H\) explicitly verifies the metric-existence promise.

The graph has at most \(O(\tau^2)\) edges. Constructing it, finding its Euler circuit, and assembling all rankings take \(O(m\tau)=O(\tau^2)\) operations on \(O(\log\tau)\)-bit words. Serializing the input costs \(O(L)\) bit-output operations, with

\(L=O(m\tau\log\tau)=O(\tau^2\log\tau).\)

Thus the reduction runs in polynomial time. Moreover, \(\tau=2(n+1)(3n+s)\) is polynomial in the original formula size.

Combining the proved equivalences gives

\(\varphi\text{ is satisfiable}\quad\Longleftrightarrow\quad H\text{ has a dominating set of size at most }n\quad\Longleftrightarrow\quad K\text{ is feasible}.\)

Therefore the stated per-input feasibility problem is \(\mathrm{NP}\)-hard, even for fixed \(\alpha=\tfrac32\) and \(k=\tau-1\). A polynomial-time decision algorithm would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the requested decision problem: feasibility is \(\mathrm{NP}\)-hard, even when \(\alpha=\tfrac32\) and \(k=\tau-1\). I found no major or minor gaps requiring repair.

• The rankings force equality of graph-edge lengths.

The Euler-circuit theorem is applied with the required hypotheses: \(H\) is finite, connected, and every vertex has even degree. Positive degree also ensures that every vertex has a neighbor.

At each vertex, the incoming–outgoing pairs partition its incident edges. This includes the cyclic pairing of the last and first edges at the circuit’s starting vertex. Because the graph is simple and the circuit uses each edge once, each pair consists of distinct incident edges and distinct neighboring vertices. Consequently, the prescribed comparisons can be incorporated into a complete ranking without conflict.

For each consecutive pair of circuit edges, consistency and metric symmetry give \(x_i\le x_{i+1}\). The cyclic comparison supplies \(x_M\le x_1\), so all graph edges indeed have the same length \(\delta\).

The lower bound on every off-diagonal distance also follows: an adjacent pair has distance \(\delta\), while each nonneighbor appears after every neighbor in its endpoint’s ranking. Additional comparisons introduced by ordering the pairs do not invalidate the construction, since the explicit witness metric satisfies all of them.

• The promised consistent metric is valid.

The proposed \(d_H\) is symmetric, vanishes precisely on the diagonal, and is positive elsewhere. For three distinct vertices, each summand in a two-edge path is at least \(1\), whereas the remaining distance is at most \(2\). This verifies every nontrivial triangle inequality. Repeated-vertex cases are immediate.

All neighbors have distance \(1\), and all nonneighbors have distance \(2\). Thus the rankings are consistent, including the arbitrary ordering within each distance class. The metric-existence promise is explicitly satisfied.

• The domination–feasibility equivalence respects the metric and probability quantifiers.

Every set of \(N-1\) centers omits one vertex. That vertex has a selected graph neighbor at distance \(\delta\), and no selected vertex can be closer than \(\delta\). Therefore every such set has radius \(\delta\), establishing
\[ \operatorname{OPT}_{N-1}(d)=\delta. \]

A dominating set \(D\) covers every unselected vertex through an edge of length \(\delta\). Selected vertices have distance zero to \(D\). Hence its radius is at most the optimum for every consistent metric. A single point-mass distribution therefore works simultaneously for all those metrics.

Conversely, under \(d_H\), any nonempty nondominating set leaves an unselected vertex whose distance to every center is \(2\). Its radius is exactly \(2\), while \(\operatorname{OPT}_{N-1}(d_H)=1\). The strict inequality needed for failure holds throughout the stated range \(1\le\alpha<2\).

If no allowed dominating set exists, this same metric defeats every allowed center set. Thus every distribution has success probability zero on that metric. This correctly handles randomization; it does not interchange the existential distribution and universal metric quantifiers.

A dominating set here is necessarily nonempty because the graph has vertices, so the forward direction also respects the nonempty-center requirement.

• The satisfiability reduction produces the required graphs.

The source problem—satisfiability of conjunctive-normal-form formulas with at most three literals per clause—is \(\mathrm{NP}\)-complete, as stated in [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf). Restricting to nonempty clauses preserves hardness, and adding unused variables preserves satisfiability while ensuring \(n\ge2\).

Every base-graph vertex has positive degree: literal vertices belong to a clique of size \(2n\), variable vertices have two literal neighbors, and clause vertices have at least one literal neighbor. The base graph is connected.

Replacing vertices by independent blocks preserves the stated adjacency structure. Each clone has degree \(r\deg_G(v)\), which is positive and even because \(r=2(n+1)\). Connectivity of \(H\) follows from the connected literal-block subgraph and the attachments of all remaining blocks. The vertex count \(N=2(n+1)(3n+s)\) is correct.

• Both directions of the satisfiability–domination equivalence are valid.

A satisfying assignment selects exactly one literal clone per variable. These selections dominate every variable block and every clause block. They also dominate every literal block: because \(n\ge2\), there is a selected literal belonging to another variable, and its entire block is adjacent to the block being checked. This explicitly covers unselected clones in a selected literal’s own independent block.

Conversely, \(r>n\) ensures that every block contains an unselected clone whenever \(|D|\le n\). An unselected variable clone requires a selected clone in its own variable’s literal-block pair. The \(n\) pairs are disjoint, forcing exactly one selection per pair and no selections elsewhere.

The resulting assignment is well-defined. Every clause block contains an unselected clone whose selected neighbor must represent a literal in that clause. That literal is true under the defined assignment. Thus all clauses are satisfied.

• The society encoding and polynomial bound are sufficient.

The parameters satisfy \(m=\tau=N\), \(1\le k=N-1\le N\), and \(1\le K=n\le N\). The threshold is the fixed binary rational \(\tfrac32\).

Since \(2^b\ge N\), the last mass has positive numerator. The mass sum is
\[ \frac{N-1+2^b-N+1}{2^b}=1. \]
Each mass has \(O(\log N)\) encoding length. Their absence from the radius calculations is legitimate because the objective takes a maximum over the positive-mass support.

The stated \(O(m\tau)\) word-operation bound and \(O(L)\) serialization bound establish polynomial construction time. With \(O(\log\tau)\)-bit words, these are compatible with a polynomial bit-time bound, and the explicit rankings have total length \(O(m\tau\log\tau)\). The output support size is polynomial in the source formula size.

The two equivalences therefore establish a polynomial-time many-one reduction to the exact promised feasibility problem. No additional clarification is needed. The proof establishes hardness; it does not claim membership in \(\mathrm{NP}\) or unconditional exclusion of a polynomial-time algorithm.

⟨structured verdict parsed — rendered above⟩