CLR cover

Problem 62: Shortest Common Superstring of Short Words

A common superstring of a set $X$ of words is a word in which all elements of $X$ occur as factors. Computing a shortest common superstring (SCS) is an NP-complete problem but there are simple cases that can be solved efficiently, like the special case discussed in the problem.

Show how to compute in linear time the length of a shortest common superstring of a set $X$ of words of length $2$ over an integer alphabet.
Transform the question into a problem on graphs.

References

  • J. Gallant, D. Maier, and J. A. Storer. On finding minimal length superstrings. Journal of Computer and System Sciences, 20(1):50-58, 1980.