Measurement Errors Make the Partial Digest Problem NP-hard | |
Authors: | Mark Cieliebak and Stephan Eidenbenz. |
Reference: | In "Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004)". Buenos Aires, Argentina, May 2004. Springer, LNCS 2976, pp. 379-390, 2004. |
Download: | Postscript (.ps) or PDF (.pdf) |
Abstract: |
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 the variation of Partial Digest in which each distance is known only
up to some error, due to experimental inaccuracies. The error can be specified
either by some additive offset or by a multiplicative factor. We show
that both types of error make the Partial Digest problem strongly NP-complete,
by giving reductions from 3-Partition. In the case of relative errors,
we show that the problem is hard to solve even for constant relative error.
|
Remarks: |