On the kernelization complexity of string problems

In the Closest String problem we are given an alphabet Σ, a set of strings S = { s 1, s 2, …, s k } over Σ such that | s i | = n and an integer d. The objective is to check whether there exists a string s over Σ such that d H ( s, s i ) ≤ d, i ∈ { 1, …, k }, 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, | Σ | 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.

Authors

• Manu Basavaraju
• Fahad Panolan
• Ashutosh Rai
• M.S. Ramanujan
• Saket Saurabh

Keywords

• String problems
• Closest String
• Kernelization
• Cross-composition