Golovnev, Alexander ;
Kulikov, Alexander S. ;
Logunov, Alexander ;
Mihajlin, Ivan ;
Nikolaev, Maksim
Collapsing Superstring Conjecture
Abstract
In the Shortest Common Superstring (SCS) problem, one is given a collection of strings, and needs to find a shortest string containing each of them as a substring. SCS admits 2 11/23approximation in polynomial time (Mucha, SODA'13). While this algorithm and its analysis are technically involved, the 30 years old Greedy Conjecture claims that the trivial and efficient Greedy Algorithm gives a 2approximation for SCS.
We develop a graphtheoretic framework for studying approximation algorithms for SCS. The framework is reminiscent of the classical 2approximation for Traveling Salesman: take two copies of an optimal solution, apply a trivial edgecollapsing procedure, and get an approximate solution. In this framework, we observe two surprising properties of SCS solutions, and we conjecture that they hold for all input instances. The first conjecture, that we call Collapsing Superstring conjecture, claims that there is an elementary way to transform any solution repeated twice into the same graph G. This conjecture would give an elementary 2approximate algorithm for SCS. The second conjecture claims that not only the resulting graph G is the same for all solutions, but that G can be computed by an elementary greedy procedure called Greedy Hierarchical Algorithm.
While the second conjecture clearly implies the first one, perhaps surprisingly we prove their equivalence. We support these equivalent conjectures by giving a proof for the special case where all input strings have length at most 3 (which until recently had been the only case where the Greedy Conjecture was proven). We also tested our conjectures on millions of instances of SCS.
We prove that the standard Greedy Conjecture implies Greedy Hierarchical Conjecture, while the latter is sufficient for an efficient greedy 2approximate approximation of SCS. Except for its (conjectured) good approximation ratio, the Greedy Hierarchical Algorithm provably finds a 3.5approximation, and finds exact solutions for the special cases where we know polynomial time (not greedy) exact algorithms: (1) when the input strings form a spectrum of a string (2) when all input strings have length at most 2.
BibTeX  Entry
@InProceedings{golovnev_et_al:LIPIcs:2019:11241,
author = {Alexander Golovnev and Alexander S. Kulikov and Alexander Logunov and Ivan Mihajlin and Maksim Nikolaev},
title = {{Collapsing Superstring Conjecture}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {26:126:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11241},
URN = {urn:nbn:de:0030drops112411},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.26},
annote = {Keywords: superstring, shortest common superstring, approximation, greedy algorithms, greedy conjecture}
}
17.09.2019
Keywords: 

superstring, shortest common superstring, approximation, greedy algorithms, greedy conjecture 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 