Noisy data make the partial digest problem NP-hard
Mark Cieliebak, Eidenbenz, Stephan J., Penna, Paolo · 2002
The PARTIAL DIGEST problem well-known for its applications in computational biology and for the intriguingly open status of its computational complexity asks for the coordinates of n points on a line such that the pairwise distances of the points form a given multi-set of () distances. In an effort to model real-life data, we study the computational complexity of a minimization version of PARTIAL DIGEST, in which only a subset of all pairwise distances is given and the rest are lacking due to experimental errors. We show that this variation is NP-hard to solve exactly, thus making the existence of polynomial-time algorithms for this problem extremely unlikely. Our result answers an open question posed by Pevzner (2000). We then study a maximiza- tion version of PARTIAL DIGEST where a superset of all pairwise distances is given, with some additional distances due to inaccurate measurements. We show that this maximization version is NP-hard to approximate to within a factor of [D[ -c for any e 0, where [D[ is the number of input distances, which implies that polynomial-time algorithms cannot even guarantee to find a solution for the problem that comes close to the optimum. Our inapproximabilky result is tight up to low-order terms as we give a trivial approximation algorithm that achieves a matching approximation ratio. Our optimization variations model two different error types that occur in real-life data.