Hoppenworth, Gary ;
Bentley, Jason W. ;
Gibney, Daniel ;
Thankachan, Sharma V.
The FineGrained Complexity of Median and Center String Problems Under Edit Distance
Abstract
We present the first finegrained complexity results on two classic problems on strings. The first one is the kMedianEditDistance 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 kMedianEditDistance 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 kCenterEditDistance 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 kTreeAlignment and the kBottleneckTreeAlignment 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 FineGrained Complexity of Median and Center String Problems Under Edit Distance}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {61:161:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12927},
URN = {urn:nbn:de:0030drops129278},
doi = {10.4230/LIPIcs.ESA.2020.61},
annote = {Keywords: Edit Distance, Median String, Center String, SETH}
}
26.08.2020
Keywords: 

Edit Distance, Median String, Center String, SETH 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 