On the kernelization complexity of string problems

DOI10.1016/J.TCS.2018.03.024MaRDI QIDQ1749539zbMATH OpenOpenAlexWikidataFDO

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

Publication date 17 May 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.03.024

zbMATH Keywords

kernelizationstring problemsclosest stringcross-composition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• On the kernelization complexity of string problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• scientific article; zbMATH DE number 2081011
• Closest Substring Problems with Small Distances
• Randomized and Parameterized Algorithms for the Closest String Problem

Cites work

• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• Closest Substring Problems with Small Distances
• Distinguishing string selection problems.
• Finding similar regions in many sequences
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Incompressibility through Colors and IDs
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization Lower Bounds by Cross-Composition
• Lossy kernelization
• Minimum common string partition problem: hardness and approximations
• Multivariate algorithmics for NP-hard string problems
• On covering problems of codes
• On problems without polynomial kernels
• On the closest string and substring problems
• On the parameterized intractability of motif search problems
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The complexity of multiple sequence alignment with SP-score that is a metric

Cited in

(13)

• On Hardness of Several String Indexing Problems
• \(k\) one-way heads cannot do string-matching
• On the kernelization complexity of string problems
• The complexity of string partitioning
• Offensive alliances in graphs
• scientific article; zbMATH DE number 6851884 (Why is no real title available?)
• FLIPPING LETTERS TO MINIMIZE THE SUPPORT OF A STRING
• The Complexity of String Partitioning
• Consensus strings with small maximum distance and small distance sum
• Parameterized complexity analysis for the closest string with wildcards problem
• The complexity of binary matrix completion under diameter constraints
• On the complexity of learning strings and sequences
• The invariant problem for binary string structures and the parallel complexity theory of queries

Describes a project that uses

Uses Software

• MSOAR

This page was built for publication: On the kernelization complexity of string problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749539)