2026-07-23T05:29:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12142 2024-03-06T10:49:24Z ddc:004 open_access

String Factorizations Under Various Collision Constraints Grüttemeier, Niels Komusiewicz, Christian Morawietz, Nils Sommer, Frank NP-hard problem fixed-parameter algorithms collision-aware string partitioning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niels Grüttemeier and Christian Komusiewicz and Nils Morawietz and Frank Sommer 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.17 urn:nbn:de:0030-drops-121428 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.17 eng https://creativecommons.org/licenses/by/3.0/legalcode