Complexity of Maximizing Hamming Distances Below a Threshold

Question

Problem Statement

Is the following problem NP-Complete?

Input: A collection $S$ of binary strings, with each string of length $m$.

Goal: Compute a binary string $s^*$ of length $m$ that mazimizes the number of strings $s \in S$ for which the Hamming Distance is at most $d_H(s, s^*) < \frac{m}{2}$.

---

Additional Information and Background

This feels like a covering problem. However, I don't see any simple (Karp) reduction to Set Cover, Set Multicover, or Hypergraph Vertex Cover.

If the upperbound on the Hamming Distance to each string in $S$ were a constant $d_H(s, s^*) < c$, thereby removing the dependence on $m$, then the problem becomes LOGSNP. At the same time, if the bound is $d_H(s, s^*) < m-c$ for $c$ constant, then it is still LOGSNP. However, once the bound becomes $d_H(s, s^*) < m * c$ for some constant $0 < c < 1$, I suspect it is NP-Hard.

Motivation

The original motivation for the problem comes from a simple voting problem. Suppose each voter has a binary preference over each issue in a set of binary issues. The voters are going to elect a representative using approval voting. A voter only approves of a candidate if they agree on more than half the issues. If a candidate wants to pander to the voters, and lie about their preferences on the issues to get elected, what preference vector should they report to maximize the number of approvals they receive?

Equivalent Problem Statements

Given a set of points $S$ on the unit hypercube of dimension d, find the point $x$ on the unit hypercube that maximizes the number of points in $S$ within the ball of radius $\lfloor\frac{d-1}{2}\rfloor$ around $x$.

Answer 1

Lemma 1. The problem is NP-hard, by reduction from Max-2-SAT.

Proof sketch. The reduction is in two steps. Consider the variant of the problem in which $d$ is even and the coverage requirement is loosened so that $s^*$ covers a string $s$ iff it differs with $s$ on at most half the bits (that is, Hamming distance is at most $d/2$, instead of $d/2-1$). Reduce this variant to the original problem as follows: given an instance of this problem, replace each of the given strings $s$ by $s\,1$ (that is, append a 1).

To cover the resulting set of strings, we may as well use a covering string of the form $s^*1$ (ending in a 1). Each string string $s\,1$ in the reduced instance is then covered by $s^*1$ if and only $s$ and $s^*$ agree on at least half the bits. So optimal solutions to the reduced instance correspond to optimal solutions to the original instance.

To complete the proof we describe a reduction from 2-SAT to the above variant. Given a 2-SAT formula $\phi$ with $n$ variables and $m$ clauses, assume without loss of generality that $n=2^k$ is a power of two (if not, make it so by adding at most $m$ dummy variables not included in any clause).

First, introduce $m$ copies of each of the following strings: $0^{2n}$, and its complement $1^{2n}$, and, for each $j\in \{2^i : 0\le i < k\}$, the two strings $(0^j1^j)^{n/j}$ and its complement $(1^j0^j)^{n/j}$.

To cover both a string and its complement simultaneously, a candidate answer $s^*$ has to agree with each at exactly half the coordinates.

Claim. A candidate solution $s^*$ will cover all of the strings introduced so far if and only if it has the form $\{01, 10\}^n$ (that is, consists of a sequence of pairs, where each pair contains one 0 and one 1).

Here's why. To cover the all-zero and all-one strings, $s^*$ has to consist of half zeros and half ones. Then, to cover the $0^n1^n$ and its complement $1^n 0^n$, it has to (also) have exactly $n/2$ zeros in its first half, and $n/2$ zeros in its second half. Then, to cover the $(0^{n/2}1^{n/2})^2$ and its complement, it has to have exactly $n/4$ zeros in each of its four quarters, and so on. This is why the claim holds.

Now, there is a natural bijection between the strings of that form, that is, $s^* \in \{01, 10\}^n$, and the assignments to the variables of $\phi$. Namely, the assignment of the $i$th variable $x_i$ is encoded in the $i$th pair in $s^*$ by encoding True as the pair 01, and False as the pair 10.

With this in mind, for each clause $C$ in $\phi$, let $x_i$ and $x_j$ be the variables in $C$, then introduce a string $s_C$ in which every pair is 00, except the $i$th and $j$th pairs, which are determined as follows. If $x_i$ occurs positively in $C$, make the $i$th pair $01$, otherwise ($x_i$ occurs negatively in $C$) make the $i$th pair $10$. Likewise for $x_j$ and the $j$th pair in $s_C$.

Given that $s^*\in \{01, 10\}^n$, it will cover $s_C$ if and only if $s^*$ agrees with $s_C$ in the $i$th pair and/or the $j$th pair. That is, if and only if the corresponding assignment satisfies $C$. Thus, maximizing the number of satisfied clauses corresponds to maximizing the number of strings covered by $s^*$. $~~~~\Box$