Solving 3-superstring in 3n/3 time

Abstract. In the shortest common superstring problem (SCS) one is given a set s1,..., sn of n strings and the goal is to find a shortest string containing each si as a substring. While many approximation algorithms for this problem have been developed, it is still not known whether it can be solved exactly in fewer than 2n steps. In this paper we present an algorithm that solves the special case when all of the input strings have length 3 in time 3n/3 and polynomial space. The algorithm generates a combination of a de Bruijn graph and an overlap graph, such that a SCS is then a shortest directed rural postman path (DRPP) on this graph. We show that there exists at least one optimal DRPP satisfying some natural properties. The algorithm works basically by exhaustive search, but on the reduced search space of such paths of size 3n/3.