Partial Digest is Hard to Solve for Erroneous Input Data
Authors: Mark Cieliebak, Stephan Eidenbenz, and Paolo Penna.
Reference: Theoretical Computer Science. Vol. 349, No. 3, pp. 361-381, 2005.
Download: coming soon
The Partial Digest problem asks for the coordinates of m points on a line such that the pairwise distances of the points form a given multiset of $m \choose 2$ distances. Partial Digest is a well-studied problem with important applications in physical mapping of DNA molecules. Its computational complexity status is open. Input data for Partial Digest from real-life experiments are always prone to error, which suggests to study variations of Partial Digest that take this fact into account. In this paper, we study the computational complexity of Partial Digest variants that model three different error types that can occur in the data: additional distances, missing distances, and erroneous fragment lengths. We show that these variations are NP-hard, hard to approximate, and strongly NP-hard, respectively.
Remarks: Link to ScienceDirect:!&_cdi=5674&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=57a569df92987096d0f5b6d34e842fd0

Note: electronic versions may not always correspond exactly to printed versions.