Source-linked AI summary
A Tight Cycle-Cover Inequality for Shortest Common Superstring
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal
TL;DR
SCS and its maximum-overlap greedy algorithm have approximation guarantees the paper aims to improve. The authors analyze a cycle-cover inequality and establish a sharp coefficient, yielding a 7/3 approximation for SCS and a guarantee of at most 3 for greedy.
Problem
Prior improvements to SCS and greedy guarantees were driven by a cycle-cover inequality whose coefficient remained a central target for improvement.
Source: §1.2 · p. 2Method
The authors analyze minimum-cost cycle covers in the associated overlap graph using global graph properties rather than treating each optimum-cover cycle separately.
Source: §1.2 · p. 2, §2.2 · p. 3Results
SCS admits a 7/3 approximation, the greedy algorithm’s approximation guarantee is at most 3, and the cycle-cover inequality holds for γ=1.
Source: §1.1 · p. 1, §1.2 · p. 2Takeaways & Limitations
γ=1 is the optimal endpoint of this approach, because every γ<1 fails.
Source: §1.2 · p. 2, §3 · p. 5
Abstract
from arXiv · showhide
In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Its best known approximation ratio is $2.466$, whereas the currently strongest upper bound on the approximation guarantee of the maximum-overlap greedy algorithm is $3.396$ (Englert, Matsakis, and Vesel{ý}, 2023), though it is conjectured to be $2$. We improve both approximation guarantees: SCS admits a $\frac{7}{3}$ approximation and the approximation guarantee of the greedy algorithm is at most $3$. The main technical ingredient of our proof is a certain inequality for minimum-cost cycle covers of an overlap graph associated with the input strings. Every previous improvement of greedy's worst-case guarantee and the two recent record guarantees for general SCS are driven by it. We improve this inequality by pushing it to its limit: for a particular coefficient of this inequality, we show a new upper bound and prove that it cannot be improved further.
1 Approximating Shortest Common Superstring
The paper improves approximation guarantees for SCS and its maximum-overlap greedy algorithm, and identifies the sharp coefficient behind these bounds.
1 Approximating Shortest Common Superstring
- SCS seeks a shortest string containing every input as a substring; its best known ratio is 2.466, while greedy’s best upper bound is 3.396, despite a conjectured ratio of 2.Source: §1 · p. 1
1.1 Our Contribution
- SCS admits a 7/3 approximation, and the greedy algorithm’s approximation guarantee is at most 3.Source: §1.1 · p. 1
1.2 Common Coefficient
- The cycle-cover inequality holds at γ=1, the optimal endpoint, and every γ<1 fails.The paper says its proof uses global overlap-graph properties rather than analyzing each optimum-cover cycle separately.Source: §1.2 · p. 2
2 Overlap Graph and the Cycle-Cover Inequality
The preliminaries define SCS and overlap-based merging; the overlap graph turns strings into a directed graph whose edge costs support cycle-cover bounds. The section motivates breaking an optimal cycle cover into paths and describes how substring counts yield a cycle-cover inequality.
2.1 Preliminaries
- SCS seeks a shortest string containing every input string as a substring, and GREEDY repeatedly merges the pair with maximum overlap.The overlap merge appends to the first string the part of the second string beyond their matching suffix-prefix overlap.Source: §2.1 · pp. 2–3
2.2 Overlap Graph
- The overlap graph is a complete directed graph with self-loops; its edges carry overlap weights and prefix-distance costs, so minimizing cycle-cover cost is equivalent to maximizing total overlap.A directed cycle cover is a permutation of the vertices, viewed as vertex-disjoint directed cycles.Source: §2.2 · p. 3
- An optimal cycle cover has total prefix-distance cost at most OPT(S); breaking its cycles into paths and joining them motivates constructing a common superstring.Breaking a cycle produces a corresponding string whose length is the cycle cost plus the weight of the removed edge.Source: §2.2 · p. 3
- A cycle-cover coefficient γ gives a greedy approximation bound of 2 + γ and, with a δ-approximation for Max-ATSP, an SCS bound of 2 + (1 − δ)γ.The section uses this connection to motivate improving the cycle-cover inequality.Source: §2.2 · p. 4
- Earlier coefficient improvements classified cycles by o(c)/w(c); [EMV22] combined bounds for different cycle balances, while strengthened an edge-swap argument on the original cover.A similar result was previously known in a related form.Source: §2.2 · p. 4
- For a fixed common superstring, counting substrings by length bounds how many cycles can satisfy each length condition; summing these bounds yields the desired inequality.The proof uses the telescoping relationship between the numbers of length-m and length-(m−1) substrings.Source: §2.2 · p. 4
3 Optimal Bound on the Cycle-Cover Inequality
The section proves that the optimal coefficient in the cycle-cover inequality is γ = 1, then shows that every smaller coefficient fails. Its upper-bound proof uses cycle-string structure and substring counting, while its lower bound uses a family of binary strings.
3 Optimal Bound on the Cycle-Cover Inequality
- γ = 1 is the smallest coefficient for which the cycle-cover inequality holds; every γ < 1 fails for some instance.The lower-bound construction establishes failure for every fixed γ < 1 once its parameter is sufficiently large.Source: §3 · p. 5, §3.1 · p. 5, §3.2 · pp. 6–7
3.1 Upper Bound
- The upper-bound proof uses distinct Lyndon representatives of cycle strings and a connected substring graph to count deletions.It orders selected length-m substrings and shows their deletion preserves connectivity, yielding the needed counting bound.Source: §3.1 · pp. 5–6
3.2 Lower Bound
- For S_m = {s_2, …, s_m}, the all-self-loop cycle cover is minimum-cost, W = Θ(m^2), and O − OPT(S_m) > γW for every fixed γ < 1 when m is sufficiently large.The construction uses binary strings whose pairwise substring and overlap properties support the minimum-cost all-self-loop cover.Source: §3.2 · p. 7
AI disclosure
The authors describe using language models to explore proofs and perform mechanical work, while stating that they wrote the arguments themselves and take responsibility for the manuscript.
AI disclosure
- ChatGPT suggested a simpler route to an inequality proof while the authors were exploring a self-reduction for SCS.The suggestion was not directly related to the question under discussion, and the authors later simplified the initial proof together with the agent.Source: AI disclosure · p. 7
- The authors used ChatGPT for mechanical work constructing the example in Theorem 3.5.Source: AI disclosure · p. 7
- The authors used Codex to find typos and state that they wrote all arguments themselves and assume full responsibility for the manuscript.Source: AI disclosure · p. 7