The Complexity of String Partitioning

DOI10.1007/978-3-642-31265-6_13zbMATH Open1358.68336arXiv1204.2201OpenAlexW2924094412MaRDI QIDQ2904489FDOQ2904489

Authors: Anne Condon, Ján Maňuch, Chris Thachuk 

Publication date: 14 August 2012

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Abstract: Given a string $w$ over a finite alphabet $Sigma$ and an integer $K$, can $w$ be partitioned into strings of length at most $K$, such that there are no emph{collisions}? We refer to this question as the emph{string partition} problem and show it is NP-complete for various definitions of collision and for a number of interesting restrictions including $|Sigma|=2$. This establishes the hardness of an important problem in contemporary synthetic biology, namely, oligo design for gene synthesis.

Full work available at URL: https://arxiv.org/abs/1204.2201

Recommendations

• The complexity of string partitioning
• Exponential and polynomial time algorithms for the minimum common string partition problem
• The combinatorial complexity of a finite string
• Minimum common string partition problem: hardness and approximations
• Algorithms and Computation
• On the kernelization complexity of string problems
• On the kernelization complexity of string problems
• Crochemore's partitioning on weighted strings and applications
• Minimum common string partition revisited
• Minimum common string partition revisited

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cited In (4)

• Separating strings with small automata
• The complexity of string partitioning
• Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
• Computing equality-free string factorisations

This page was built for publication: The Complexity of String Partitioning

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