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

DOI10.1016/J.TCS.2016.12.018zbMATH Open1356.68101arXiv1604.03243OpenAlexW2963448547MaRDI QIDQ507598FDOQ507598

Authors: Giuseppe Lancia, Luke Mathieson, Pablo Moscato 

Publication date: 6 February 2017

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Three one-way heads cannot do string matching
• A practical algorithm to find the best subsequence patterns
• Disjoint pattern matching and implication in strings
• Computing and Combinatorics

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)