License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.61
URN: urn:nbn:de:0030-drops-129278
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12927/
Go to the corresponding LIPIcs Volume Portal

Hoppenworth, Gary ; Bentley, Jason W. ; Gibney, Daniel ; Thankachan, Sharma V.

The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance

pdf-format:
LIPIcs-ESA-2020-61.pdf (0.6 MB)

Abstract

We present the first fine-grained complexity results on two classic problems on strings. The first one is the k-Median-Edit-Distance problem, where the input is a collection of k strings, each of length at most n, and the task is to find a new string that minimizes the sum of the edit distances from itself to all other strings in the input. Arising frequently in computational biology, this problem provides an important generalization of edit distance to multiple strings and is similar to the multiple sequence alignment problem in bioinformatics. We demonstrate that for any ε > 0 and k ≥ 2, an O(n^{k-ε}) time solution for the k-Median-Edit-Distance problem over an alphabet of size O(k) refutes the Strong Exponential Time Hypothesis (SETH). This provides the first matching conditional lower bound for the O(n^k) time algorithm established in 1975 by Sankoff.
The second problem we study is the k-Center-Edit-Distance problem. Here also, the input is a collection of k strings, each of length at most n. The task is to find a new string that minimizes the maximum edit distance from itself to any other string in the input. We prove that the same conditional lower bound as before holds. Our results also imply new conditional lower bounds for the k-Tree-Alignment and the k-Bottleneck-Tree-Alignment problems studied in phylogenetics.

BibTeX - Entry

@InProceedings{hoppenworth_et_al:LIPIcs:2020:12927,
  author =	{Gary Hoppenworth and Jason W. Bentley and Daniel Gibney and Sharma V. Thankachan},
  title =	{{The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{61:1--61:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12927},
  URN =		{urn:nbn:de:0030-drops-129278},
  doi =		{10.4230/LIPIcs.ESA.2020.61},
  annote =	{Keywords: Edit Distance, Median String, Center String, SETH}
}

Keywords: Edit Distance, Median String, Center String, SETH
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI