Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/79868
Title: On the kernelization complexity of string problems
Authors: Basavaraju, M
Panolan, F
Rai, A 
Ramanujan, MS
Saurabh, S
Keywords: String problems
Closest String
Kernelization
Cross-composition
Issue Date: 2018
Publisher: Elsevier
Source: Theoretical computer science, 19 June 2018, v. 730, p. 21-31 How to cite?
Journal: Theoretical computer science 
Abstract: In the CLOSEST STRING problem we are given an alphabet Sigma, a set of strings S = s2,...,sk over Sigma such that vertical bar S-i vertical bar = n and an integer d. The objective is to check whether there exists a string s over E such that d(H)(s, s(i)) <= d, i is an element of {1, ..., where d(H)(x,y) denotes the number of places strings x and y differ at. CLOSEST STRING is a prototype string problem. This problem together with several of its variants such as DISTINGUISHING STRING SELECTION and CLOSEST SUBSTRING have been extensively studied from parameterized complexity perspective. These problems have been studied with respect to parameters that are combinations of k, d, vertical bar Sigma vertical bar and n. However, surprisingly the kernelization question for these problems (for the versions when they admit fixed-parameter tractable algorithms) is not studied at all. In this paper we fill this gap in the literature and do a comprehensive study of these problems from kernelization complexity perspective. We settle almost all the problems by either obtaining a polynomial kernel or showing that the problem does not admit a polynomial kernel under a standard assumption in complexity theory.
URI: http://hdl.handle.net/10397/79868
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2018.03.024
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.