Separating Sets of Strings by Finding Matching
Patterns is Almost Always Hard
Giuseppe Lancia
Dipartimento di Matematica e Informatica, University of Udine, Via delle Scienze 206,
33100 Udine, Italy

arXiv:1604.03243v3 [cs.CC] 19 Dec 2016

Luke Mathieson
School of Electrical Engineering and Computer Science, University of Newcastle,
Callaghan, NSW 2308, Australia

Pablo Moscato
School of Electrical Engineering and Computer Science, University of Newcastle,
Callaghan, NSW 2308, Australia

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.
Keywords: pattern identification, parameterized complexity,
computational complexity
1. Introduction
Finding patterns in a collection of data is one of the fundamental problems
in data mining, data science, artificial intelligence, bioinformatics and many
other areas of both theoretical and applied computer science. Accordingly

Preprint submitted to Elsevier

December 20, 2016

there are a large number of formulations of this problem. In this paper we
develop a particular formulation, drawn from two central motivations:
1. multiparent recombination in genetic and evolutionary algorithms, and
2. the construction of explanatory patterns in single-nucleotide polymorphisms related to disease.
It should not be construed however that these motivations are limitations on
the applicability of the problem we develop and study. As will be seen, the
underlying computational problem is a general one that occurs as a fundamental component of many other computational problems.
1.1. The Central Problem
Before expanding upon the motivations, we briefly introduce the core computational problem to provide a semi-formal context and some unifying vocabulary. For full definitions we refer the reader to Section 2. Central to the
problem is the notion of pattern, a string over an alphabet Σ which has been
augmented with a special symbol ∗. A pattern matches a string over Σ if the
pattern and the string are the same length and each character of the pattern
is the same as the character of the string at that position, or the pattern has
an ∗ at that position, i.e. ∗ ‘matches’ any symbol from the alphabet. The
fundamental problem is then, given two sets, G and B, of strings over Σ,
can we find a set of patterns of size at most k such that every string in G
matches one of our patterns, and none of the strings in B match any of our
patterns.
1.2. Separating Healthy Patterns from Diseased
A significant portion of bioinformatics and computational medicine efforts
are focused on developing diagnostic tools. The identification of explanatory
genes, uncovering of biomarkers, metabolic network analysis and protein interaction analysis all have as a key (but not sole) motivation the identification
of differential markers of disease and consequently routes to treatment. Consider the following problem as a motivating archetypal example: we have two
sets of individuals, healthy and diseased and for each example we are given a
string that encodes the single-nucleotide polymorphism (SNPs) states across
the two copies of each genome, giving us two sets of strings G and B 1 . A
SNP has several alleles of which an individual has two. The individual may
1

Whether healthy is G and diseased is B or vice versa depends on what information
we wish the set of patterns to extract.

2

thus be homozygous in any of the alleles, or heterozygous with any choice of
pairs of alleles, giving the underlying alphabet Σ.
It is easy to see that if we can identify patterns of SNPs that separate the
healthy from the diseased individuals, we have a source of genetic information
that may assist in explaining and treating the disease.
This problem is even more apparent in its computational form when considering a biologically motivated form of computation, i.e., evolutionary algorithms.
1.3. Patterns in Multiparent Recombination
The central mechanism for optimization in Genetic Algorithms (GAs) is the
recombination of parent solutions to produce a new child solution which
ideally retains the positive aspects of the parents. The mechanism derives
from an analogy with sexual reproduction in biological evolution and hence
typically combines two existing solutions to produce the offspring. In the
optimization setting however, there’s no conceptual reason for this restriction.
Given that recombination can be viewed as a local move in the search space
from one individual solution to another as mediated by a third individual
solution, a natural generalization of this is to employ multiple parents in the
hope of further refining the components of the solution that promote quality,
while producing new solutions that effectively cover the search space.
The central theoretical formalization for describing this process is that of
schemata 2 . An individual solution in a (simple) GA is described by an array,
which we can represent as a string, of length n over a given alphabet Σ.
A schema is a string of length n over the same alphabet augmented with
the special “wild card” character ∗, i.e., a pattern. A schema can then be
thought of as representing a portion of the search space. The preservation of
desirable shared characteristics of two or more parent individuals can then be
viewed as the problem of defining a suitable schema. We can define a set G
using the individuals selected as parents for a recombination operation, and,
if desired, a set B from any individuals whose characteristics we may wish to
avoid. The child individual(s) can then be generated from this schema with
the wild cards replaced in whichever manner is chosen. Thus we can use
schemata to model the basic operation of genetic recombination operators.
This idea not only models multiparent recombination but also multi-child
recombination. When considering simply a set of parents from which we wish
to generate a set of children, constructing schemata that are compatible with
2
We use the third declension neuter form of schema, as it matches better the Greek
roots of the word.

3

the parents is straightforward. A single schema that is a string of n many
∗ symbols would suffice as a trivial solution and the natural solution where
for each position, if all the parents agree on the same symbol, the schema
has that symbol and ∗ otherwise also provides a simple solution. However
in these cases it is reasonably easy to see that the schemata generated can
easily be under-specified, leading to a loss of useful information, rendering
the recombination operation ineffective. One solution to this problem is to
ask for a small set of schemata that are compatible with the parents, but are
incompatible with a set of forbidden strings – akin to the list of forbidden
elements in Tabu search. In this paper, we elaborate upon and examine this
idea.
Some further complexity issues surrounding multiparent recombination have
been examined in [10].
1.4. Our Contribution
In this paper we formalize the problem of finding a small set of patterns that
match a set of strings, without matching a set of forbidden strings, as discussed in the introduction and examine its complexity. We call the general
form of the problem Pattern Identification and introduce some useful
variants. In most cases this problems turn out to be hard. We naturally
then consider the problem from a Parameterized Complexity perspective.
The problem has a rich parameter ecology and also provides an interesting
example of a non-graph theoretic problem. Unfortunately for many parameterizations the problem turns out to be hard in this setting as well. The
natural parameterization by the number of desired schemata is W[2]-hard.
Even if we take the length of the strings as the parameter, the problem is
para-NP-complete. Table 1 gives a summary of the parameterized results,
and some key open problems. It is also inapproximable and for some cases
we obtain parameterized inapproximability results as well. The only case
for which we are able to obtain fixed-parameter tractability relies on a small
number of input strings which have a limited number of symbols which are
different from a given “base” symbol.
1.5. Related Work
The identification of patterns describing a set of strings forms a well studied
family of problems with a wide series of applications. Although, as best
as we can determine, the precise problems we studied here have not yet
been considered, a number of interesting related problems are explored in
the literature. We present here a selection of some of the more relevant
and interesting results, however these can at best form a basis for further
exploration by the interested reader.
4

One of most immediately similar variants is that where pattern variables are
allowed. In contrast to the work here, these variables can act as substrings
of arbitrary length. Keans and Pitt [23] give a family of polynomial time
algorithms for learning the language generated by a single such pattern with
a given number k of pattern variables. Angluin [1] studies the inverse problem
of generating a pattern, with a polynomial time algorithm for the case where
the pattern contains a single pattern variable being the central result. We
note that a central difference here is the repeated use of variables, allowing
the same undefined substring to be repeated. The properties of these pattern
languages have since been studied in some detail, far beyond the scope of this
paper.
Bredereck, Nichterlein and Niedermeier [4] employ a similar, but not identical, formalism to that employed here, but study the problem of taking a set
of strings and a set of patterns and determining whether the set of strings
can be altered to match the set of patterns. In their formalism patterns are
strings over the set {, ?}. We note in particular though that their definition of matching differs from our definition of compatibility in that a string
matches a pattern if and only if the string has the special symbol ? exactly
where the pattern does. They show this problem to be NP-hard, but in FPT
when parameterized by the combined parameter of the number of patterns
and the number of strings. They also present an ILP based implementation and computational results. Bredereck et al. [3] examine forming teams,
i.e., mapping the set of strings to the set of patterns in a consistent manner.
They use a similar basis, excepting that the special ? symbol in a pattern now
matches any symbol in a string and that the  symbol requires homogeneity
of the matched strings (i.e. the symbol it matches is not specified, but all
matching strings must have the same symbol at that point). They give a series of classification results, with the problem mostly being intractable, but
in FPT for the number of input strings, the number of different input strings
and the combined parameter of alphabet size with the length of the strings.
Gramm, Guo and Niedermeier [18] study another similar problem, Distinguishing Substring Selection, where the input is two sets of strings
(“good” and “bad”), and two integers dg and db with the goal of finding a
single string of length L whose Hamming distance from all length L substrings of every “good” string is at least dg and from at least one length L
substring for each “bad” string is at most db . An extension of the Closest
String [19, 24] and Closest Substring [15] problems, the problem has
a ptas [12] but they show that it is W[1]-hard when parameterized by any
combination of the parameters dg , db and the number of “good” or “bad”
strings. Under sufficient restriction they demonstrate an FPT result, requiring a binary alphabet, a ‘dual’ parameter d0g = L − dg and that d0g is optimal
5

in the sense that it is the minimum possible value. We note that, in relation to the problems studied here, although the number of ∗ symbols in the
patterns provides an upper-bound for the Hamming distance, the Hamming
distance for a set of strings may be much lower; consider a set of strings with
one position set to 1 and all others to 0 such that for every possible position
there is a string with a 1 at that point, then the string (or indeed substring)
of all 0 has Hamming distance at most one from each input string, but a
single pattern would need to be entirely ∗ symbols to match the entire set.
Hermelin and Rozenberg introduce a further variant of the Closest String
problem [21], the Closest String with Wildcards problem. The input
is a set of strings {si }, which may include wildcard characters, and an integer
d. The goal is to find a string with hamming distance at most d to each si .
The solution is required to have no wildcard characters. The examine a number of parameters: the length n of the input strings, the number m of input
strings, d, the number |Σ| of characters in the alphabet, and the minimum
number k of wildcard characters in any input string. They show that the
problem is in FPT (with varying explicit running times) when parameterized
by m, m+n, |Σ|+k +d and k +d. They also show that the special case where
d = 1 can be solved in polynomial time, whereas the problem is NP-hard for
every d ≥ 2.
Bulteau et al. [5] also give a survey of the parameterized complexity of a
variety of more distantly related string problems, with similar multivariate parameterizations as in other work in this area. They cover, amongst
others, Closest String, Closest Substring, Longest Common Subsequence, Shortest Common Supersequence, Shortest Common
Superstring, Multiple Sequence Alignment and Minimum Common String.
Introduced by Cannon and Cowen [6], the Class Cover problem is a geometric relative of Pattern Identification where the input is two sets
of points colored red and blue, with the goal of selecting a minimum set of
blue points (centers) that “cover” the full set of blue points, in the sense
that any blue point is closer to its nearest center than any red point. It
is NP-hard with an O(log n + 1)-factor approximation algorithm, bearing a
close similarity to Dominating Set.
2. Preliminaries and Definitions
We now give the relevant definitions for the complexity analysis that follows. In the reductions we use the well known Dominating Set and
Vertex Cover problems. The graphs taken as input for these problems
are simple, undirected and unweighted. To assist with notation and indexing,
6

we take the vertex set V (G) of a graph G to be the set {1, . . . , n}. The edge
set E(G) is then a set of pairs drawn from V (G) and we denote the edge
between vertices i and j by ij (= ji). The Set Cover and k-Feature Set
problems are also employed. The problems are defined as follows:
Dominating Set:
Instance:
A graph G and an integer k.
Question:
Is there a set V 0 ⊆ V (G) with |V 0 | ≤ k such
that for every u ∈ V (G) there exists a v ∈ V 0
with u ∈ N (v)?
Vertex Cover:
Instance:
A graph G and an integer k.
Question:
Is there a set V 0 ⊆ V (G) with |V 0 | ≤ k such
that for every uv ∈ E(G) we have u ∈ V 0 or
v ∈ V 0?
Set Cover:
Instance:
A base set U , a set S ⊆ P(U ) and an integer
k.
Question:
Is
a set S 0 ⊆ S with |S 0 | ≤ k such that
S there
0
S = U?
k-Feature Set:
Instance:
An n × m 0-1 matrix M , an n × 1 0-1 vector
f and an integer k.
Question:
Is there a set of indices I ⊆ {1, . . . , m} with
|I| ≤ k such that for all a, b where fa 6= fb
there exist i ∈ I such that Ma,i 6= Mb,i ?
We note the following key classification results:
• Dominating Set is NP-complete, O(log n)-APX-hard3 and W[2]complete when parameterized by k, the size of the dominating set.
• Vertex Cover is NP-complete and APX-hard, and remains NPcomplete when the input is a planar graph [17].
3

That is there exists some c > 0 such that Dominating Set has no c · log n-factor
approximation algorithm unless P = NP.

7

• Set Cover is W[2]-complete when parameterized by the size of the
set cover.
• k-Feature Set is W[2]-complete when parameterized by the size of
the feature set [9].
We also employ a parameterized version of the Model Checking problem,
which takes as input a finite structure and a logical formula and asks the
question of whether the structure is a model of the formula, i.e. whether
there is a suitable assignment of elements of the universe of the structure
to variables of the formula such that the formula evaluates to true under
that assignment. The parameter is the length of the logic formula. While
we informally introduce the finite structural elements as needed, we briefly
describe here the fragments of first-order logic we employ. Let Σ0 = Π0 be
the set of unquantified Boolean formulae. The classes Σt and Πt for t > 0
can be defined recursively as follows:
Σt = {∃x1 . . . ∃xk ϕ | ϕ ∈ Πt−1 }
Πt = {∀x1 . . . ∀xk ϕ | ϕ ∈ Σt−1 }
The class Σt,u is the subclass of Σt where each quantifier block after the first
existential block has length at most u. We note that trivially Πt−1 ⊂ Σt .
We note that these classes are specified in prenex normal form, and are, in
general, not robust against Boolean combinations of formulae. In general,
the process of converting a formula to prenex normal form (where all quantifiers are “out the front”) increases the number of quantifier alternations. An
analog of the Σ classes is Σ∗t,u . Let Θ0,u be the set of quantifier free formulae,
and Θt,u for t > 0 be the set of Boolean combinations of formulae where
each leading quantifier block is existential and quantifies over a formula in
Θt−1,u , where the length of each quantifier block is at most u. That is, the
formulae in Θt,u are not required to be in prenex normal form, and Boolean
connectives may precede some quantifiers. We can deal with leading universal quantification by the normal expedient of the introduction of a trivial
existential block. Then Σ∗t,u is the class of formulae of the form ∃x1 . . . ∃xk ϕ
where ϕ ∈ Θt−1,u and where k may be greater than u.
Thus we refer to the Model Checking problem as MC(Φ) where Φ is the
first-order fragment employed. In the parameterized setting, MC(Σt,u ) is
W[t]-complete for every u ≥ 1, and MC(Σ∗t,u ) is W∗ [t]-complete for every
u ≥ 1. The W∗ -hierarchy is the hierarchy analogous to the W-hierarchy
obtained from using MC(Σ∗t,u ) as the complete problem instead of MC(Σt,u ).
While it is known that W[1] = W∗ [1] and W[2] = W∗ [2]; for t ≥ 3, the best
known containment relationship is W[t] ⊆ W∗ [t] ⊆ W[2t − 2]. For more
8

detail on these results and the full definitions relating to first-order logic
and structures we refer the reader to [16]. The W∗ -hierarchy, introduced by
Downey, Fellows and Taylor [14] but more fully explored later [7, 16] is a
parameterized hierarchy which takes into account the Boolean combinations
of quantified first-order formulae, but is otherwise similar to the more usual
W-hierarchy.
In several of our intractability results we make use of the class para-NP,
and a useful corollary due to Flum and Grohe with a detailed explanation
in [16] (presented as Corollary 2.16). The class para-NP is the direct parameterized complexity translation of NP, where we replace “polynomial-time”
with “fixed-parameter tractable time” (or fpt-time in short) in the definition. Flum and Grohe’s result states that if, given a parameterized problem
(Π, κ), the classical version of the problem Π is NP-complete for at least
one fixed value of κ, then (Π, κ) is para-NP-complete. As may be expected,
FPT = para-NP if and only if P = NP, thus para-NP-completeness is strong
evidence of intractability. We also make reference to parameterized approximation. A parameterized approximation algorithm is, in essence, a standard
approximation algorithm, but where we relax the running time to fpt-time,
rather than polynomial-time. We refer to [25] for a full introduction to this
area.
The other parameterized complexity theory employed is more standard, thus
for general definitions we refer the reader to standard texts [13, 16].
We write A ≤F P T B to denote that there exists a parameterized reduction
from problem A to problem B, and similarly A ≤P B to denote the existence
of a polynomial-time many-one reduction from problem A to problem B. We
also use strict polynomial-time reductions to obtain some approximation results. A strict reduction is one that, given two problems A and B, guarantees
that the approximation ratio for A is at least as good as that of B. In the
cases we present, we employ them for approximation hardness results, so the
precise ratio is not discussed. For a full definition of strict reductions (and
other approximation preserving reductions) we refer to [11].
Definition 2.1 (Pattern). A pattern is a string over an alphabet Σ and a
special symbol ∗.
Given a string s ∈ Σ∗ and an integer i, we denote the ith symbol of s by s[i].
Definition 2.2 (Compatible). A pattern p is compatible with a string g,
denoted p → g, if for all i such that p[i] 6= ∗ we have g[i] = p[i]. If a pattern
and string are not compatible, we write p 6→ g. We extend this notation to
sets of strings, writing p → G to denote ∀g ∈ G, p → g and P → G for
∀g ∈ G∃p ∈ P, p → g.
9

Definition 2.3 (G-B-Separated Sets). A set P of patterns G-B-separates
an ordered pair (G, B) of sets of strings, written P → (G, B) if
• P → G, and
• for every b ∈ B and p ∈ P we have p 6→ b.
Thus we can state the central problem for this paper:
Pattern Identification:
Instance:
A finite alphabet Σ, two disjoint sets G, B ⊆
Σn of strings and an integer k.
Question:
Is there a set P of patterns such that |P | ≤ k
and P → (G, B)?
The complexity analysis of the problem in the parameterized setting leads
to the definition of a second, subsidiary problem which allows a convenient
examination of sets of strings which are very similar.
Definition 2.4 (Small String). A string s over an alphabet Σ is d-small if,
given an identified symbol σ ∈ Σ, for exactly d values of i, p[i] 6= σ.
We call σ the base symbol.
A set of strings S is d-small if, given a fixed base symbol all strings in S are
d-small.
This restriction on the structure of the input gives further insight into the
complexity of Pattern Identification and is key to some of the tractability results in Section 4. For convenience we phrase a restricted version of the
Pattern Identification problem:
PI with Small Strings:
Instance:
An alphabet Σ, two disjoint d-small sets
G, B ⊆ Σn , an integer k.
Question:
Is there a set P of patterns with |P | ≤ k such
that P → (G, B)?
From the perspective of multiparent recombination, minimizing the number
of wildcard symbols in each pattern is also an interesting objective:
PI with Large Patterns:
Instance:
An alphabet Σ, two disjoint sets G, B ⊆ Σn ,
integers k and r.
Question:
Is there a set P of patterns with |P | ≤ k such
that P → (G, B) and for each p ∈ P the number of ∗ symbols in p is at most r?
10

We implicitly define the obvious intersection of the two restricted problems,
PI with Large Patterns and Small Strings.
From a combinatorial perspective, the inverse problem is also interesting:
PI with Small Patterns:
Instance:
An alphabet Σ, two disjoint sets G, B ⊆ Σn ,
integers k and s.
Question:
Is there a set P of patterns with |P | ≤ k such
that P → (G, B) and for each p ∈ P the number of non-∗ symbols in p is at most s?
3. Hard Cases of the Pattern Identification Problem
We first examine the intractable cases of the Pattern Identification
problem. This narrows down the source of the combinatorial complexity
of the problem.
Theorem 3.1. Pattern Identification is W[2]-hard when parameterized
by k, even if |Σ| = 2 and |B| = 1.
Lemma 3.2. Dominating Set ≤F P T Pattern Identification.

3

G

1
1
1
1
1

1
1
1
0
0

1
1
1
0
0

1
0
0
1
1

1
0
0
1
1

B

0

0

0

0

0

2
→

1
5

4
P = {1 ∗ ∗ ∗ ∗}

Figure 1: An example of the reduction used in Lemma 3.2 with k = 1. The
dominating set is highlighted in red, and the correspond set of patterns (a
singleton) is shown.
Proof. Let (G, k) be an instance of Dominating Set. Let n = |V (G)| and
assume V (G) = {1, . . . , n}. We construct an instance (Σ, G, B, k) as follows:
1. Σ = {1, 0},
11

2. G = {g1 , . . . , gn } where for each i, gi ∈ Σn where for every j, gi [j] = 1
if ij ∈ E(G) or i = j and gi [j] = 0 otherwise,
3. B = {0n }.
An example of the reduction is given in Figure 1.
Claim 3.3. If (G, k) is a Yes instance of Dominating Set then (Σ, G, B, k)
is a Yes instance of Pattern Identification.
Let D ⊆ V (G) with |D| ≤ k be a dominating set witnessing that (G, k) is a
Yes instance. We can construct a witness set of patterns P with |P | = |D|
such that P → (G, B). For each i ∈ D, we create a pattern pi where pi [i] = 1
and pi [j] = ∗ for all j 6= i.
As D is a dominating set, for every vertex j ∈ V (G) there is a vertex i ∈ D
such that ij ∈ E(G). Then for string gj ∈ G, pattern pi is compatible with
gj as by construction gj [i] = 1. Therefore for every string g ∈ G there exists
p ∈ P such that p → g.
Moreover there is no p ∈ P such that p → b where b ∈ B. As B consists of
the single string b = 0n and for each p ∈ P exactly one element is neither 0
nor ∗ there is one position where the pattern does not match b.
Thus (Σ, G, B, k) is a Yes instance.
Claim 3.4. If (Σ, G, B, k) is a Yes instance of Pattern Identification
then (G, k) is a Yes instance of Dominating Set
Let P with |P | ≤ k be the witness set of patterns that (Σ, G, B, k) is a Yes
instance. Inductively, we may assume that every p ∈ P is compatible with
at least one element of G, if not, P \ {p} constitutes an alternate witness.
First we note that no p ∈ P can consist of only ∗ and 0 symbols, as this
would be compatible with the single element of B. Therefore each p ∈ P has
at least one i such that p[i] = 1.
Consider a p ∈ P , and the corresponding set of vertices Vp (i.e. each position
i where p[i] = 1). Let gj ∈ G be a string such that p → gj . By construction
for every i ∈ Vp , ij ∈ E(G). Let Vp→g be the set of vertices corresponding
to the set Gp ⊆ G where p → Gp . Each vertex j ∈ Vp→g is adjacent (or
identical) to every vertex in Vp . Thus we may select arbitrarily a single
vertex from Vp to be in the dominating set D.
Thus we have D with |D| ≤ |P | ≤ k, where every vertex in V (G) is adjacent
(or identical) to some vertex in D. Therefore (G, k) is a Yes instance.
The construction can be clearly performed in fpt time (in fact, polynomial
time), and the lemma follows.
Proof of Theorem 3.1. The theorem follows immediately from Lemma 3.2.

12

The structure of the reduction then gives the following:
Corollary 3.5. PI with Small Patterns is W[2]-complete when parameterized by k and NP-complete even when s = 1, |Σ| = 2 and |B| = 1.
Proof. The W[2]-hardness is apparent from the proof of Lemma 3.2 (in fact
the restriction would make the proof simpler). To show containment in W[2],
we reduce PI with Small Patterns to MC(Σ2,1 ). The first-order structure is equipped with four unary relations N , Σ, G and B and a binary
function symbol C. Each string is represented by an integer, according to an
arbitrary fixed ordering. Gi is true if string i is in G, Bi is true if string i is in
B. Σσ is true if σ ∈ Σ and N i is true if i ∈ N. The function C : N × N → Σ
is defined Cij = σ if σ is the jth symbol of string i.
We
now
provide
the
first-order
formula
expressing
PI with Small Patterns:
^
∃i1,1 , . . . , ik,s , c1,1 , . . . , ck,s ∀j((
N il,b )∧
l∈[k],b∈[s]

(

^

Σcl,b )∧

l∈[k],b∈[s]

_ ^
(Gj → ( (
Cjil,b = cl,b )))∧
l∈[k] b∈[s]

(Bj → (

^ _
(
Cjil,b 6= cl,b ))))

l∈[k] b∈[s]

The formula states that a solution to PI with Small Patterns consists
of k sets of s symbols along with positions such that for each string in G, for
at least one set of symbols, the string is compatible and for each string in B
no set of symbols is compatible.
Containment in NP can be demonstrated by the usual polynomial verification
approach (indeed in much the same format as the above formula).
Corollary 3.6. Pattern Identification has no constant factor fptapproximation algorithm unless FPT = W[2] and there exists a c ≥ 0 such
that Pattern Identification has no c · log n polynomial time approximation algorithm unless P = NP, even when |Σ| = 2 and the optimization goal
is min k.
Proof. As Dominating Set has no constant factor fpt-approximation [8]
unless FPT = W[2] and no c · log n polynomial time approximation [26] for
some c > 0 unless P = NP and the reduction of Lemma 3.2 is a strict
polynomial-time reduction, the corollary follows.
13

Given the construction in the proof of Lemma 3.2, we can deduce that one
source of complexity might be the freedom (unboundedness) in the alphabet and the structure of the strings. We demonstrate that restricting these
parameters is fruitless from a computational complexity perspective.
Corollary 3.7. PI with Small Strings is NP complete even when |Σ| =
2, d = 4, s = 1 and |B| = 1.
Proof. As Dominating Set is NP-complete on planar graphs of maximum
degree 3 [17], the number of 1s in each string in the construction of the proof
of Lemma 3.2 is at most 4, where we take the base symbol to be 0.
This result also demonstrates the following:
Lemma 3.8. PI with Large Patterns and Small Strings and
PI with Large Patterns are both NP-complete even when |Σ| = 2, d = 4,
r = 9 and |B| = 1.
Proof. Following Corollary 3.7, we can see from the construction given in the
proof of Lemma 3.2 that for each p ∈ P , instead of setting p[i] = ∗ for each
i not in the dominating set, we can choose r to be nine, and set p[i] := 1 if i
is in the dominating set, p[j] = ∗ for the at most three values of j such that
ij ∈ E(G) and the at most six additional values of j at distance two4 from i,
and p[l] = 0 for all other l ∈ {1, . . . , n}. For the reverse argument, we have
similar conditions as before, at least one symbol of each pattern must be a
1 and at most four can be 1s. With at most nine ∗ symbols, the pattern is
compatible with all the strings that the corresponding vertex dominates, and
all other symbols in these strings are 0.
Corollary 3.9. The following are true:
1. PI with Large Patterns and Small Strings
is
para-NPcomplete when parameterized by |Σ| + d + r + |B|.
2. PI with Large Patterns is para-NP-complete when parameterized
by |Σ| + r + |B|.
3. PI with Small Patterns and Small Strings
is
para-NPcomplete when parameterized by |Σ| + d + s + |B|.
4. PI with Small Patterns is para-NP-complete when parameterized
by |Σ| + s + |B|.
4

As G has maximum degree three, each neighbor of i has at most two other neighbors,
so the patterns representing each of these neighbors has a 1 in the ith position, a 1 for its
own position and two other 1s. Therefore we need only three ∗ symbols for the neighbors
themselves, and two more per neighbor for the distance two neighborhood.

14

Proof. The result are obtained as follows:
1. Lemma 3.8 gives NP-completeness with fixed |Σ|, d, r and |B|. With
Corollary 2.16 from [16], the result follows.
2. The preservation of hardness when taking subsets of a set of parameters
gives the result from 1.
3. Corollary 3.7 shows NP-completeness with fixed |Σ|, d, s and |B|.
Corollary 2.16 from [16] completes the result.
4. The result follows immediately from 3.

We note that Dominating Set is in FPT for graphs of bounded degree, so
we do not obtain a W[2]-hardness result. However we can tighten this result
a little further:
Theorem 3.10. Pattern Identification is NP-complete and APX-hard
even when Σ = {0, 1} and all strings have at most two symbols as 1 (equiv.
at most two symbols as 0) and |B| = 1.
Lemma 3.11. Vertex Cover ≤P Pattern Identification.

3

1
0
0
0
1
0

0
1
0
0
1
0

0
0
1
0
0
1

0
0
0
1
0
1

B

0

0

0

0

0

2
→

1
5

G

1
1
1
1
0
0

4
P = {1 ∗ ∗ ∗ ∗, ∗1 ∗ ∗∗, ∗ ∗ ∗1∗}

Figure 2: An example of the reduction used in Lemma 3.11 with k = 3.
The vertex cover is highlighted in red, and the correspond set of patterns is
shown.
Proof. Given an instance (G, k) of Vertex Cover with V (G) = {1, . . . , n},
we construct an instance (Σ, G, B, k) of Pattern Identification as follows:
15

1. Σ = {0, 1}.
2. G = {gij | ij ∈ E(G)} with gij ∈ Σn where gij [i] = gij [j] = 1 and
gij [u] = 0 for u 6= i, j.
3. B = {0n }.
Clearly this construction can be performed in polynomial time. The construction is illustrated in Figure 2.
Claim 3.12. If (G, k) is a Yes instance of Vertex Cover then (Σ, G, B, k)
is a Yes instance of Pattern Identification.
Let V 0 ⊆ V (G) where |V 0 | ≤ k be a vertex cover witnessing that (G, k) is
a Yes instance of Vertex Cover. We construct a set of patterns P with
|P | = |V 0 | that is a solution for (Σ, G, B, k) where for each i ∈ V 0 there
is a pattern pi ∈ P with pi [i] = 1 and pi [j] = ∗ for j 6= i. For each edge
ij ∈ E(G), either i ∈ V 0 or j ∈ V 0 (or both). Therefore for the string gij
corresponding to ij, we have either pi ∈ P or pj ∈ P such that pi → gij or
pj → gij . Hence P → G. Moreover there is no pi ∈ P such that pi → b
where b is the single element of B as each pi , by construction, contains a
1, whereas b consists of only 0s. Therefore (Σ, G, B, k) is a Yes instance of
Pattern Identification.
Claim 3.13. If (Σ, G, B, k) is a Yes instance of Pattern Identification
then (G, k) is a Yes instance of Vertex Cover.
Let P with |P | ≤ k be the set of patterns witnessing the fact that (Σ, G, B, k)
is a Yes instance of Pattern Identification. We may assume without
loss of generality that for every p ∈ P , there exists some g ∈ G such that
p → g. Each p ∈ P must contain at least one 1, otherwise p → b where b is
the single element of B. No p ∈ P can contain more than two 1s, as there
exists g ∈ G such that p → g, and every such g has exactly two 1s. We note
that if a pattern p has two 1s, then there is exactly one g ∈ G such that
p → g.
Let P1 ⊆ P be the set of patterns with exactly one 1 and P2 ⊆ P be the
set of patterns with exactly two 1s. We have P1 ∪ P2 = P . We construct a
vertex cover V 0 ⊆ V (G) with |V 0 | ≤ |P | as follows:
1. for each p ∈ P1 add i to V 0 where p[i] = 1,
2. for each p ∈ P2 where p[i] = p[j] = 1, arbitrarily add one of i or j to
V 0.
Consider every edge ij ∈ E(G), then for the corresponding gij ∈ G there
exists a p ∈ P such that p → gij . As each p has at least one 1, this 1 must
be at position i or j (or both). Therefore i or j is in V 0 (or perhaps both),
therefore V 0 forms a valid vertex cover for G.
16

Proof of Theorem 3.10. The NP-hardness follows from Lemma 3.11. The
containment in NP follows from the usual verification algorithm. The
APX-hardness follows as the reduction of Lemma 3.11 is strict and
Vertex Cover is APX-hard [20].
Finally, as restricting the alphabet did not reduce the complexity, we consider
the case where the strings themselves are short. Again the problem is hard,
but we note that to achieve this reduction we relax the bound on Σ (or in
Parameterized Complexity terms, |Σ| is no longer a parameter – if |Σ| is a
parameter, the problem is in FPT).
Theorem 3.14. PI with Small Strings is NP-complete even when n =
4, d = 4 and |B| = 1.
Lemma 3.15. Planar Vertex Cover ≤P PI with Small Strings
even when the length of strings is restricted to 4.

3

σ2
σ6
σ4
σ6
σ2
σ4

σ6
σ3
σ6
σ5
σ3
σ5

σ6
σ6
σ6
σ6
σ6
σ6

B

σ6

σ6

σ6

σ6

2
→

1
5

G

σ1
σ1
σ1
σ1
σ6
σ6

4
P = {σ1 ∗ ∗∗, ∗σ2 ∗ ∗, ∗σ4 ∗ ∗}

Figure 3: An example of the reduction used in Lemma 3.15 with k = 3.
The vertex cover is highlighted in red, and the correspond set of patterns
is shown. Note the difference with the reduction in Lemma 3.11, here the
position encodes the coloring and the symbols encode the edges, whereas
previously the string more directly encode the graph.
Proof. Let (G, k) be an instance of Planar Vertex Cover. We assume
without loss of generality that V (G) = {1, . . . , n}. As G is planar, we can
compute a proper 4-coloring in polynomial time [2]. Let C : V (G) →
{1, 2, 3, 4} be such a coloring. We construct an instance (Σ, G, B, k 0 , d) of
PI with Small Strings as follows:
1. Σ = {σ1 , . . . , σn+1 }.
17

2. G = {gij | ij ∈ E(G)} where for k ∈ {1, . . . , 4} we set


if C(i) = k
σ i
gij [k] := σj
if C(j) = k


σn+1 otherwise.
4
}.
3. B = {σn+1
4. d = 4.

We note that as C is a proper coloring, C(i) 6= C(j) for any ij ∈ E(G).
Moreover for i ∈ V (G), σi only appears as the C(i)th symbol in any string.
The construction can clearly be performed in polynomial time. The construction is illustrated in Figure 3.
Claim 3.16. If (G, k) is a Yes instance of Planar Vertex Cover then
(Σ, G, B, k, d) is a Yes instance of PI with Small Strings.
Let V 0 ⊆ V (G) with |V 0 | ≤ k be a vertex cover witnessing that (G, k) is a
Yes instance of Planar Vertex Cover. We construct a set P with |P | =
|V 0 | ≤ k of patterns that forms a solution for (Σ, G, B, k, d) in the following
manner: for each i ∈ V 0 , we add the pattern pi to P where pi [C(i)] = σi
and all other symbols in pi are ∗. No pattern in P is compatible with the
singleton element of B, as each has a symbol σi with 1 ≤ i ≤ n. For every
edge ij ∈ E(G), at least one of i and j is in V 0 . Without loss of generality
assume that i ∈ V 0 . By construction the string gij is compatible with the
pattern pi ∈ P , therefore every string in G is compatible with some pattern
in P .
Claim 3.17. If (Σ, G, B, k, d) is a Yes instance of PI with Small Strings
then (G, k) is a Yes instance of Planar Vertex Cover.
Let P with |P | ≤ k be a set of patterns such that P → (G, B). As before we
may assume that P is minimal in the sense that each pattern is compatible
with some string in G. Each p ∈ P must have at least one symbol drawn from
the set {σ1 , . . . , σn }, otherwise p → B. No pattern p ∈ P can have more than
two symbols from {σ1 , . . . , σn }, otherwise p 6→ G. As before, we partition P
into P1 , the subset of patterns with one symbol from {σ1 , . . . , σn }, and P2 ,
the subset of patterns with two symbols from {σ1 , . . . , σn }. We construct a
vertex cover V 0 ⊆ V (G) for G with |V 0 | ≤ |P | ≤ k as follows:
• for each p ∈ P1 add i to V 0 if p[C(i)] = σi ,
• for each p ∈ P2 where p[C(j)] = σj and p[C(i)] = σi , arbitrarily add
either i or j to V 0 .

18

Consider every edge ij ∈ E(G). The string gij is compatible with some
pattern p ∈ P , therefore at least one of i and j is in V 0 , thus V 0 forms a
proper vertex cover for G.
Proof of Theorem 3.14. The construction used in the proof of Lemma 3.15
has the required structural properties. Again containment in NP is apparent
from the usual verification algorithm techniques.
Corollary 3.18. PI with Small Strings is para-NP-complete when parameterized by n + d + |B|.
Proof. The corollary follows from Theorem 3.10 and Corollary 2.16 from [16].
3.1. Containment
Although the W[2]-hardness reduction is quite direct, containment of
Pattern Identification when parameterized by k is not apparent. In
fact it is not clear that the problem lies in W[P] or even XP. As the nonparameterized version of the problem is NP-complete, it is at least contained
in para-NP. For PI with Small Patterns we have shown containment in
W[2]. In contrast, for PI with Large Patterns we can show containment
in W∗ [5].
Theorem 3.19. PI with Large Patterns ∈ W∗ [5] when parameterized
by k + r.
Proof. We reduce the problem to MC(Σ∗5,1 ), which is complete for W∗ [5] [7,
16]. We use the same first-order structure as in the proof of Corollary 3.5,
and give a suitable first-order formula:
∃s1 , . . . , sk , i1,1 , . . . , ik,r ∀j
_
_
(Gj → (∃l(
l = sc ∧ ∀b(Cjb = Clb ∨
b = ic,d ))))∧
c∈[k]

(Bj → (∀l(

^

d∈[r]

l = sc ∧ ∃b(Cjb 6= Clb ∧

c∈[k]

(

^

c∈[k]

(N sc ∧

^

^

b 6= ic,d ))))∧

d∈[r]

N ic,d ))

d∈[r]

The formula picks out k indices of strings (implicitly in G, as a choice of
a string from B will fail) and for each of these, r indices which will be the
19

location of the ∗ symbols in the patterns. For each index, if the index selects
a string in G, then one of the patterns is compatible with the string, if it
selects a string in B, no pattern is compatible with the string. We note that
the B clause is in Π2,1 , and hence Σ3,1 , giving the final bound of Σ∗5,1 .
This also places PI with Large Patterns somewhere between W[5] and
W[8] [7]. We note that the above formula could be converted into prenex
form, giving a tighter containment, however the central observation is that
it will be greater than W[2], in contrast to the hardness result and the containment of PI with Small Patterns.
4. Tractable Cases of Pattern Identification Problem
Guided by the results of Section 3, we identify the following cases where the
Pattern Identification problem is tractable.
Theorem 4.1. Pattern Identification is fixed-parameter tractable when
parameterized by |Σ| + n.
Proof. Taking the alphabet size and the string length as a combined parameter gives an immediate kernelization. The total number of strings of length
n over alphabet Σ is |Σ|n . Thus |G| + |B| ≤ |Σ|n .
Theorem 4.2. PI with Small Strings is fixed-parameter tractable when
parameterized by d + |G| + |B|, with a kernel of size O(d · (|G| + |B|)2 ) in both
the total number of symbols across all strings and the size of the alphabet.
Proof. As G and B are d-small, there can be at most d · (|G| + |B|) positions
where any pair of strings in G∪B differ, that is, every other position must be
the base symbol uniformly across all strings. The positions where every string
is identical cannot be of use in generating patterns, thus we may ignore these
positions. This gives restricted sets G0 and B 0 of size |G0 | + |B 0 | ≤ |G| + |B|
containing strings of length at most d · (|G| + |B|). Furthermore this restricts
the number of symbols used from Σ to at most d · (|G| + |B|)2 . Thus we can
restrict our alphabet to these symbols alone, denote this new alphabet by
Σ0 . This gives our required kernel size.
The initial determination of which positions to ignore can be computed in
O(n·(|G|+|B|)) time, thus the kernelization can be performed in polynomial
time.
Theorem 4.3. Pattern Identification is fixed-parameter tractable when
parameterized by k + n.

20

Proof. Let (Σ, G, B, k) be an instance of Pattern Identification. If
(Σ, G, B, k) is a Yes instance, by definition, there exists a P with |P | ≤ k
such that every string g ∈ G must be compatible with at least one p ∈ P .
Therefore given g, the compatible p must consist of, at each position, either
the ∗ symbol, or the symbol at the same position in g.
This
gives
a
direct
bounded
search
tree
algorithm
for
Pattern Identification. At each node in the tree we select an arbitrary g from G. We then branch on all possible patterns p that are
compatible with g, with a new set G := G \ {h ∈ G | p → h} (note that this
removes g from further consideration). If there is a b ∈ B such that p → b,
then we terminate the branch. If we reach depth k and G 6= ∅, we terminate
the branch. Otherwise if at any point we have G = ∅, we answer Yes.
Obviously the depth of the search tree is explicitly bounded by k. The
branching factor is equal to the number of patterns compatible with a string
of length n, which is 2n . The adjustment of G and checks against B at each
node individually take O(n) time, giving O((|G| + |B|) · n) time at each node.
Combined the algorithm takes O(2kn · (|G| + |B|) · n) time, and the theorem
follows.
Theorem 4.4. Pattern Identification is fixed-parameter tractable when
parameterized by |G| + n.
Proof. The search tree approach used in the proof of Theorem 4.3 can also
be adapted to the combined parameter |G| + n. Again we select an arbitrary
g from G. We branch on all possible patterns p that are compatible with g,
of which there are at most 2n , with the new set G := G \ {h ∈ G | p → h}.
If p → b for any b ∈ B, the branch is terminated. When we have G = ∅, we
check whether the collected set P of patterns in that branch. If |P | ≤ k we
answer Yes, otherwise the branch is terminated. If all branches terminate
with no Yes answer, we answer No.
Theorem 4.5. PI with Large Patterns and Small Strings is fixedparameter tractable when parameterized by k + |Σ| + d + r + |B|.
Proof. As each pattern can have at most r many ∗ symbols, every other
symbol in each pattern is fixed. Thus each pattern is compatible with |Σ|r
strings. This limits the number of strings in G to k · |Σ|r .
The tractability then follows from Theorem 4.2.
5. Discussion
Complementing the classification results given above, we now discuss some
related issues. Firstly (in Section 5.1), given the complex parameter
21

landscape introduced, what problems remain unsolved, and which are
the interesting parameterizations for future work? Secondly, we related
Pattern Identification to some similar problems that give some small
intuition as to sources of complexity in Pattern Identification (Section 5.2).
5.1. The Mire of Multivariate Analysis: Untangling the Parameters
The complexity analysis in this work involves a considerable number of parameters and unsurprisingly, there are some relationships between them that
can be identified, allowing a better perspective on the sources of complexity
in the problem, and what cases remain open. The immediately obvious relationships, for non-trivial parameter values5 , are r ≤ n, s ≤ n and d ≤ n. We
also note that k ≤ |G| and k ≤ (|Σ| + 1)n , again for non-trivial values of k.
This helps to unravel some of the relationships present in the results of this
work. We also note that, of course, expanding a list of parameters preserves
tractability, while reducing a list of parameters preserves intractability
A visual summary of the tractable, intractable and open cases for a simplified
parameter space is given in Figure 4. Given the relationships between s, r,
d and n, we reduce the parameter space to k, |Σ|, n, |G| and |B|. Although
this reduces the accuracy of the space, the broad complexity landscape of
the problem becomes more comprehensible.
Speculatively, we may observe that the problem seems to require at least two
parameters for tractability. This is perhaps unsurprising, given the nature of
the input – we need some parametric “handle” on the length of the strings
and another on the number of strings.
From Figure 4 it is clear that the central parameter in the open cases is |G|,
though we note that in the full parameter space, there are combinations of
s, r and d with other parameters for which the complexity remains open6 .
5.2. Ties to Other Problems
The Pattern Identification problem, as would be expected, has ties to
other problems that (can) model the general search for patterns that separate
two sets of data. These ties also illustrate some features of the computational
complexity of the problem.
5

By non-trivial we mean values which differentiate the parameters – for example, if
s > n, s becomes meaningless as any number of ∗ symbols would be allowed, within the
limitation of length n strings.
6
At last hand-count, 72 cases out of the 256 possible parameterizations with these
parameters remain open, compared to 8 with the reduced parameter space.

22

para-NP-complete
W[2]-hard
FPT
Open

|G|

|B|

k

n

|Σ|
Figure 4: Simplified representation of the parameter space and the complexity results. We note in particular that n or at least one of its related
parameters s, r or d seems essential for tractability (though never sufficient).
Given the nature of the input as a set of strings, it is perhaps unsurprising
that at least two parameters are (apparently) needed for tractability. The
obvious open cases are dominated by the parameter |G|.
5.2.1. Set Covering
When the length n of the strings is small, Pattern Identification
can be easily reduced to Set Cover. Given an instance (Σ, G, B, k) of
Pattern Identification, we can generate the set P of all patterns that
are compatible with some string in G. We know that |P | ≤ |G| · 2n . From
P we remove any pattern that is compatible with a string in B. Let P 0 be
the set thus obtained. For each p ∈ P 0 , let sp = {g ∈ G | p → g}, and let
S = {sp | p ∈ P 0 }. Taking G as the base set, (G, S, k) forms an instance
of Set Cover (parameterized by k). This reduction can be performed in
O((|B| + |G|) · |G| · 2n n) time.
This leads to the following theorem:
Theorem 5.1. Pattern Identification ∈ W[2] when n ≤ f (k) · log |I|
where |I| is the overall size of the instance and f (k) is a computable function
of the parameter k.
Proof. The reduction above is a parameterized reduction if 2n ∈ O(g(k)·|I|c )
23

for some computable function g.
It is not clear that we retain W[2]-hardness in this case however, so we unfortunately do not obtain a W[2]-completeness result.
This does give us an immediate approximation algorithm for this case however. As Set Cover has a 1 + log(|S|)-factor linear time approximation
algorithm [22], we obtain a 1 + log(|G|2 · log(|I|) · 2f (k) )-factor fpt-time approximation algorithm.
5.2.2. Feature Set
The k-Feature Set problem bears a strong resemblance to the
Pattern Identification problem7 , except in the k-Feature Set case,
the problem asks for a set of features that separate the “good” examples from
the “bad” rather than a set of patterns. In fact, given a feasible solution for
one problem, we can construct a feasible (but not necessarily optimal) solution to the other.
Given a set I = {i1 , . . . , ik } of indices of columns forming a feature set, we can
construct a set of patterns that separates G and B as follows: for each g ∈ G,
let pg be the pattern where pg [i] = g[i] if i ∈ I and pg [i] = ∗ otherwise. We
note that this gives a set of small patterns (i.e., s = k), however the number
of patterns may be as large as |G|.
Conversely, given a set of patterns P with at most s non-∗ symbols in each
pattern, the set I = {i ∈ [n] | ∃p ∈ P (p[i] 6= ∗)} forms a feature set. Again
we note that the size of the feature set may be as large as |G| · s.
If we consider a variant of PI with Small Patterns where we relax the
constraint on the number of patterns in the solution, it is easy to see that this
problem is in W[2]. This suggests that the solution size plays a significant role
in raising the complexity of the problem from a parameterized perspective.
6. Conclusion and Future Directions
There are a number of open complexity questions prompted by this paper,
three of which we think are particularly interesting.
The central question is of course the precise classification of
Pattern Identification.
Although PI with Small Patterns is
W[2]-complete, the general problem is only W[2]-hard, and the containment
of PI with Large Patterns simply gives a loose upper bound, although
does suggest that the problem is harder than PI with Small Patterns.
7

Indeed, variants of k-Feature Set have also been considered for use in similar applications as Pattern Identification [10].

24

The problem, intuitively, also shares some similarities with p-Hypergraph(Non)-Dominating-Set which is W[3]-complete [7].
p-Colored∗
Hypergraph-(Non)-Dominating-Set however is W [3]-complete [7] and
appears “harder” than Pattern Identification, hence we conjecture:
Conjecture 6.1. Pattern Identification is W[3]-complete when parameterized by k.
There are also some interesting parameterizations for which the complexity
remains open:
• PI with Small Strings parameterized by k + |Σ| + d, and
• PI with Large Patterns and Small Strings parameterized by
k + d + r.
Turning to the parameter |G|, results for the following combinations of parameters would also close some of the significant open cases:
• Pattern Identification parameterized by k + |Σ| + |G|,
• Pattern Identification parameterized by |G| + |Σ| + |B|, and
• Pattern Identification parameterized by k + |B| + |G|.
As a matter of prognostication, we would guess that the first of these is in
FPT, and the latter two are hard for some level of the W-hierarchy, but as
yet have no strong evidence for these claims.
7. Acknowledgements
PM acknowledges funding of his research by the Australian Research Council
(ARC, http://www.arc.gov.au/) grants Future Fellowship FT120100060 and
Discovery Project DP140104183.
8. References
References
[1] Dana Angluin. Finding patterns common to a set of strings. Journal of
Computer and System Sciences, 21(1):46–62, 1980.

25

[2] Kenneth Appel and Wolfgang Haken. Every Planar Map is FourColorable, volume 98 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1989. With the collaboration of J.
Koch.
[3] Robert Bredereck, Thomas Köhler, André Nichterlein, Rolf Niedermeier,
and Geevarghese Philip. Using patterns to form homogeneous teams.
Algorithmica, 71:517–538, 2015.
[4] Robert Bredereck, André Nichterlein, and Rolf Niedermeier. Patternguided k-anonymity. Algorithms, 6:678–701, 2013.
[5] Laurent Bulteau, Falk Hüffner, Christian Komusiewicz, and Rolf Niedermeier. Multivariate algorithmics for NP-hard string problems. Bulletin
of the EACTS, 114, 2014.
[6] Adam Cannon and Lenore Cowen. Approximation algorithms for the
class cover problem. Annals of Mathematics and Artificial Intelligence,
40(3-4):215–224, 2004.
[7] Yijia Chen, Jörg Flum, and Martin Grohe. An analysis of the W∗ hierarchy. The Journal of Symbolic Logic, 72(2):513–534, 2007.
[8] Yijia Chen and Bingkai Lin. The constant inapproximability of the
parameterized dominating set problem. CoRR, abs/1511.00075, 2015.
[9] Carlos Cotta and Pablo Moscato. The k-Feature Set problem is W[2]complete. Journal of Computer and System Sciences, 67(4):686–690,
2002.
[10] Carlos Cotta and Pablo Moscato. The parameterized complexity of
multiparent recombination. In Proceedings of the 6th Metaheuristics
International Conference (MICS2005), pages 237–242, 2005.
[11] Pierluigi Crescenzi. A short guide to approximation preserving reductions. In Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, pages 262–273. IEEE Computer Society, 1997.
[12] Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, and Lusheng Wang. A
ptas for distinguishing (sub)string selection. In Proceedings of the 29th
International Colloquium on Automata, Languages and Programming,
ICALP ’02, pages 740–751. Springer-Verlag, 2002.
[13] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
26

[14] Rodney G. Downey, Michael R. Fellows, and Udayan Taylor. The parameterized complexity of relational database queries and an improved
characterization of W[1]. In Douglas S. Bridges, Cristian S. Calude,
Jeremy Gibbons, Steve Reeves, and Ian H. Witten, editors, First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, DMTCS 1996, Auckland, New Zealand, December, 9-13,
1996, pages 194–213. Springer-Verlag, Singapore, 1996.
[15] Michael R. Fellows, Jens Gramm, and Rolf Niedermeier. On the parameterized intractability of CLOSEST SUBSTRING size and related
problems. In Helmut Alt and Afonso Ferreira, editors, Proceedings of
the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2002), volume 2285 of Lecture Notes in Computer Science,
pages 262–273. Springer, 2002.
[16] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts
in Theoretical Computer Science. An EATCS Series. Springer, 2006.
[17] M. R. Garey and D. S. Johnson. Computers and Intractability – A
Guide to the Theory of NP–completeness. Freeman and Company, San
Francisco, 1979.
[18] Jens Gramm, Jiong Guo, and Rolf Niedermeier. Parameterized intractability of distinguishing substring selection. Theory of Computing
Systems, 39(4):545–560, 2006.
[19] Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Fixed-parameter
algorithms for CLOSEST STRING and related problems. Algorithmica,
37(1):25–42, 2003.
[20] J. Håstad. Some optimal inapproximability results. In Proceedings of
the 29th ACM Symposium on the Theory of Computing (STOC), pages
1–10, 1997.
[21] Danny Hermelin and Liat Rozenberg. Parameterized complexity analysis
for the closest string with wildcards problem. Theoretical Computer
Science, 600:11–18, 2015.
[22] D. S. Johnson. Approximation algorithms for combinatorial problems.
Journal of Computer and System Sciences, pages 256–278, 1974.
[23] Michael Kearns and Leonard Pitt. A polynomial-time algorithm for
learning k–variable pattern languages from examples. In Proceedings

27

of the 2nd Annual ACM Workshop on Computational Learning Theory,
pages 57–71, 1991.
[24] Ming Li, Bin Ma, and Lusheng Wang. On the closest string and substring
problems. Journal of the ACM, 49(2):157–171, March 2002.
[25] Dániel Marx. Parameterized complexity and approximation algorithms.
The Computer Journal, 51(1):60–78, 2008.
[26] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree
test, and a sub-constant error-probability PCP characterization of NP.
In Proceedings of the 29th ACM Symposium on the Theory of Computing
(STOC), pages 475–484, 1997.

28

Parameter

Complexity

k + |Σ| + |B|
k + |Σ| + s + |B|
n + d + |B|
|Σ| + d + r + |B|
|Σ| + d + s + |B|
d + |G| + |B|
|Σ| + n
k+n
|G| + n
k + |Σ| + d + r + |B|
k + |G| + |B|
|Σ| + |G| + |B|
k + |Σ| + d

W[2]-hard
W[2]-complete
para-NP-complete
para-NP-complete
para-NP-complete
FPT
FPT
FPT
FPT
FPT
Open
Open
Open

Theorem
3.1
3.5
3.18
3.9
3.9
4.2
4.1
4.3
4.4
4.5

Table 1: Summary of the parameterized results of the paper. |Σ| is the size
of the alphabet, n is the length of the strings and patterns, |G| and |B| are
the sizes of the two input string sets, k is the number of patterns, r is the
maximum number of ∗ symbols in a pattern, s is the maximum number of
non-∗ symbols in a pattern and d is the number of ‘non-base’ elements in each
string. Of course the usual inferences apply: tractable cases remain tractable
when expanding the parameter and intractable cases remain intractable when
restricting the parameter. We note that a number of cases remain open, of
which we include some of the more pertinent here, however given the number
of parameters under consideration, we refer the reader to Sections 5.1 and 6
for a proper discussion of the open cases.

29

