Separating sets of strings by finding matching patterns is almost always hard

DOI10.1016/J.TCS.2016.12.018MaRDI QIDQ507598zbMATH OpenOpenAlexFDO

Authors Giuseppe Lancia, Luke Mathieson, Pablo Moscato

Publication date 6 February 2017

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

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

zbMATH Keywords

computational complexityparameterized complexitypattern identification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Abstract: We study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W[2]-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others.

Recommendations

• scientific article; zbMATH DE number 2086339
• A practical algorithm to find the best subsequence patterns
• On the parameterized intractability of motif search problems
• Distinguishing string selection problems.
• Parameterized intractability of distinguishing substring selection

Cites work

• scientific article; zbMATH DE number 67610 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2086391 (Why is no real title available?)
• scientific article; zbMATH DE number 2086667 (Why is no real title available?)
• An analysis of the W*-hierarchy
• Approximation algorithms for combinatorial problems
• Approximation algorithms for the class cover problem
• Every Planar Map is Four Colorable
• Finding patterns common to a set of strings
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Fundamentals of parameterized complexity
• Multivariate algorithmics for NP-hard string problems
• On the closest string and substring problems
• Parameterized complexity analysis for the closest string with wildcards problem
• Parameterized intractability of distinguishing substring selection
• Parametrized complexity theory.
• Pattern-guided \(k\)-anonymity
• The Parameterized Complexity of k-Edge Induced Subgraphs
• The \(k\)-feature set problem is \(W[2]\)-complete
• Using patterns to form homogeneous teams

Cited in

(5)

• Computing and Combinatorics
• A practical algorithm to find the best subsequence patterns
• scientific article; zbMATH DE number 2086339 (Why is no real title available?)
• Disjoint pattern matching and implication in strings
• Three one-way heads cannot do string matching

This page was built for publication: Separating sets of strings by finding matching patterns is almost always hard

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