Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.
OAI-26 family 128: factor-two shortest-common-superstring approximation
Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This source-pinned documentary record reports the publisher's claimed theorem; it does not independently verify the algorithm.
The question in plain language
Given several strings, find the shortest single string containing every input as a contiguous substring. The shortest common superstring problem rewards reuse of overlapping prefixes and suffixes, but selecting overlaps globally can be difficult.
Family 128 claims a deterministic polynomial-time algorithm producing a superstring no longer than twice the optimum.
A small example
The strings ABCD and CDEF can be combined into ABCDEF, reusing their common CD overlap. Simply concatenating the inputs instead would require eight characters rather than six. When many strings are involved, optimizing one local overlap may prevent a better global arrangement.
If the minimum feasible length is \(L^\ast\), a factor-two approximation promises a constructed string \(S\) with \(|S|\le 2L^\ast\). The output must contain each input as a contiguous substring, not merely as a subsequence.
What is known
The protected Family 128 catalogue identifies one manuscript, A Polynomial-Time 2-Approximation for Shortest Common Superstring.
The pinned publisher overview claims that for every finite family of explicitly represented strings, a deterministic polynomial-time algorithm constructs a common superstring satisfying
where \(\mathrm{OPT}(\mathcal F)\) is the least achievable superstring length.
The overview specifies running time polynomial in the full encoded input length, including symbol labels. This qualification matters when the alphabet is variable; symbol operations cannot be treated as free without accounting for their encoding.
The claimed result is an approximation upper bound, not proof that factor two is optimal or an exact polynomial-time algorithm.
GCL verification state
Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The protected catalogue identifies the manuscript, and the pinned overview specifies the approximation factor, determinism and encoded-input complexity.
This documentary pass has not checked the algorithm, approximation proof, preprocessing of contained strings, duplicate handling, or bit-complexity analysis. No Family 128-specific critical proof audit, Comparator result, Lean elaboration, or MATHCERT certificate is asserted.
What remains
Read the pinned PDF and extract the exact algorithm and approximation theorem. Reconstruct the overlap, ordering and cycle/path arguments, and check that every input string occurs contiguously in the output. Use small exhaustive examples to test the claimed length inequality, including nested strings and ambiguous overlaps.
Audit deterministic implementation and complexity with variable alphabets and encoded symbol labels. Check duplicate, empty and contained strings, and any exceptional assumptions about the input family.
Complete mathematical Markdown/MkDocs regression, source-critical editorial review and protected merge/readback. Editorial admission does not certify the algorithm.
Sources and claim boundaries
Boundary: NO_CERTIFICATION. The factor-two approximation remains a publisher-reported claim awaiting independent proof verification.
Indexed primary manuscript paths:
- A Polynomial-Time 2-Approximation for Shortest Common Superstring —
preprints/A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026/paper.pdf