PaperlayerView exact revision on arXiv

Source-linked AI summary

Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting

Jakub Dargaj, Aris Filos-Ratsikas, Paul W. Goldberg

arXiv:2609.35386v1cs.GT

TL;DR

The paper asks how to cover incomplete binary strings with a fixed number of centers under an agreement threshold, motivated in particular by designing representatives voters will delegate to. It classifies computational complexity by the number of centers and threshold, giving a complete picture for missing-entry strings while leaving a narrow threshold range unresolved for complete strings.

  • Problem

    The paper asks how to classify the complexity of covering incomplete binary strings with a fixed number of centers under a hard agreement threshold, a model motivated by delegated voting.

    Source: §1 · p. 1

  • Method

    The paper classifies tractability by center count and agreement threshold, using CSP dichotomies for hardness with missing entries and code-distance constructions for complete strings.

    Source: §2 · p. 5

  • Results

    The classification is complete when strings may have missing entries, while the complete-string results extend hardness to any number of centers and large thresholds but leave a narrow threshold range unresolved.

    Source: §1.1 · p. 3, §5 · p. 16

  • Takeaways & Limitations

    In delegated voting, the model treats representatives as centers and voter willingness to delegate as an agreement threshold over known issues.

    Source: §1 · p. 1

    For complete strings, the intractability landscape leaves an unresolved range of thresholds.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a given relative distance of the closest center. The problem has applications in binary $k$-center clustering and bioinformatics, but our main motivation comes from computational social choice. In the setting of multi-issue approval voting, we consider an algorithmic question that precedes any election: how should representatives be designed so that as many voters as possible are willing to delegate? We study the problem in two dimensions, namely the number of centers and the agreement threshold, parameters that are application-specific, and provide a complete picture of its computational complexity when entries may be missing. For the special case without missing entries, we extend our hardness results to any number of centers and large values of threshold, leaving a narrow range of thresholds unresolved.

1 Introduction

The paper studies covering incomplete binary strings with a fixed number of centers under a hard agreement threshold, motivated especially by delegated voting. It classifies tractability by the number of centers and threshold, then relates the problem to earlier string-covering and voting models.

1 Introduction

  • A string is represented when at least one of k complete centers agrees with it on at least a τ-fraction of its non-missing coordinates.In delegated voting, strings encode voters’ approval preferences, missing entries indicate issues they do not know or care about, and the threshold represents willingness to delegate.Source: §1 · pp. 1–2
  • The same model can represent haplotype assembly, where sequencing reads with missing entries are covered by one complete center per chromosome copy.Unlike minimum error correction, which minimizes total bit flips, this objective bounds the error rate per read.Source: §1 · p. 2

1.1 Our Contributions

  • The main contribution is a tractability classification across the number of centers k and agreement threshold τ, with a complete picture when strings may contain missing entries.The paper also considers complete strings, where its intractability landscape leaves an unresolved range of thresholds.Source: §1.1 · p. 3
  • The paper’s maximization version seeks k centers covering as many input strings as possible, while approximation algorithms and parameterized complexity are outside its scope.The paper notes that its NP-hardness results carry over to the maximization version and that stronger inapproximability results are available in the Appendix.Source: §1.1 · p. 4

1.2 Discussion and Related Work

  • Hard-threshold maximum covering distinguishes (k,τ)-center from related string-covering and clustering problems.Close to Most Strings is a restricted variant with one center, complete strings, and τ as input; prior work showed no PTAS at τ = 1/2 unless ZPP = NP (Boucher et al., 2013).Source: §1.2 · p. 4
  • Prior delegated-voting work using majority agreement focuses on voting outcomes, whereas this paper focuses on which voters are represented.The cited work’s results imply that high representation need not align with good voting outcomes.Source: §1 · pp. 1–2, §1.2 · p. 4

2 Technical Prerequisites

The section supplies the constraint-satisfaction and coding-theory tools used to establish the paper’s complexity results. CSP dichotomies support hardness arguments, while code-distance bounds support constructions for complete strings.

2 Technical Prerequisites

  • CSP dichotomy theorems establish hardness by encoding each input string as a constraint on the centers.For one center, the reduction uses a binary CSP; for multiple centers, it uses a CSP over {0,1}^k.Source: §2 · p. 5

2.2 Error-Correcting Codes

  • For complete-string hardness, the paper uses codes of large minimum distance to construct instances in which no two clusters can share a center.The section reviews codewords, minimum distance, and classical coding bounds used in these constructions.Source: §2 · p. 5, §2.2 · p. 6

2.1 Constraint Satisfaction Problems

  • A CSP asks whether an assignment to its variables satisfies every constraint in the given constraint language.The section defines constraint languages as sets of relations over a finite domain.Source: §2.1 · p. 5

2.1.1 CSPs over Binary Domain

  • For binary-domain CSPs, Schaefer’s theorem gives tractability when the language has one of six stated polymorphisms; otherwise the problem is NP-complete.The listed polymorphisms are unary constants, AND, OR, majority, and parity.Source: §2.1.1 · p. 5

2.1.2 CSPs over Finite Domains

  • For finite-domain CSPs, the cited dichotomy result implies NP-completeness when a finite constraint language has no Siggers polymorphism.The section presents the Siggers-polymorphism formulation of the general CSP dichotomy.Source: §2.1.2 · pp. 5–6

3 Complexity of (𝑘,𝜏)-center

The section classifies the fixed-parameter decision problem by center count and agreement threshold. Its reductions use binary CSP for one center and CSP over {0,1}^k for multiple centers.

3 Complexity of (𝑘,𝜏)-center

  • For fixed k and τ, the paper classifies (k,τ)-center complexity, reducing single-center cases from binary CSPs and multiple-center cases from CSPs over {0,1}^k.Source: §3 · p. 7

3.1 Single Center

  • For every τ in (0,1), (1,τ)-center is NP-complete, via a polynomial-time reduction from binary CSP.Source: §3.1 · pp. 7–8

3.2 Multiple Centers

  • At τ≤1/2, centers 0^m and 1^m cover all strings; at τ=1, the problem is in P for k≤2 and NP-complete for k≥3.Source: §3.2 · pp. 8–9
  • For multiple centers, the CSP reduction yields hardness even when every input string reveals only a constant number of positions.Source: §3 · p. 7, §3.2 · p. 9

4 Special Case: Complete Strings

This section studies the special case in which every input string is complete and the radius is uniform. It establishes hardness and tractability results for one center, then extends hardness to multiple centers at large thresholds.

4 Special Case: Complete Strings

  • Complete strings make each string constrain all m coordinates, unlike the bounded-arity constraints arising from sparse strings with missing entries.The section examines this setting because the earlier CSP dichotomy arguments do not apply when constraint arity grows with the instance.Source: §4 · p. 10
  • For complete strings, (k,τ)-center is NP-hard for every k when τ∈(5/6,1).The section’s complexity classification is organized by k and τ.Source: Table 3 · p. 10

4.1 Single Center

  • For one center, (1,τ)-center is NP-complete for every τ∈[1/2,1), even with complete strings.The self-contained reduction also yields instances whose string weights barely exceed half the length, a feature used in the multiple-center hardness results.Source: §4.1 · p. 10
  • The weight-restricted single-center instances have length 2m′ and every string has Hamming weight at most m′+4.This restriction supplies the source instances for the multiple-center reduction.Source: §4.1 · p. 10, §4.2 · p. 14
  • For τ<1/2, max-(1,τ)-center with complete strings is solvable in polynomial time.The argument uses random-center coverage and conditional expectations for sufficiently long inputs; short instances are solved by exhaustive search.Source: §4.1 · pp. 12–14

4.2 Multiple Centers

  • For multiple centers, the reduction adds k−1 outliers that cannot share a covering center with each other or with any real string.Thus the outliers consume k−1 centers, leaving one center for the original instance’s real strings.Source: §4.2 · pp. 14, 16
  • The outlier construction uses a code whose minimum-distance-to-length ratio is tight under the Plotkin bound.The construction is used to keep outlier strings far apart.Source: §4.2 · p. 14

5 Discussion and Future Work

The discussion identifies open complexity and approximation questions, alongside parameterized results and directions for exploiting input structure. It also asks how many strings can be covered in worst-case or distributional settings.

5 Discussion and Future Work

  • For complete strings with k≥2, the complexity remains unresolved for thresholds 1/2<τ≤τ*_k.The authors describe resolving this range as technically challenging.Source: §5 · p. 16
  • A constant approximation is achievable when each string has a constant number of non-missing entries, while max-(k,τ)-center is APX-hard.For τ≤1/2 and k=1 without missing entries, the better of a center and its complement gives a 2-approximation; improvement or a constant approximation for τ>1/2 remains elusive.Source: §5 · p. 16
  • When either m or n is constant, the problem is solvable in polynomial time; hardness persists with only a small constant number of missing entries per string.For constant m, the approach is enumeration; for constant n, it uses an ILP or dynamic programming.Source: §5 · p. 16
  • The appendix adapts an FPT algorithm parameterized by the incidence graph’s vertex cover number, while further positive results from structural restrictions remain a direction for future work.The adaptation is attributed to Friedrich et al. (2025).Source: §5 · p. 17
  • For large thresholds, worst-case instances can limit any constant-size center set to covering only a constant number of strings; the authors propose studying inputs drawn from distributions.The discussion frames this as an information-theoretic question about feasible coverage.Source: §5 · p. 17

A Instances with Few Coverable Strings

Coding-theoretic constructions show that at thresholds above 1/2, instances can have exponentially many complete strings while each center—or set of k centers—covers only a bounded number. For thresholds above 3/4, the bounds sharpen to one string per center.

A Instances with Few Coverable Strings

  • For any τ>1/2, some instances of max-(k,τ)-center have exponentially many strings while any one center covers at most a τ-dependent constant.The bound is independent of input size.Source: A Instances with Few Coverable Strings · p. 20
  • For τ>3/4, a complete-string max-(1,τ)-center instance can contain 2^Θ(m) strings while no center covers more than one.The construction uses codewords with minimum distance 2d_max+1, so a radius-d_max ball contains at most one codeword.Source: A Instances with Few Coverable Strings · pp. 20–21
  • For any τ>1/2, there are instances with exponentially many complete strings in which no k centers cover more than O(k) strings.The stated bound is 2k/ε^2 when ε=2τ−1, for m≥8/ε^2.Source: A Instances with Few Coverable Strings · p. 21
  • For τ>3/4 and sufficiently large m, instances can be constructed in which no k centers cover more than k strings.The condition given is m≥4/(2ε−1).Source: A Instances with Few Coverable Strings · p. 21

B Small Instances

The paper gives algorithms for small instances: a decision algorithm based on partitioning strings into clusters, and a dynamic program that also handles the maximization variant. Their stated runtimes depend differently on the number of strings and the string length.

B Small Instances

  • (k,τ)-center admits an algorithm with runtime n^O(n^2)O(log m).It enumerates partitions into k clusters and solves a separate (1,τ)-center instance for each cluster.Source: B Small Instances · p. 21
  • An elementary dynamic program offers a self-contained alternative that avoids the integer-programming machinery and extends directly to maximization, at the cost of worse dependence on m.The text presents this as an alternative for the case of a constant number of input strings.Source: B Small Instances · p. 22
  • max-(k,τ)-center admits an algorithm with runtime m^O(n).The dynamic program tracks feasible distance matrices across string positions and can recover centers by backtracking.Source: B Small Instances · p. 22

C Instances with Small Vertex Cover Number

The appendix adapts a vertex-cover-parameterized FPT algorithm to the missing-entry setting by using per-string distance limits. It also explains why analogous adaptations for treewidth and fracture number are less immediate.

C Instances with Small Vertex Cover Number

  • The adapted algorithm is FPT parameterized by the incidence graph’s vertex cover number, with runtime 2^O(vc(G)^2 log vc(G))poly(nm) for constant k.It replaces a shared radius with each string’s bound d_i=⌊(1−τ)m_i⌋.Source: C Instances with Small Vertex Cover… · pp. 22–23
  • The algorithm separates long strings, which meet the vertex cover’s string vertices, from short strings whose known entries lie only in the covered positions.It enumerates assignments for long strings and center values on the covered positions, then tests whether each cluster admits a center.Source: C Instances with Small Vertex Cover… · pp. 23–24
  • For each cluster, the center-feasibility test is a Non-uniform Closest String instance on the covered positions; short strings can be assigned independently when within their radius.The appendix identifies the test as NUCS.Source: C Instances with Small Vertex Cover… · p. 24
  • Treewidth adaptation is complicated by radii proportional to m_i, while the fracture-number approach loses its case where short strings are covered by every center for free.The authors identify fracture-number FPT as a direction of particular interest for delegated voting.Source: C Instances with Small Vertex Cover… · p. 24

D Hardness of Approximation

The section establishes constant-factor approximability for M-sparse instances and APX-hardness even within that restricted class. It derives these results by applying a MAX-CSP dichotomy and reductions between covered strings and satisfied constraints.

D Hardness of Approximation

  • The classification applies Khanna et al.’s MAX-CSP dichotomy, which distinguishes languages by 2-monotonicity.The section uses it to establish approximation for restricted instances and APX-hardness in general.Source: D Hardness of Approximation · pp. 24–25
  • For every τ∈(0,1) and positive integer M, max-(1,τ)-center on M-sparse instances is in APX.A MAX-CSP approximation yields a center that approximates the maximum number of strings covered by one center.Source: D Hardness of Approximation · p. 25
  • For M≥1/min(τ,1−τ), the constraint language Γ_{τ,M} yields an APX-complete MAX-CSP problem.The hardness argument shows the language is not 2-monotone, invoking the MAX-CSP dichotomy.Source: D Hardness of Approximation · p. 25
  • For every τ∈(0,1), max-(1,τ)-center is APX-hard on M-sparse instances for constant M=⌈1/min(τ,1−τ)⌉.Therefore, it is APX-hard on unrestricted instances as well.Source: D Hardness of Approximation · p. 26
  • The reduction from MAX-CSP preserves objective value exactly by matching satisfied constraints to covered strings.The constructed instances have every string revealing exactly M positions.Source: D Hardness of Approximation · p. 26
Loading 2609.35386v1…