Source-linked AI summary
Disproving the Greedy Superstring Conjecture
Hiroki Shibata
TL;DR
The shortest common superstring problem asks for a minimum-length string containing all inputs, and the greedy algorithm’s conjectured 2-approximation guarantee had remained unresolved. This paper constructs equal-length instances and analyzes optimal and greedy solutions, showing that the conjecture is false and that the greedy algorithm’s approximation ratio is at least 9/4.
Problem
SCS seeks a minimum-length string containing every input string, but the best possible approximation ratio remains unknown despite extensive approximation research.
Method
The paper constructs equal-length instances with controlled circular-substring overlaps and compares an optimal solution with a greedy output.
Results
9/4 is the lower bound established for the greedy algorithm’s approximation ratio on unrestricted SCS instances.
Takeaways & Limitations
The greedy superstring conjecture is false, including for instances whose input strings all have the same even length k ≥10.
Takeaways & Limitations
The greedy algorithm may produce multiple outputs because ties among maximum-overlap pairs can be resolved differently.
Abstract
from arXiv · showhide
The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a $2$-approximation algorithm, and this conjecture had remained open for nearly four decades. In this paper, we disprove this conjecture and show that the approximation ratio of this algorithm is at least $9/4$.
1 Introduction
The shortest common superstring problem seeks a minimum-length string containing every input string, and its approximation landscape remains unresolved despite extensive study. This paper disproves the conjecture that the greedy algorithm is always a 2-approximation, showing a lower bound of 9/4.
- Problem and context: SCS asks for a minimum-length string containing every input string as a substring and is NP-hard and APX-hard over binary alphabets.These difficulties have motivated approximation algorithms and heuristics.
- Greedy algorithm: The greedy algorithm repeatedly merges a pair of strings with maximum overlap, where overlap is a suffix-prefix match, and runs in linear time.Despite reported practical performance, its exact approximation ratio was unknown.
- Prior conjecture: The greedy algorithm has approximation ratio at least 2, motivating the conjecture that it always achieves a 2-approximation.A tie-breaking choice on a specific input family yields ratios approaching 2.
- Prior results: Prior work established the conjecture for length-4 inputs and a lower bound of 2 for length-6 inputs, while the general ratio gap remained open.Related variants and both upper- and lower-bound results had been studied extensively.
- Contribution: The paper disproves the greedy superstring conjecture by constructing lower bounds for instances whose strings all have the same even length k ≥10.The contribution targets the approximation ratio ρ_k for k-SCS instances.
- Main result: 9/4 is the resulting lower bound on the greedy algorithm’s approximation ratio for unrestricted SCS instances.The bound follows by taking k →∞ from the even-length construction.
2 Preliminaries
The preliminaries define overlaps, merging, circular substrings, and the greedy process, then establish that maximum overlap length is monotone during greedy execution. They also specify the equal-length k-SCS setting.
- String operations: Circular substrings are fixed-length substrings of an infinite periodic repetition, enabling consecutive cyclic windows to be analyzed as strings.The notation CSubstrℓ(T, i) denotes the window of length ℓ starting at position i in T∞.
- String operations: An overlap from X to Y is a suffix of X that is also a prefix of Y; X⊙Y merges the strings using their longest overlap.The merge is the shortest string having X as prefix and Y as suffix.
- Circular-substring lemmas: Consecutive circular substrings of a non-unary string have overlap length ℓ−1, and merging n such windows in order yields a longer circular substring with a border.The condition ℓ≥n prevents a full-length overlap unless the source string is unary.
- Problem variant: In SCS, strings contained in other input strings may be removed without changing the optimum, so the analysis assumes no input string contains another.The k-SCS variant restricts every input string to length k.
- Greedy algorithm: The greedy algorithm recursively selects any ordered pair attaining maxov(S), merges it, and repeats until one string remains.Multiple maximizing pairs can produce multiple outputs, collected in GREEDY(S).
- Monotonicity: For inputs without substring containment, one greedy merge preserves that property and cannot increase the maximum overlap length.The proof compares overlaps involving the merged string with overlaps involving its constituents.
- Monotonicity: Maximum overlap length is nonincreasing across every sequence of greedy steps while at least two strings remain.This is obtained by repeatedly applying the one-step lemma.
3 Construction and Proof Outline
The construction creates equal-length circular-substring instances with carefully controlled shared substrings. Its proof outline contrasts an Eulerian-circuit optimum with greedy merges whose border restrictions force shorter later overlaps and a longer output.
- Construction: For every even k=2s≥10, the construction defines strings U_i, V_i, and W_i over an alphabet containing x, y, a, and unique symbols b_i.The input consists of circular substrings generated from these base strings.
- Construction: The input set S_k,t contains k circular substrings from each U_i, s from each V_i, and s+2 from each W_i.All listed strings have length k.
- Distinctness: The construction’s strings are pairwise distinct because their unique b_i symbols identify the index, while within-index positions distinguish the circular substrings.Additional occurrence patterns separate the U, V, and W families.
- Proof outline: All length-k circular substrings share selected length-(k−1) circular substrings, allowing the order-k−1 de Bruijn graph to have an Eulerian circuit.That circuit is used to construct an optimal common superstring.
- Greedy lower bound: The lower-bound execution first merges each family’s circular substrings into 3t strings corresponding to U_i, V_i, and W_i.Each resulting string is a longer circular substring with a length-(k−1) border.
- Greedy lower bound: Careful choices of first circular substrings restrict which borders can overlap substantially, forcing shorter overlaps in the remaining merges and producing a long output.These restrictions are the central mechanism of the lower-bound construction.
4 Optimal Value of the Instance
The paper determines the instance’s optimal superstring length by matching a counting lower bound with an Eulerian-circuit construction in a de Bruijn graph. The resulting exact value is OPT(Sk,t) = t(4s + 2) + k −1.
- Lower bound: The distinct length-k input strings imply OPT(Sk,t) ≥ t(4s + 2) + k −1.A superstring of length |T| contains at most |T|−k+1 distinct length-k substrings, while Sk,t has t(4s + 2) distinct strings.
- Graph construction: The de Bruijn graph G uses length-(k−1) substrings as vertices and length-k input strings as directed labeled edges.Edges connect each string’s length-(k−1) prefix to its length-(k−1) suffix, and the input strings form directed circuits associated with Ui, Vi, and Wi.
- Eulerian circuit: Shared vertices αi, βi, and γ connect the directed circuits, making G strongly connected while preserving equal indegree and outdegree at every vertex.αi connects CUi with CVi, βi connects CUi with CWi, and γ connects the circuits CUi across indices.
- Upper bound: An Eulerian circuit of G yields a common superstring containing every input string as a length-k window, with length at most t(4s + 2) + k −1.Each graph edge corresponds to one input string, and traversing all edges produces the required superstring.
- Exact optimum: Therefore, the exact optimum is OPT(Sk,t) = t(4s + 2) + k −1.The matching lower and upper bounds establish equality.
5 Lower Bound on the Approximation Ratio
The lower-bound construction engineers strings and merge sequences that remain valid choices for the greedy algorithm, producing a long greedy output. Its length yields an approximation-ratio lower bound approaching 9/4.
- Construction: The construction forms each ˆUi, ˆVi, and ˆWi by prescribed left-to-right merges whose overlaps have length k−1.Their lengths are 4s−1, 3s−1, and 3s+1, respectively, for even k=2s≥10.
- Overlap analysis: Maximum overlaps among the constructed strings can be determined from their length-(k−1) borders.The border reduction follows because overlaps cannot reach length k for distinct underlying strings.
- Greedy sequence: The procedure merges each ˆVi with ˆUi using overlap s−3, then merges the resulting Mi strings using overlap 1.At each stage, the selected overlap equals the current maximum, so the operations satisfy the greedy selection rule.
- Output length: The final merges with the ˆWi strings have overlap 0, after which the greedy output has length |T′|=t(9s+1)+1.The zero-overlap phase also satisfies the greedy selection rule because no positive overlap remains.
- Approximation ratio: The resulting construction gives an approximation-ratio lower bound of 9/4−7/(4k+4) for even k, and therefore at least 9/4 in general.Taking the limit over even k produces the unrestricted SCS lower bound.
AI Usage Disclosure
The paper discloses use of OpenAI’s GPT-5.6 Sol for discovery, technical drafting, proofreading, and organization, with the author verifying the claims and proofs.
- AI Usage Disclosure: The author used GPT-5.6 Sol to help discover and simplify proof strategies and to assist with technical writing.The disclosed uses include drafting technical text, correcting typographical errors, and improving manuscript organization.
- AI Usage Disclosure: The author states that all claims and proofs were verified and takes full responsibility for the paper.