An Optimal Algorithm for Binary Closest String

Nick Fischer, Mursalin Habib · 2026

Read An Optimal Algorithm for Binary Closest String by Nick Fischer, Mursalin Habib (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-31417.txt.

Introduction

Fischer and Habib revisit the Binary Closest String problem: given a set of binary strings, find a string cutting the maximum Hamming distance to the set. Prior tuned algorithms for the optimal distance improved from base d down through bases 16, 10, 8 and 7 to the best-known base 5. The authors present a faster chance-based algorithm with base 4. Their result meets a recent fine-grained lower bound and is therefore optimal on current proofs. As an extra benefit, the algorithm is very simple.

Catalog record

CREATORNick Fischer, Mursalin Habib
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13553
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.31417

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Optimal Algorithm for Binary Closest String Nick Fischer, Mursalin Habib Abstract We revisit the Binary Closest String problem, which asks, given a set of binary strings X ⊆ { 0 , 1 } n X\subseteq\{0,1\}^{n} , to compute a string minimizing the maximum Hamming distance to X X . A long line of work has focused on parameterized algorithms with respect to the optimal distance d d , yielding a sequence of improvements from O ∗ ​ ( d d ) O^{*}(d^{d}) through O ∗ ​ ( 16 d ) O^{*}(16^{d}) , O ∗ ​ ( 9.513 d ) O^{*}(9.513^{d}) , O ∗ ​ ( 8 d ) O^{*}(8^{d}) , O ∗ ​ ( 6.731 d ) O^{*}(6.731^{d}) to the current best-known running time of O ∗ ​ ( 5 d ) O^{*}(5^{d}) [Chen, Ma, Wang; Algorithmica ’16]. We present a faster randomized algorithm running in time O ∗ ​ ( 4 d ) O^{*}(4^{d}) . Our result matches a recent fine-grained lower bound [Abboud, Fischer, Goldenberg, Karthik C.S., Safier; ESA ’23], and is therefore conditionally optimal . As an extra benefit, our algorithm is remarkably simple. Max Planck Institute for Informatics, Saarbrücken, [email protected]://orcid.org/0009-0001-0909-3296 Rutgers University, New Brunswick, NJ, [email protected]://orcid.org/0000-0002-6671-4669Supported by the National Science Foundation under Grants CCF-2313372, CCF-2422558, and CCF-2443697. We are very grateful to Karthik C.S. for fruitful discussions at an early stage of this project. {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010052¡/concept_id¿ ¡concept_desc¿Theory of computation Parameterized complexity and exact algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Parameterized complexity and exact algorithms keywords Closest String, Parameterized Complexity, Fine-Grained Complexity † † runningauthor: N. Fischer and M. Habib † † funding: Part of this work was done while visiting INSAIT at Sofia University “St. Kliment Ohridski” and funded by the Bulgarian Ministry of Education and Science through its support of INSAIT under the Bulgarian National Roadmap for Research Infrastructure. 1 Introduction The Closest String problem asks, given a set of strings X\subseteq\Sigma^{n} , to find a string y^{*}\in\Sigma^{n} that minimizes the maximum Hamming distance to the strings in X . It constitutes one of the most fundamental clustering tasks on strings, and is also of great importance in bioinformatics, for instance in the computer-aided design of universal PCR primers [ 12 ] , motif finding [ 10 ] , and drug design [ 7 ] . The Closest String problem is extremely well-studied, from both the theory and applied computational biology communities. It is known to be NP-hard [ 8 , 12 ] (even for binary strings), and well-understood through the lens of approximation [ 3 , 9 , 12 , 13 , 2 , 14 ] . Here we focus on the parameterized setting, where the goal is to design algorithms whose running time depends on the optimal distance d . This setting has concrete practical relevance, as for the aforementioned biology applications d is typically very small. Over the past two decades, a long sequence of papers has developed progressively faster parameterized algorithms [ 11 , 14 , 6 , 16 , 17 , 4 , 5 ] . And yet, despite this sustained effort, it remained open to pinpoint the precise complexity of Closest String—even in the most basic regime of binary strings (i.e., for |\Sigma|=2 ). Concretely, the first parameterized algorithm was given by Gramm, Niedermeier, and Rossmanith [ 11 ] and runs in time 1 1 1 Here and throughout, the O^{*}(\cdot) notation hides polynomial factors in the input size, \poly(|X|,n) . O^{*}(d^{d}) . The subsequent milestones for Binary Closest String are algorithms in time O^{*}(16^{d}) [ 14 ] , O^{*}(9.513^{d}) [ 16 ] , O^{*}(8^{d}) [ 17 ] , O^{*}(6.731^{d}) [ 4 ] , before culminating in the current state-of-the-art O^{*}(5^{d}) due to Chen, Ma, and Wang [ 5 ] . On the converse side, a recent lower bound construction due to Abboud, Fischer, Goldenberg, Karthik C.S., and Safier [ 1 ] implies that there is no O^{*}((4-\epsilon)^{d}) -time algorithm for Binary Closest String, for any constant \epsilon>0 , unless the Strong Exponential-Time Hypothesis (SETH) from fine-grained complexity fails. 2 2 2 In detail: Abboud, Fischer, Goldenberg, Karthik C.S., and Safier [ 1 ] show that Binary Closest String cannot be solved in time O^{*}((2-\epsilon)^{n}) . Inspecting their lower bound reveals that it applies to instances with d=(1/2\pm o(1))n , implying that Binary Closest String cannot be solved in time O^{*}((4-\epsilon)^{d}) in the regime where d=(1/2\pm o(1))n . A simple padding argument extends this lower bound to the full range d\leq n/2 . For d>n/2 the brute-force O^{*}(2^{n}) -time algorithm becomes more efficient. This leaves an exponential gap between the 5^{d} upper bound and the 4^{d} lower bound. In this paper we finally close this gap, and thereby resolve the parameterized complexity of Binary Closest String: Theorem 1 . Binary Closest String can be solved in randomized time O^{*}(4^{d}) . Notably, our algorithm is not only conditionally optimal, but also pleasingly simple . It can be stated in 6 lines of pseudocode (see \cref alg:main), and is also conceptually simple. In fact, our algorithm is almost identical to a simple local search algorithm by Chen, Ma, and Wang [ 5 ] that runs in time O^{*}((2e)^{d})=O^{*}(5.437^{d}) (from same paper that established the previous state of the art). We propose a technical yet important nuance: instead of running O^{*}((2e)^{d}) independent local searches of length O(d) , we run one local search of length O^{*}(4^{d}) . Our analysis is based on Markov chains and conceptually inspired by Schöning’s seminal algorithm [ 15 ] for k -SAT. The specific Markov chain turns out to be more complicated than in Schöning’s algorithm, but viewed the right way its analysis does not take more than a page. To conclude, while our new algorithm will perhaps not have immediate practical impact, it does constitute the first optimal result in a long line of work [ 11 , 14 , 6 , 16 , 17 , 4 , 5 ] . For this reason we are confident that it may form the baseline to make progress on more general variants, e.g., for larger alphabets or for the strictly more general and even more practically important Closest Substring problem. 2 Formal Definitions The Hamming distance of two strings x,y\in\Sigma^{n} is defined as \HD(x,y)=|\{j:x[j]\neq y[j]\}| . The Closest String problem is, given a set X\subseteq\Sigma^{n} , to find a string y^{*} that minimizes \max_{x\in X}\HD(x,y^{*}) . We define the parameter d=\max_{x\in X}\HD(x,y^{*}) as the optimal distance. The Binary Closest String problem is the restriction to alphabets of size |\Sigma|=2 . 3 Algorithm This section is devoted to the proof of \cref thm:main. Throughout, to solve the Closest String problem, we assume that as part of the input we are given a parameter 1\leq d<n and the goal is to decide if there is a center string y^{*}\in\{0,1\}^{n} within distance \max_{x\in X}\HD(x,y)\leq d . The optimal d can then be identified by testing d\leftarrow 1,2,\dots one by one; the overhead of this search is only a constant factor in our final O^{*}(4^{d}) -time algorithm. Algorithm 1 The O^{*}(4^{d}) -time algorithm for Binary Closest String 1: A set of strings X\subseteq\{0,1\}^{n} and an integer d\geq 0 2: A string y^{*}\in\{0,1\}^{n} with \max_{x\in X}\HD(x,y^{*})\leq d (if

Read the complete text