In my view, reducing overlap assembly to the Hamilton Path problem is just an illusion. I could not find the full text of old literatures -- among the papers I know, such a formulation seems to first appear in the 2001 Euler paper, a paper that objects to OLC. Even if there are earlier papers on this formulation, the modern theory on OLC as is established by Myers et al has nothing to do with Hamilton Path reduction. It almost seems to me that the Hamilton reduction was introduced only to promote the Eulerian approach.
Anyway, on real data, there may be many dead ends, artifactual reads and missing or false overlaps. Strict Hamilton paths often don't make sense. In addition, we usually require very low misassembly rate. That is best achieved by breaking contigs whenever there are ambiguities -- rather than seeking "optimal" Hamilton Paths that may be sensitive to all kinds of errors. Furthermore, most heuristic overlap-based assemblers has average time complexity better than O(N^2). I guess those approximate Hamilton Path finders can't achieve this?
For long reads, OLC is still the king. To my limited knowledge, the vast majority (if not all) of large genomes sequenced with >=1kb reads were assembled with OLC-based assemblers. If you are interested in de novo assembly, I would recommend to read Myers et al's papers in 1995 (overlap graph), 2000 (celera assembler) and 2005 (string graph). These are the proven theory on OLC and are still used today for PacBio and nanopore assemblies.
