Please use this identifier to cite or link to this item: https://idr.l2.nitk.ac.in/jspui/handle/123456789/12377
Title: On the kernelization complexity of string problems
Authors: Basavaraju, M.
Panolan, F.
Rai, A.
Ramanujan, M.S.
Saurabh, S.
Issue Date: 2018
Citation: Theoretical Computer Science, 2018, Vol.730, , pp.21-31
Abstract: In the CLOSEST STRING problem we are given an alphabet ?, a set of strings S={s1,s2, ,sk} over ? such that |si|=n and an integer d. The objective is to check whether there exists a string s over ? such that dH(s,si)?d, i?{1, ,k}, where dH(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, |?| 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. 2018 Elsevier B.V.
URI: http://idr.nitk.ac.in/jspui/handle/123456789/12377
Appears in Collections:1. Journal Articles

Files in This Item:
There are no files associated with this item.


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