Collapsing Superstring Conjecture.

摘要: In the Shortest Common Superstring (SCS) problem, one is given a collection of strings, and needs to find shortest string containing each them as substring. SCS admits $2\frac{11}{23}$-approximation in polynomial time (Mucha, SODA'13). While this algorithm its analysis are technically involved, 30 years old Greedy Conjecture claims that trivial efficient Algorithm gives 2-approximation for SCS. We develop graph-theoretic framework studying approximation algorithms The reminiscent classical Traveling Salesman: take two copies an optimal solution, apply edge-collapsing procedure, get approximate solution. framework, we observe surprising properties solutions, conjecture they hold all input instances. first conjecture, call Collapsing there elementary way transform any solution repeated twice into same graph $G$. This would give 2-approximate second not only resulting $G$ but can be computed by greedy procedure called Hierarchical Algorithm. While clearly implies one, perhaps surprisingly prove their equivalence. We support these equivalent conjectures giving proof special case where strings have length at most 3. standard Conjecture, while latter sufficient Except (conjectured) good ratio, provably finds 3.5-approximation.