Grüttemeier, Niels ;
Komusiewicz, Christian ;
Morawietz, Nils ;
Sommer, Frank
String Factorizations Under Various Collision Constraints
Abstract
In the NPhard EqualityFree 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 EqualityFree 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 EqualityFree String Factorization where equality can be replaced by an arbitrary polynomialtime computable equivalence relation on strings. We also consider two factorization problems to which this algorithm does not apply, namely PrefixFree String Factorization where we ask for a factorization of size k such that no factor is a prefix of another factor and SubstringFree 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 NPhard as well. Then, we show that PrefixFree String Factorization with the prefixfree relation is fixedparameter tractable with respect to k by providing a polynomial problem kernel. Finally, we show a generic ILP formulation for RFree String Factorization where R is an arbitrary relation on strings. This formulation improves over a previous one for EqualityFree String Factorization in terms of the number of variables.
BibTeX  Entry
@InProceedings{grttemeier_et_al:LIPIcs:2020:12142,
author = {Niels Gr{\"u}ttemeier and Christian Komusiewicz and Nils Morawietz and Frank Sommer},
title = {{String Factorizations Under Various Collision Constraints}},
booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
pages = {17:117:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771498},
ISSN = {18688969},
year = {2020},
volume = {161},
editor = {Inge Li G{\o}rtz and Oren Weimann},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12142},
URN = {urn:nbn:de:0030drops121428},
doi = {10.4230/LIPIcs.CPM.2020.17},
annote = {Keywords: NPhard problem, fixedparameter algorithms, collisionaware string partitioning}
}
09.06.2020
Keywords: 

NPhard problem, fixedparameter algorithms, collisionaware string partitioning 
Seminar: 

31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Issue date: 

2020 
Date of publication: 

09.06.2020 