String Factorizations Under Various Collision Constraints

Authors Niels Grüttemeier , Christian Komusiewicz , Nils Morawietz, Frank Sommer



PDF
Thumbnail PDF

File

LIPIcs.CPM.2020.17.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Niels Grüttemeier
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Christian Komusiewicz
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Nils Morawietz
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Frank Sommer
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany

Cite AsGet BibTex

Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. String Factorizations Under Various Collision Constraints. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CPM.2020.17

Abstract

In the NP-hard Equality-Free String Factorization problem, we are given a string S and ask whether S can be partitioned into k factors that are pairwise distinct. We describe a randomized algorithm for Equality-Free String Factorization with running time 2^k⋅ k^{𝒪(1)}+𝒪(n) improving over previous algorithms with running time k^{𝒪(k)}+𝒪(n) [Schmid, TCS 2016; Mincu and Popa, Proc. SOFSEM 2020]. Our algorithm works for the generalization of Equality-Free String Factorization where equality can be replaced by an arbitrary polynomial-time computable equivalence relation on strings. We also consider two factorization problems to which this algorithm does not apply, namely Prefix-Free String Factorization where we ask for a factorization of size k such that no factor is a prefix of another factor and Substring-Free String Factorization where we ask for a factorization of size k such that no factor is a substring of another factor. We show that these two problems are NP-hard as well. Then, we show that Prefix-Free String Factorization with the prefix-free relation is fixed-parameter tractable with respect to k by providing a polynomial problem kernel. Finally, we show a generic ILP formulation for R-Free String Factorization where R is an arbitrary relation on strings. This formulation improves over a previous one for Equality-Free String Factorization in terms of the number of variables.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Pattern matching
Keywords
  • NP-hard problem
  • fixed-parameter algorithms
  • collision-aware string partitioning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, and Shiho Sugimoto. Diverse palindromic factorization is NP-complete. Int. J. Found. Comput. Sci., 29(2):143-164, 2018. Google Scholar
  2. Andreas Björklund. Determinant sums for undirected hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. Google Scholar
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci., 87:119-139, 2017. Google Scholar
  4. Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Fast witness extraction using a decision oracle. In Proceedings of the 22nd Annual European Symposium on Algorithms (ESA '14), volume 8737 of LNCS, pages 149-160. Springer, 2014. Google Scholar
  5. Laurent Bulteau, Falk Hüffner, Christian Komusiewicz, and Rolf Niedermeier. Multivariate algorithmics for NP-hard string problems. Bulletin of the EATCS, 114, 2014. Google Scholar
  6. Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci., 23(2):357-374, 2012. Google Scholar
  7. Anne Condon, Ján Manuch, and Chris Thachuk. Complexity of a collision-aware string partition problem and its relation to oligo design for gene synthesis. In Proceedings of the 14th International Computing and Combinatorics Conference (COCOON '08), volume 5092 of LNCS, pages 265-275. Springer, 2008. Google Scholar
  8. Anne Condon, Ján Manuch, and Chris Thachuk. The complexity of string partitioning. J. Discrete Algorithms, 32:24-43, 2015. Google Scholar
  9. Maxime Crochemore and Wojciech Rytter. Jewels of stringology. World Scientific, 2002. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  11. Henning Fernau, Florin Manea, Robert Mercas, and Markus L. Schmid. Pattern matching with variables: Fast algorithms and new hardness results. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS '15), volume 30 of LIPIcs, pages 302-315. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  12. Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for scheduling and packing problems. SIAM J. Discrete Math., 30(1):343-366, 2016. Google Scholar
  13. Christian Komusiewicz, Mateus de Oliveira Oliveira, and Meirav Zehavi. Revisiting the parameterized complexity of maximum-duo preservation string mapping. In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM '17), volume 78 of LIPIcs, pages 11:1-11:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  14. Lukasz Kowalik and Juho Lauri. On finding rainbow and colorful paths. Theor. Comput. Sci., 628:110-114, 2016. Google Scholar
  15. Radu Stefan Mincu and Alexandru Popa. The maximum equality-free string factorization problem: Gaps vs. no gaps. In Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '20), volume 12011 of LNCS, pages 531-543. Springer, 2020. Google Scholar
  16. Markus L. Schmid. Computing equality-free and repetitive string factorisations. Theor. Comput. Sci., 618:42-51, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail