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

DOI10.1016/j.tcs.2016.12.018zbMath1356.68101arXiv1604.03243OpenAlexW2963448547MaRDI QIDQ507598

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)

Cites Work

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

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