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.MFCS.2018.1
URN: urn:nbn:de:0030-drops-95834
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9583/
Go to the corresponding LIPIcs Volume Portal

Bulteau, Laurent ; Schmid, Markus L.

Consensus Strings with Small Maximum Distance and Small Distance Sum

pdf-format:
LIPIcs-MFCS-2018-1.pdf (0.6 MB)

Abstract

The parameterised complexity of consensus string problems (Closest String, Closest Substring, Closest String with Outliers) is investigated in a more general setting, i. e., with a bound on the maximum Hamming distance and a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of Closest String and Closest Substring, and partly for Closest String with Outliers; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds.

BibTeX - Entry

@InProceedings{bulteau_et_al:LIPIcs:2018:9583,
  author =	{Laurent Bulteau and Markus L. Schmid},
  title =	{{Consensus Strings with Small Maximum Distance and Small Distance Sum}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9583},
  URN =		{urn:nbn:de:0030-drops-95834},
  doi =		{10.4230/LIPIcs.MFCS.2018.1},
  annote =	{Keywords: Consensus String Problems, Closest String, Closest Substring, Parameterised Complexity, Kernelisation}
}

Keywords: Consensus String Problems, Closest String, Closest Substring, Parameterised Complexity, Kernelisation
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

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