Topology of strings: median string is NP-complete
Given a set of strings, the problem of finding a string that minimises its distance to the set is directly related with problems frequently encountered in areas involving pattern recognition or computational biology. Based on the Levenshtein (or edit) distance, different definitions of distances between a string and a set of strings can be adopted. In particular, if this definition is the sum of the distances to each string of the set, the string that minimises this distance is the (generalised) median string. Finding this string corresponds in speech recognition to giving a model for a set of acoustic sequences, and in computational biology to constructing an optimal evolutionary tree when the given phylogeny is a star. Only efficient algorithms are known for finding approximate solutions. The results in this paper are combinatorial and negative. We prove that computing the median string corresponds to a NP-complete decision problems, thus proving that this problem is NP-hard.
- Complexities of the centre and median string problems
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
- Recognizing string graphs in NP
- The consensus string problem for a metric is NP-complete
- Some computations in string topology
- scientific article; zbMATH DE number 1336330
- String graphs. II: Recognizing string graphs is NP-hard
- The transposition median problem is NP-complete
- A survey of multiple sequence comparison methods
- Approximation algorithms for tree alignment with a given phylogeny
- Finding approximate patterns in strings
- From the median to the generalized center
- scientific article; zbMATH DE number 3825216 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 828444 (Why is no real title available?)
- Multiple sequence comparison -- a peptide matching approach
- The String-to-String Correction Problem
- The computational complexity of calculating partition functions of optimal medians with Hamming distance
- Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
- An efficient approach for the rank aggregation problem
- Hardness results for the center and median string problems under the weighted and unweighted edit distances
- Computing the expected edit distance from a string to a PFA
- Heuristics for the generalized median graph problem
- Complexities of the centre and median string problems
- scientific article; zbMATH DE number 4057049 (Why is no real title available?)
- Computing the expected edit distance from a string to a probabilistic finite-state automaton
- scientific article; zbMATH DE number 2090197 (Why is no real title available?)
- scientific article; zbMATH DE number 1446756 (Why is no real title available?)
- NP-completeness of special string editing problems
- New approach to searching for string median and visualization of string clusters
- Listing center strings under the edit distance metric
- The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
- Hardness of median and center in the Ulam metric
- The consensus string problem for a metric is NP-complete
- Generalized median graph computation by means of graph embedding in vector spaces
This page was built for publication: Topology of strings: median string is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978500)
