text:
\section{Introduction}
\label{sec:intro}

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 there are a large number of formulations of this problem. In this paper we develop a particular formulation, drawn from two central motivations:

\begin{enumerate}
\item multiparent recombination in genetic and evolutionary algorithms, and
\item the construction of explanatory patterns in single-nucleotide polymorphisms related to disease.
\end{enumerate}

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.

\subsection{The Central Problem}
\label{sec: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~\ref{sec:prelims}. Central to the problem is the notion of \emph{pattern}, a string over an alphabet $\Sigma$ which has been augmented with a special symbol $\ast$. A pattern matches a string over $\Sigma$ 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 $\ast$ at that position, \emph{i.e.}{} $\ast$ `matches' any symbol from the alphabet.  The fundamental problem is then, given two sets, $G$ and $B$, of strings over $\Sigma$, 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.

\subsection{Separating Healthy Patterns from Diseased}
\label{sec:motivation_SNP}

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$\footnote{Whether healthy is $G$ and diseased is $B$ or vice versa depends on what information we wish the set of patterns to extract.}. A SNP has several alleles of which an individual has two. The individual may thus be homozygous in any of the alleles, or heterozygous with any choice of pairs of alleles, giving the underlying alphabet $\Sigma$.

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, \emph{i.e.}, evolutionary algorithms.

\subsection{Patterns in Multiparent Recombination}
\label{sec:motivation_GA}

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 \emph{schemata}\footnote{We use the third declension neuter form of \emph{schema}, as it matches better the Greek roots of the word.}. 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 $\Sigma$. A \emph{schema} is a string of length $n$ over the same alphabet augmented with the special ``wild card'' character $\ast$, \emph{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 the parents is straightforward. A single schema that is a string of $n$ many $\ast$ 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 $\ast$ 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~\cite{CottaMoscato2005}.

\subsection{Our Contribution}
\label{sec:ccc}

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 \PI{} 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 \Wtwo{}-hard. Even if we take the length of the strings as the parameter, the problem is \paraNP{}-complete. Table~\ref{tab:Results} 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.

\begin{table}[t]
  \centering
  \begin{tabular}{@{}llr@{}} \toprule
   Parameter & Complexity & Theorem\\ \midrule
   $k + \Card{\Sigma} + \Card{B}$       & \Wtwo{}-hard & \ref{thm:PI_W[2]-c}\\
   $k + \Card{\Sigma} + s + \Card{B}$ & \Wtwo{}-complete & \ref{cor:PIp_W[2]-complete}\\
   $n + d + \Card{B}$ & \paraNP{}-complete & \ref{cor:PIS_paraNP-c_short_strings}\\
   $\Card{\Sigma} + d + r + \Card{B}$ & \paraNP{}-complete & \ref{cor:PIP_PIPS_paraNP-c}\\
   $\Card{\Sigma} + d + s + \Card{B}$ & \paraNP{}-complete & \ref{cor:PIP_PIPS_paraNP-c}\\
   $d + \Card{G} + \Card{B}$ & \FPT{} & \ref{PI_FPT_few_small_strings}\\
   $\Card{\Sigma} + n$ & \FPT{} & \ref{thm:PI_FPT_k_Sigma_n}\\
   $k + n$ & \FPT{} & \ref{thm:PI_FPT_k_n}\\
   $\Card{G} + n$ & \FPT{} & \ref{thm:PI_FPT_G_n}\\
   $k + \Card{\Sigma} + d + r + \Card{B}$ & \FPT{} & \ref{thm:PIP_FPT_k_r_Sigma_B}\\
   $k + \Card{G} + \Card{B}$ & Open &\\
   $\Card{\Sigma} + \Card{G} + \Card{B}$ & Open & \\
   $k + \Card{\Sigma} + d$ & Open &\\
   \bottomrule
  \end{tabular}
  \caption{Summary of the parameterized results of the paper. $\Card{\Sigma}$ is the size of the alphabet, $n$ is the length of the strings and patterns, $\Card{G}$ and $\Card{B}$ are the sizes of the two input string sets, $k$ is the number of patterns, $r$ is the maximum number of $\ast$ symbols in a pattern, $s$ is the maximum number of non-$\ast$ 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~\ref{sec:discussion_parameters} and~\ref{sec:conclusion} for a proper discussion of the open cases.}
\label{tab:Results}
\end{table}

\subsection{Related Work}
\label{sec:related}

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.

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~\cite{KearnsPitt1991} 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~\cite{Angluin1980} 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~\cite{BredereckNichterleinNiedermeier2013} 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 $\{\Box,\star\}$. 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 $\star$ 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 \emph{et al.}~\cite{Brederecketal2015} examine forming teams, \emph{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 $\star$ symbol in a pattern now matches any symbol in a string and that the $\Box$ symbol requires homogeneity of the matched strings (\emph{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 \emph{different} input strings and the combined parameter of alphabet size with the length of the strings.

Gramm, Guo and Niedermeier~\cite{Gramm2006} study another similar problem, \textsc{Distinguishing Substring Selection}, where the input is two sets of strings (``good'' and ``bad''), and two integers $d_{g}$ and $d_{b}$ 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 $d_{g}$ and from at least one length $L$ substring for each ``bad'' string is at most $d_{b}$. An extension of the \textsc{Closest String}~\cite{GrammNR03,Li2002} and \textsc{Closest Substring}~\cite{FellowsGN2002} problems, the problem has a ptas~\cite{Deng2002} but they show that it is \Wone{}-hard when parameterized by any combination of the parameters $d_{g}$, $d_{b}$ and the number of ``good'' or ``bad'' strings. Under sufficient restriction they demonstrate an \FPT{} result, requiring a binary alphabet, a `dual' parameter $d'_{g} = L - d_{g}$ and that $d'_{g}$ is optimal in the sense that it is the minimum possible value. We note that, in relation to the problems studied here, although the number of $\ast$ 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 $\ast$ symbols to match the entire set.

Hermelin and Rozenberg introduce a further variant of the \textsc{Closest String} problem~\cite{HermelinR15}, the \textsc{Closest String with Wildcards} problem. The input is a set of strings $\{s_{i}\}$, which may include wildcard characters, and an integer $d$. The goal is to find a string with hamming distance at most $d$ to each $s_{i}$. 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 $\Card{\Sigma}$ 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$, $\Card{\Sigma} + 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 \geq 2$.

Bulteau \emph{et al.}~\cite{BulteauHKN2014} 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, \textsc{Closest String}, \textsc{Closest Substring}, \textsc{Longest Common Subsequence}, \textsc{Shortest Common Supersequence}, \textsc{Shortest Common Superstring}, \textsc{Multiple Sequence Alignment} and \textsc{Minimum Common String}.

Introduced by Cannon and Cowen~\cite{CannonC04}, the \textsc{Class Cover} problem is a geometric relative of \PI{} 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 \DS{}.

\section{Preliminaries and Definitions}
\label{sec:prelims}

\sloppypar We now give the relevant definitions for the complexity analysis that follows. In the reductions we use the well known \DS{} and \VC{} problems. The graphs taken as input for these problems are simple, undirected and unweighted. To assist with notation and indexing, we take the vertex set $V(\mathfrak{G})$ of a graph $\mathfrak{G}$ to be the set $\{1,\ldots ,n\}$. The edge set $E(\mathfrak{G})$ is then a set of pairs drawn from $V(\mathfrak{G})$ and we denote the edge between vertices $i$ and $j$ by $ij$ ($=ji$). The \SetCover{} and \kFS{} problems are also employed. The problems are defined as follows:

\problem{\DS{}}{A graph $\mathfrak{G}$ and an integer $k$.}{Is there a set $V' \subseteq V(\mathfrak{G})$ with $\Card{V'} \leq k$ such that for every $u \in V(\mathfrak{G})$ there exists a $v \in V'$ with $u \in N(v)$?}

\problem{\VC{}}{A graph $\mathfrak{G}$ and an integer $k$.}{Is there a set $V' \subseteq V(\mathfrak{G})$ with $\Card{V'} \leq k$ such that for every $uv \in E(\mathfrak{G})$ we have $u \in V'$ or $v \in V'$?}

\problem{\SetCover{}}{A base set $U$, a set $S \subseteq \mathcal{P}(U)$ and an integer $k$.}{Is there a set $S' \subseteq S$ with $|S'| \leq k$ such that $\bigcup S' = U$?}

\problem{\kFS{}}{An $n\times m$ $0\text{-}1$ matrix $M$, an $n\times 1$ $0\text{-}1$ vector $f$ and an integer $k$.}{Is there a set of indices $I \subseteq \{1,\ldots, m\}$ with $\Card{I} \leq k$ such that for all $a,b$ where $f_{a} \neq f_{b}$ there exist $i \in I$ such that $M_{a,i} \neq M_{b,i}$?}

We note the following key classification results:

\begin{itemize}
\item \sloppypar \DS{} is \NP{}-complete, $O(\log n)\text{-}\APX{}$-hard\footnote{That is there exists some $c > 0$ such that \DS{} has no $c\cdot\log n$-factor approximation algorithm unless $\P{} = \NP{}$.} and \Wtwo{}-complete when parameterized by $k$, the size of the dominating set.
\item \sloppypar \VC{} is \NP{}-complete and \APX{}-hard, and remains \NP{}-complete when the input is a planar graph~\cite{GareyJohnson79}.
\item \sloppypar \SetCover{} is \Wtwo{}-complete when parameterized by the size of the set cover.
\item \sloppypar \kFS{} is \Wtwo{}-complete when parameterized by the size of the feature set~\cite{CottaMoscato2002}.
\end{itemize}

We also employ a parameterized version of the \textsc{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, \emph{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 $\Sigma_{0} = \Pi_{0}$ be the set of unquantified Boolean formulae. The classes $\Sigma_{t}$ and $\Pi_{t}$ for $t > 0$ can be defined recursively as follows:
\begin{align*}
\Sigma_{t} &= \{\exists x_{1}\ldots \exists x_{k}\varphi \mid \varphi \in \Pi_{t-1}\}\\
\Pi_{t} &= \{\forall x_{1} \ldots \forall x_{k} \varphi \mid \varphi \in \Sigma_{t-1}\}
\end{align*}
The class $\Sigma_{t,u}$ is the subclass of $\Sigma_{t}$ where each quantifier block after the first existential block has length at most $u$. We note that trivially $\Pi_{t-1} \subset \Sigma_{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 $\Sigma$ classes is $\Sigma^{\ast}_{t,u}$. Let $\Theta_{0,u}$ be the set of quantifier free formulae, and $\Theta_{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 $\Theta_{t-1,u}$, where the length of each quantifier block is at most $u$. That is, the formulae in $\Theta_{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 $\Sigma^{\ast}_{t,u}$ is the class of formulae of the form $\exists x_{1} \ldots \exists x_{k} \varphi$ where $\varphi \in \Theta_{t-1,u}$ and where $k$ may be greater than $u$.

Thus we refer to the \textsc{Model Checking} problem as \textsc{MC}($\Phi$) where $\Phi$ is the first-order fragment employed. In the parameterized setting, \MCSigmatu{} is \Wt{}-complete for every $u \geq 1$, and \MCSigmaStartu{} is \Wstart{}-complete for every $u \geq 1$. The $\mathsf{W}^{\ast}$-hierarchy is the hierarchy analogous to the $\mathsf{W}$-hierarchy obtained from using \MCSigmaStartu{} as the complete problem instead of \MCSigmatu{}. While it is known that $\Wone{} = \Wstarone{}$ and $\Wtwo{} = \Wstartwo{}$; for $t \geq 3$, the best known containment relationship is $\Wt \subseteq \Wstart{} \subseteq \Wtwotminustwo{}$. For more detail on these results and the full definitions relating to first-order logic and structures we refer the reader to~\cite{FlumGrohe2006}. The $\mathsf{W}^{\ast}$-hierarchy, introduced by Downey, Fellows and Taylor~\cite{DowneyFT96} but more fully explored later~\cite{ChenFlumGrohe2007,FlumGrohe2006} is a parameterized hierarchy which takes into account the Boolean combinations of quantified first-order formulae, but is otherwise similar to the more usual $\mathsf{W}$-hierarchy.

In several of our intractability results we make use of the class \paraNP{}, and a useful corollary due to Flum and Grohe with a detailed explanation in~\cite{FlumGrohe2006} (presented as Corollary 2.16). The class \paraNP{} 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 $(\Pi,\kappa)$, the classical version of the problem $\Pi$ is \NP{}-complete for at least one fixed value of $\kappa$, then $(\Pi, \kappa)$ is \paraNP{}-complete. As may be expected, $\FPT{} = \paraNP{}$ if and only if $\P{} = \NP{}$, thus \paraNP{}-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~\cite{Marx2008} 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~\cite{DowneyFellows2013,FlumGrohe2006}.

We write $A \leq_{FPT} B$ to denote that there exists a parameterized reduction from problem $A$ to problem $B$, and similarly $A \leq_{P} B$ to denote the existence of a polynomial-time many-one reduction from problem $A$ to problem $B$. We also use \emph{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~\cite{Crescenzi1997}.

\begin{definition}[Pattern]\label{def:pattern}
  A \emph{pattern} is a string over an alphabet $\Sigma$ and a special symbol $\ast$.
\end{definition}

Given a string $s \in \Sigma^{\ast}$ and an integer $i$, we denote the $i$th symbol of $s$ by $s[i]$.

\begin{definition}[Compatible]\label{def:compatible}
A pattern $p$ is compatible with a string $g$, denoted $p \to g$, if for all $i$ such that $p[i] \neq \ast$ we have $g[i] = p[i]$. If a pattern and string are not compatible, we write $p \not\to g$. We extend this notation to sets of strings, writing $p \to G$ to denote $\forall g \in G, p \to g$ and $P \to G$ for $\forall g \in G \exists p \in P, p \to g$.
\end{definition}

\begin{definition}[$G$-$B$-Separated Sets]\label{def:separated_sets}
A set $P$ of patterns \emph{$G$-$B$-separates} an ordered pair $(G,B)$ of sets of strings, written $P \to (G,B)$ if
\begin{itemize}
\item $P \to G$, and
\item for every $b \in B$ and $p \in P$ we have $p \not\to b$.
\end{itemize}
\end{definition}

Thus we can state the central problem for this paper:

\problem{\PI{}}{A finite alphabet $\Sigma$, two disjoint sets $G, B \subseteq \Sigma^{n}$  of strings and an integer $k$.}{Is there a set $P$ of patterns such that $\Card{P} \leq k$ and $P \to (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.

\begin{definition}[Small String]\label{def:small_string}
  A string $s$ over an alphabet $\Sigma$ is $d$-\emph{small} if, given an identified symbol $\sigma \in \Sigma$, for exactly $d$ values of $i$, $p[i] \neq \sigma$.

We call $\sigma$ the \emph{base} symbol.

A set of strings $S$ is $d$-small if, given a fixed base symbol all strings in $S$ are $d$-small.
\end{definition}

This restriction on the structure of the input gives further insight into the complexity of \PI{} and is key to some of the tractability results in Section~\ref{sec:easy}. For convenience we phrase a restricted version of the \PI{} problem:

\problem{\PIS{}}{An alphabet $\Sigma$, two disjoint $d$-small sets $G, B \subseteq \Sigma^{n}$, an integer $k$.}{Is there a set $P$ of patterns with $\Card{P} \leq k$ such that $P \to (G,B)$?}

From the perspective of multiparent recombination, minimizing the number of wildcard symbols in each pattern is also an interesting objective:

\problem{\PIP{}}{An alphabet $\Sigma$, two disjoint sets $G, B \subseteq \Sigma^{n}$, integers $k$ and $r$.}{Is there a set $P$ of patterns with $\Card{P} \leq k$ such that $P \to (G,B)$ and for each $p \in P$ the number of $\ast$ symbols in $p$ is at most $r$?}

We implicitly define the obvious intersection of the two restricted problems, \PIPS{}.

From a combinatorial perspective, the inverse problem is also interesting:

\problem{\PIp{}}{An alphabet $\Sigma$, two disjoint sets $G, B \subseteq \Sigma^{n}$, integers $k$ and $s$.}{Is there a set $P$ of patterns with $\Card{P} \leq k$ such that $P \to (G,B)$ and for each $p \in P$ the number of non-$\ast$ symbols in $p$ is at most $s$?}

\section{Hard Cases of the Pattern Identification Problem}
\label{sec:hard}

We first examine the intractable cases of the \PI{} problem. This narrows down the source of the combinatorial complexity of the problem.

\begin{theorem}\label{thm:PI_W[2]-c}
 \sloppypar \PI{} is \Wtwo{}-hard when parameterized by $k$, even if $\Card{\Sigma} = 2$ and $\Card{B} = 1$.
\end{theorem}

\begin{lemma}\label{lemma:DS<=PI}
  $\DS{} \leq_{FPT} \PI{}$.
\end{lemma}

\begin{figure}[htb]
  \centering
  \subfloat{\raisebox{-0.5\height}{\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto]
    \node[draw,circle,fill=red!40] (q_0)                      {$1$};
    \node[draw,circle] (q_1) [above right of=q_0] {$2$};
    \node[draw,circle] (q_2) [above left of=q_0]  {$3$};
    \node[draw,circle] (q_3) [below right of=q_0] {$4$};
    \node[draw,circle] (q_4) [below left of=q_0]  {$5$};

    \path
    (q_0) edge (q_1) edge (q_2) edge (q_3) edge (q_4)
    (q_1) edge (q_2)
    (q_3) edge (q_4);
  \end{tikzpicture}}}\hspace{48pt}$\rightarrow$\hspace{48pt}
  \subfloat{
    \begin{tabular}{c|ccccc}
      \multirow{5}{*}{$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\\
      \midrule
      $B$ & 0 & 0 & 0 & 0 & 0
    \end{tabular}
  }\\
  \subfloat{
    $P = \{1\ast\ast\ast\ast\}$
  }
  \caption{An example of the reduction used in Lemma~\ref{lemma:DS<=PI} with $k=1$. The dominating set is highlighted in red, and the correspond set of patterns (a singleton) is shown.}
  \label{fig:DS_red_example}
\end{figure}

\begin{proof}
Let $(\mathfrak{G},k)$ be an instance of \DS{}. Let $n = \Card{V(\mathfrak{G})}$ and assume $V(\mathfrak{G}) = \{1,\ldots, n\}$. We construct an instance $(\Sigma, G, B, k)$ as follows:
\begin{enumerate}
\item $\Sigma = \{1, 0\}$,
\item $G = \{g_{1},\ldots, g_{n}\}$ where for each $i$, $g_{i} \in \Sigma^{n}$ where for every $j$, $g_{i}[j] = 1$ if $ij \in E(\mathfrak{G})$ or $i = j$ and $g_{i}[j] = 0$ otherwise,
\item $B = \{0^{n} \}$.
\end{enumerate}

An example of the reduction is given in Figure~\ref{fig:DS_red_example}.

\begin{claim}
  If $(G,k)$ is a \textsc{Yes}{} instance of \DS{} then $(\Sigma, G, B, k)$ is a \textsc{Yes}{} instance of \PI{}.
\end{claim}

Let $D \subseteq V(\mathfrak{G})$ with $\Card{D} \leq k$ be a dominating set witnessing that $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance. We can construct a witness set of patterns $P$ with $\Card{P} = \Card{D}$ such that $P \to (G,B)$. For each $i \in D$, we create a pattern $p_{i}$ where $p_{i}[i] = 1$ and $p_{i}[j] = \ast$ for all $j \neq i$.

As $D$ is a dominating set, for every vertex $j \in V(\mathfrak{G})$ there is a vertex $i \in D$ such that $ij \in E(\mathfrak{G})$. Then for string $g_{j} \in G$, pattern $p_{i}$ is compatible with $g_{j}$ as by construction $g_{j}[i] = 1$. Therefore for every string $g \in G$ there exists $p \in P$ such that $p \to g$.

Moreover there is no $p \in P$ such that $p \to b$ where $b \in B$. As $B$ consists of the single string $b = 0^{n}$ and for each $p \in P$ exactly one element is neither $0$ nor $\ast$ there is one position where the pattern does not match $b$.

Thus $(\Sigma, G, B, k)$ is a \textsc{Yes}{} instance.

\begin{claim}
  If $(\Sigma, G, B, k)$ is a \textsc{Yes}{} instance of \PI{} then $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance of \DS{}
\end{claim}

Let $P$ with $\Card{P} \leq k$ be the witness set of patterns that $(\Sigma, G, B, k)$ is a \textsc{Yes}{} instance. Inductively, we may assume that every $p \in P$ is compatible with at least one element of $G$, if not, $P \setminus \{p\}$ constitutes an alternate witness.

First we note that no $p \in P$ can consist of only $\ast$ and $0$ symbols, as this would be compatible with the single element of $B$. Therefore each $p \in P$ has at least one $i$ such that $p[i] = 1$.

Consider a $p \in P$, and the corresponding set of vertices $V_{p}$ (i.e. each position $i$ where $p[i] = 1$). Let $g_{j} \in G$ be a string such that $p \to g_{j}$. By construction for every $i \in V_{p}$, $ij \in E(\mathfrak{G})$. Let $V_{p\to g}$ be the set of vertices corresponding to the set $G_{p} \subseteq G$ where $p \to G_{p}$. Each vertex $j \in V_{p \to g}$ is adjacent (or identical) to every vertex in $V_{p}$. Thus we may select arbitrarily a single vertex from $V_{p}$ to be in the dominating set $D$.

Thus we have $D$ with $\Card{D} \leq \Card{P} \leq k$, where every vertex in $V(\mathfrak{G})$ is adjacent (or identical) to some vertex in $D$. Therefore $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance.

The construction can be clearly performed in fpt time (in fact, polynomial time), and the lemma follows.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:PI_W[2]-c}]
  The theorem follows immediately from Lemma~\ref{lemma:DS<=PI}.
\end{proof}

The structure of the reduction then gives the following:

\begin{corollary}\label{cor:PIp_W[2]-complete}
\sloppypar \PIp{} is \Wtwo{}-complete when parameterized by $k$ and \NP{}-complete even when $s = 1$, $\Card{\Sigma} = 2$ and $\Card{B} = 1$.
\end{corollary}

\begin{proof}
The \Wtwo{}-hardness is apparent from the proof of Lemma~\ref{lemma:DS<=PI} (in fact the restriction would make the proof simpler). To show containment in \Wtwo{}, we reduce \PIp{} to \MCSigmaTwoOne{}. The first-order structure is equipped with four unary relations $N$, $\Sigma$, $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$. $\Sigma\sigma$ is true if $\sigma \in \Sigma$ and $Ni$ is true if $i \in \mathbb{N}$. The function $C:\mathbb{N} \times \mathbb{N} \to \Sigma$ is defined $Cij = \sigma$ if $\sigma$ is the $j$th symbol of string $i$.

We now provide the first-order formula expressing \PIp{}:
\begin{align*}
\exists i_{1,1},\ldots,i_{k,s},c_{1,1},\ldots,c_{k,s}\forall j ((\bigwedge_{l\in[k],b\in[s]} Ni_{l,b}) \wedge\\ (\bigwedge_{l\in[k],b\in[s]}\Sigma c_{l,b}) \wedge\\ (Gj \to (\bigvee_{l\in[k]}(\bigwedge_{b\in[s]}Cji_{l,b} = c_{l,b}))) \wedge\\ (Bj \to (\bigwedge_{l\in[k]}(\bigvee_{b\in[s]}Cji_{l,b} \neq c_{l,b}))))
\end{align*}

The formula states that a solution to \PIp{} 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).
\end{proof}

\begin{corollary}\label{cor:no_fpt_approx}
\sloppypar  \PI{} has no constant factor fpt-approximation algorithm unless $\FPT{} = \Wtwo{}$ and there exists a $c \geq 0$ such that \PI{} has no $c\cdot\log n$ polynomial time approximation algorithm unless $\P{} = \NP{}$, even when $\Card{\Sigma} = 2$ and the optimization goal is $\min k$.
\end{corollary}

\begin{proof}
  As \DS{} has no constant factor fpt-approximation~\cite{ChenLin2015} unless $\FPT{} = \Wtwo{}$ and no $c\cdot\log n$ polynomial time approximation~\cite{RazSafra1997} for some $c > 0$ unless $\P{} = \NP{}$ and the reduction of Lemma~\ref{lemma:DS<=PI} is a strict polynomial-time reduction, the corollary follows.
\end{proof}

Given the construction in the proof of Lemma~\ref{lemma:DS<=PI}, 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.

\begin{corollary}\label{cor:PI_NPc_small_strings_small_alphabet}
\PIS{} is \NP{} complete even when $\Card{\Sigma} = 2$, $d = 4$, $s = 1$ and $\Card{B} = 1$.
\end{corollary}

\begin{proof}
As \DS{} is \NP{}-complete on planar graphs of maximum degree 3~\cite{GareyJohnson79}, the number of $1$s in each string in the construction of the proof of Lemma~\ref{lemma:DS<=PI} is at most 4, where we take the base symbol to be $0$.
\end{proof}

This result also demonstrates the following:

\begin{lemma}\label{lemma:PIP_PIPS_NPc}
\PIPS{} and\\ \PIP{} are both \NP{}-complete even when $\Card{\Sigma} = 2$, $d = 4$, $r = 9$ and $\Card{B} = 1$.
\end{lemma}

\begin{proof}
Following Corollary~\ref{cor:PI_NPc_small_strings_small_alphabet}, we can see from the construction given in the proof of Lemma~\ref{lemma:DS<=PI} that for each $p \in P$, instead of setting $p[i] = \ast$ 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] = \ast$ for the at most three values of $j$ such that $ij \in E(\mathfrak{G})$ and the at most six additional values of $j$ at distance two\footnote{As $\mathfrak{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 $i$th position, a $1$ for its own position and two other $1$s. Therefore we need only three $\ast$ symbols for the neighbors themselves, and two more per neighbor for the distance two neighborhood.} from $i$, and $p[l] = 0$ for all other $l \in \{1,\ldots,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 $1$s. With at most nine $\ast$ symbols, the pattern is compatible with all the strings that the corresponding vertex dominates, and all other symbols in these strings are $0$.
\end{proof}

\begin{corollary}\label{cor:PIP_PIPS_paraNP-c}
The following are true:
  \begin{enumerate}
  \item \PIPS{} is \paraNP{}-complete when parameterized by $\Card{\Sigma} + d + r + \Card{B}$.
  \item \PIP{} is \paraNP{}-complete when parameterized by $\Card{\Sigma} + r + \Card{B}$.
  \item \PIps{} is \paraNP{}-complete when parameterized by $\Card{\Sigma} + d + s + \Card{B}$.
  \item \PIp{} is \paraNP{}-complete when parameterized by $\Card{\Sigma} + s + \Card{B}$.
  \end{enumerate}
\end{corollary}

\begin{proof}
The result are obtained as follows:

\begin{enumerate}
\item Lemma~\ref{lemma:PIP_PIPS_NPc} gives \NP{}-completeness with fixed $\Card{\Sigma}$, $d$, $r$ and $\Card{B}$. With Corollary 2.16 from~\cite{FlumGrohe2006}, the result follows.
\item The preservation of hardness when taking subsets of a set of parameters gives the result from $1$.
\item Corollary~\ref{cor:PI_NPc_small_strings_small_alphabet} shows \NP{}-completeness with fixed $\Card{\Sigma}$, $d$, $s$ and $\Card{B}$. Corollary 2.16 from~\cite{FlumGrohe2006} completes the result.
\item The result follows immediately from $3$.
\end{enumerate}
\end{proof}

\sloppypar We note that \DS{} is in \FPT{} for graphs of bounded degree, so we do not obtain a \Wtwo{}-hardness result. However we can tighten this result a little further:

\begin{theorem}\label{thm:PI_NP-c_small_strings}
  \PI{} is \NP{}-complete and \APX{}-hard even when $\Sigma = \{0,1\}$ and all strings have at most two symbols as $1$ (equiv. at most two symbols as $0$) and $\Card{B} = 1$.
\end{theorem}

\begin{lemma}\label{lem:VC<=PI}
  $\VC{} \leq_{P} \PI{}$.
\end{lemma}

\begin{figure}[htb]
  \centering
  \subfloat{\raisebox{-0.5\height}{\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto]
    \node[draw,circle,fill=red!40] (q_0)                      {$1$};
    \node[draw,circle,fill=red!40] (q_1) [above right of=q_0] {$2$};
    \node[draw,circle] (q_2) [above left of=q_0]  {$3$};
    \node[draw,circle,fill=red!40] (q_3) [below right of=q_0] {$4$};
    \node[draw,circle] (q_4) [below left of=q_0]  {$5$};

    \path
    (q_0) edge (q_1) edge (q_2) edge (q_3) edge (q_4)
    (q_1) edge (q_2)
    (q_3) edge (q_4);
  \end{tikzpicture}}}\hspace{48pt}$\rightarrow$\hspace{48pt}
  \subfloat{
    \begin{tabular}{c|ccccc}
      \multirow{6}{*}{$G$} & 1 & 1 & 0 & 0 & 0\\
      &1&0&1&0&0\\
      &1&0&0&1&0\\
      &1&0&0&0&1\\
      &0&1&1&0&0\\
      &0&0&0&1&1\\
      \midrule
      $B$ & 0 & 0 & 0 & 0 & 0
    \end{tabular}
  }\\
  \subfloat{
    $P = \{1\ast\ast\ast\ast,\;\;\; \ast 1\ast\ast\ast,\;\;\; \ast\ast\ast 1\ast\}$
  }
  \caption{An example of the reduction used in Lemma~\ref{lem:VC<=PI} with $k=3$. The vertex cover is highlighted in red, and the correspond set of patterns is shown.}
  \label{fig:VC_red_example}
\end{figure}

\begin{proof}
Given an instance $(\mathfrak{G},k)$ of \VC{} with $V(\mathfrak{G}) = \{1,\ldots, n\}$, we construct an instance $(\Sigma, G, B, k)$ of \PI{} as follows:
\begin{enumerate}
\item $\Sigma = \{0,1\}$.
\item $G = \{g_{ij} \mid ij \in E(\mathfrak{G})\}$ with $g_{ij} \in \Sigma^{n}$ where $g_{ij}[i] = g_{ij}[j] = 1$ and $g_{ij}[u] = 0$ for $u \neq i,j$.
\item $B = \{0^{n}\}$.
\end{enumerate}

Clearly this construction can be performed in polynomial time. The construction is illustrated in Figure~\ref{fig:VC_red_example}.

\begin{claim}
  If $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance of \VC{} then $(\Sigma,G,B,k)$ is a \textsc{Yes}{} instance of \PI{}.
\end{claim}

Let $V' \subseteq V(\mathfrak{G})$ where $\Card{V'} \leq k$ be a vertex cover witnessing that $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance of \VC{}. We construct a set of patterns $P$ with $\Card{P} = \Card{V'}$ that is a solution for $(\Sigma, G, B, k)$ where for each $i \in V'$ there is a pattern $p_{i} \in P$ with $p_{i}[i] = 1$ and $p_{i}[j] = \ast$ for $j \neq i$. For each edge $ij \in E(\mathfrak{G})$, either $i \in V'$ or $j \in V'$ (or both). Therefore for the string $g_{ij}$ corresponding to $ij$, we have either $p_{i} \in P$ or $p_{j} \in P$ such that $p_{i} \to g_{ij}$ or $p_{j} \to g_{ij}$. Hence $P \to G$. Moreover there is no $p_{i} \in P$ such that $p_{i} \to b$ where $b$ is the single element of $B$ as each $p_{i}$, by construction, contains a $1$, whereas $b$ consists of only $0$s. Therefore $(\Sigma, G, B, k)$ is a \textsc{Yes}{} instance of \PI{}.

\begin{claim}
  If $(\Sigma,G,B,k)$ is a \textsc{Yes}{} instance of \PI{} then $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance of \VC{}.
\end{claim}

Let $P$ with $\Card{P} \leq k$ be the set of patterns witnessing the fact that $(\Sigma,G,B,k)$ is a \textsc{Yes}{} instance of \PI{}. We may assume without loss of generality that for every $p \in P$, there exists some $g \in G$ such that $p \to g$. Each $p \in P$ must contain at least one $1$, otherwise $p \to b$ where $b$ is the single element of $B$. No $p \in P$ can contain more than two $1$s, as there exists $g \in G$ such that $p \to g$, and every such $g$ has exactly two $1$s. We note that if a pattern $p$ has two $1$s, then there is exactly one $g \in G$ such that $p \to g$.

Let $P_{1} \subseteq P$ be the set of patterns with exactly one $1$ and $P_{2} \subseteq P$ be the set of patterns with exactly two $1$s. We have $P_{1} \cup P_{2} = P$. We construct a vertex cover $V' \subseteq V(\mathfrak{G})$ with $\Card{V'} \leq \Card{P}$ as follows:
\begin{enumerate}
\item for each $p \in P_{1}$ add $i$ to $V'$ where $p[i] = 1$,
\item for each $p \in P_{2}$ where $p[i] = p[j] = 1$, arbitrarily add one of $i$ or $j$ to $V'$.
\end{enumerate}
Consider every edge $ij \in E(\mathfrak{G})$, then for the corresponding $g_{ij} \in G$ there exists a $p \in P$ such that $p \to g_{ij}$. 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'$ (or perhaps both), therefore $V'$ forms a valid vertex cover for $\mathfrak{G}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:PI_NP-c_small_strings}]
\sloppypar The \NP{}-hardness follows from Lemma~\ref{lem:VC<=PI}. The containment in \NP{} follows from the usual verification algorithm. The \APX{}-hardness follows as the reduction of Lemma~\ref{lem:VC<=PI} is strict and \VC{} is \APX{}-hard~\cite{Hastad1997}.
\end{proof}

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 $\Sigma$ (or in Parameterized Complexity terms, $\Card{\Sigma}$ is no longer a parameter -- if $\Card{\Sigma}$ is a parameter, the problem is in \FPT{}).

\begin{theorem}\label{thm:PIS_NP-c_short_strings}
\sloppypar \PIS{} is \NP{}-complete even when $n = 4$, $d = 4$ and $\Card{B} = 1$.
\end{theorem}

\begin{lemma}\label{lem:VC<=PIS_short_strings}
\sloppypar $\PVC{} \leq_{P} \PIS{}$ even when the length of strings is restricted to $4$.
\end{lemma}

\begin{figure}[htb]
  \centering
  \subfloat{\raisebox{-0.5\height}{\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto]
    \node[draw,green,circle,fill=red!40,text=black,thick] (q_0)                      {$1$};
    \node[draw,blue,circle,fill=red!40,text=black,thick] (q_1) [above right of=q_0] {$2$};
    \node[draw,yellow,circle,text=black,thick] (q_2) [above left of=q_0]  {$3$};
    \node[draw,blue,circle,fill=red!40,text=black,thick] (q_3) [below right of=q_0] {$4$};
    \node[draw,yellow,circle,text=black,thick] (q_4) [below left of=q_0]  {$5$};

    \path
    (q_0) edge (q_1) edge (q_2) edge (q_3) edge (q_4)
    (q_1) edge (q_2)
    (q_3) edge (q_4);
  \end{tikzpicture}}}\hspace{48pt}$\rightarrow$\hspace{48pt}
  \subfloat{
    \begin{tabular}{c|cccc}
      \multirow{6}{*}{$G$} & $\sigma_{1}$ & $\sigma_{2}$ & $\sigma_{6}$ & $\sigma_{6}$ \\
      &$\sigma_{1}$&$\sigma_{6}$&$\sigma_{3}$&$\sigma_{6}$\\
      &$\sigma_{1}$&$\sigma_{4}$&$\sigma_{6}$&$\sigma_{6}$\\
      &$\sigma_{1}$&$\sigma_{6}$&$\sigma_{5}$&$\sigma_{6}$\\
      &$\sigma_{6}$&$\sigma_{2}$&$\sigma_{3}$&$\sigma_{6}$\\
      &$\sigma_{6}$&$\sigma_{4}$&$\sigma_{5}$&$\sigma_{6}$\\
      \midrule
      $B$ & $\sigma_{6}$ & $\sigma_{6}$ & $\sigma_{6}$ & $\sigma_{6}$
    \end{tabular}
  }\\
  \subfloat{
    $P = \{\sigma_{1}\ast\ast\ast,\;\;\; \ast\sigma_{2}\ast\ast,\;\;\; \ast\sigma_{4}\ast\ast\}$
  }
  \caption{An example of the reduction used in Lemma~\ref{lem:VC<=PIS_short_strings} 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~\ref{lem:VC<=PI}, here the position encodes the coloring and the symbols encode the edges, whereas previously the string more directly encode the graph.}
  \label{fig:planar_VC_red_example}
\end{figure}

\begin{proof}
Let $(\mathfrak{G},k)$ be an instance of \PVC{}. We assume without loss of generality that $V(\mathfrak{G}) = \{1,\ldots, n\}$. As $\mathfrak{G}$ is planar, we can compute a proper 4-coloring in polynomial time~\cite{AppelHaken1989}. Let $C : V(\mathfrak{G}) \rightarrow \{1,2,3,4\}$ be such a coloring.
We construct an instance $(\Sigma, G, B, k', d)$ of \PIS{} as follows:
\begin{enumerate}
\item $\Sigma = \{\sigma_{1},\ldots,\sigma_{n+1}\}$.
\item $G = \{g_{ij} \mid ij \in E(\mathfrak{G})\}$ where for $k \in \{1,\ldots, 4\}$ we set
\[
g_{ij}[k] :=
\begin{cases}
\sigma_{i} & \text{if } C(i) = k\\
\sigma_{j} & \text{if } C(j) = k\\
\sigma_{n+1} & \text{otherwise.}
\end{cases}
\]
\item $B = \{\sigma_{n+1}^{4}\}$.
\item $d = 4$.
\end{enumerate}

We note that as $C$ is a proper coloring, $C(i) \neq C(j)$ for any $ij \in E(\mathfrak{G})$. Moreover for $i \in V(\mathfrak{G})$, $\sigma_{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~\ref{fig:planar_VC_red_example}.

\begin{claim}
  If $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance of \PVC{} then $(\Sigma, G, B, k, d)$ is a \textsc{Yes}{} instance of \PIS{}.
\end{claim}

Let $V' \subseteq V(\mathfrak{G})$ with $\Card{V'} \leq k$ be a vertex cover witnessing that $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance of \PVC{}. We construct a set $P$ with $\Card{P} = \Card{V'} \leq k$ of patterns that forms a solution for $(\Sigma, G, B, k, d)$ in the following manner: for each $i \in V'$, we add the pattern $p_{i}$ to $P$ where $p_{i}[C(i)] = \sigma_{i}$ and all other symbols in $p_{i}$ are $\ast$.
No pattern in $P$ is compatible with the singleton element of $B$, as each has a symbol $\sigma_{i}$ with $1 \leq i \leq n$. For every edge $ij \in E(\mathfrak{G})$, at least one of $i$ and $j$ is in $V'$. Without loss of generality assume that $i \in V'$. By construction the string $g_{ij}$ is compatible with the pattern $p_{i} \in P$, therefore every string in $G$ is compatible with some pattern in $P$.

\begin{claim}
  If $(\Sigma, G, B, k, d)$ is a \textsc{Yes}{} instance of \PIS{} then $(\mathfrak{G},k)$ is a \textsc{Yes}{} instance of \PVC{}.
\end{claim}

Let $P$ with $\Card{P} \leq k$ be a set of patterns such that $P \to (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 \in P$ must have at least one symbol drawn from the set $\{\sigma_{1}, \ldots, \sigma_{n}\}$, otherwise $p\to B$. No pattern $p \in P$ can have more than two symbols from $\{\sigma_{1}, \ldots, \sigma_{n}\}$, otherwise $p \not\to G$. As before, we partition $P$ into $P_{1}$, the subset of patterns with one symbol from $\{\sigma_{1}, \ldots, \sigma_{n}\}$, and $P_{2}$, the subset of patterns with two symbols from $\{\sigma_{1}, \ldots, \sigma_{n}\}$. We construct a vertex cover $V' \subseteq V(\mathfrak{G})$ for $\mathfrak{G}$ with $\Card{V'} \leq \Card{P} \leq k$ as follows:
\begin{itemize}
\item for each $p \in P_{1}$ add $i$ to $V'$ if $p[C(i)] = \sigma_{i}$,
\item for each $p \in P_{2}$ where $p[C(j)] = \sigma_{j}$ and $p[C(i)] = \sigma_{i}$, arbitrarily add either $i$ or $j$ to $V'$.
\end{itemize}
Consider every edge $ij \in E(\mathfrak{G})$. The string $g_{ij}$ is compatible with some pattern $p \in P$, therefore at least one of $i$ and $j$ is in $V'$, thus $V'$ forms a proper vertex cover for $\mathfrak{G}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:PIS_NP-c_short_strings}]
The construction used in the proof of Lemma~\ref{lem:VC<=PIS_short_strings} has the required structural properties. Again containment in \NP{} is apparent from the usual verification algorithm techniques.
\end{proof}

\begin{corollary}\label{cor:PIS_paraNP-c_short_strings}
\sloppypar \PIS{} is \paraNP{}-complete when parameterized by $n + d + \Card{B}$.
\end{corollary}

\begin{proof}
The corollary follows from Theorem~\ref{thm:PI_NP-c_small_strings} and Corollary 2.16 from~\cite{FlumGrohe2006}.
\end{proof}

\subsection{Containment}
\label{sec:containment}

Although the \Wtwo{}-hardness reduction is quite direct, containment of \PI{} when parameterized by $k$ is not apparent. In fact it is not clear that the problem lies in \WP{} or even \XP{}. As the non-parameterized version of the problem is \NP{}-complete, it is at least contained in \paraNP{}. For \PIp{} we have shown containment in \Wtwo{}. In contrast, for \PIP{} we can show containment in \Wstarfive{}.

\begin{theorem}\label{thm:PIP_in_W*[5]}
$\PIP{} \in \Wstarfive$ when parameterized by $k+r$.
\end{theorem}

\begin{proof}
We reduce the problem to \MCSigmaStarFiveOne{}, which is complete for \Wstarfive{}~\cite{ChenFlumGrohe2007,FlumGrohe2006}. We use the same first-order structure as in the proof of Corollary~\ref{cor:PIp_W[2]-complete}, and give a suitable first-order formula:

  \begin{align*}
    &\exists s_{1},\ldots,s_{k},i_{1,1},\ldots,i_{k,r}\forall j\\
    &(Gj \rightarrow (\exists l (\bigvee_{c \in [k]} l = s_{c} \wedge \forall b (Cjb = Clb \vee \bigvee_{d \in [r]} b = i_{c,d})))) \wedge\\
    &(Bj \rightarrow (\forall l (\bigwedge_{c \in [k]} l = s_{c} \wedge \exists b (Cjb \neq Clb \wedge \bigwedge_{d \in [r]} b \neq i_{c,d})))) \wedge\\
    &(\bigwedge_{c \in [k]} (Ns_{c} \wedge \bigwedge_{d \in [r]} Ni_{c,d}))\\
  \end{align*}

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 location of the $\ast$ 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 $\Pi_{2,1}$, and hence $\Sigma_{3,1}$, giving the final bound of $\Sigma^{\ast}_{5,1}$.
\end{proof}

This also places \PIP{} somewhere between \Wfive{} and \Weight{}~\cite{ChenFlumGrohe2007}. 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 \Wtwo{}, in contrast to the hardness result and the containment of \PIp{}.

\section{Tractable Cases of Pattern Identification Problem}
\label{sec:easy}

Guided by the results of Section~\ref{sec:hard}, we identify the following cases where the \PI{} problem is tractable.

\begin{theorem}\label{thm:PI_FPT_k_Sigma_n}
\sloppypar \PI{} is fixed-parameter tractable when parameterized by $\Card{\Sigma} + n$.
\end{theorem}

\begin{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 $\Sigma$ is $\Card{\Sigma}^{n}$. Thus $\Card{G} + \Card{B} \leq \Card{\Sigma}^{n}$.
\end{proof}

\begin{theorem}\label{PI_FPT_few_small_strings}
\sloppypar \PIS{} is fixed-parameter tractable when parameterized by $d + \Card{G} + \Card{B}$, with a kernel of size $O(d\cdot(\Card{G} + \Card{B})^{2})$ in both the total number of symbols across all strings and the size of the alphabet.
\end{theorem}

\begin{proof}
 As $G$ and $B$ are $d$-small, there can be at most $d\cdot(\Card{G} + \Card{B})$ positions where any pair of strings in $G \cup 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 $G'$ and $B'$ of size $\Card{G'} + \Card{B'} \leq \Card{G} + \Card{B}$ containing strings of length at most $d\cdot(\Card{G} + \Card{B})$. Furthermore this restricts the number of symbols used from $\Sigma$ to at most $d\cdot(\Card{G} + \Card{B})^{2}$. Thus we can restrict our alphabet to these symbols alone, denote this new alphabet by $\Sigma'$. This gives our required kernel size.

The initial determination of which positions to ignore can be computed in $O(n \cdot(\Card{G} + \Card{B}))$ time, thus the kernelization can be performed in polynomial time.
\end{proof}

\begin{theorem}\label{thm:PI_FPT_k_n}
\sloppypar \PI{} is fixed-parameter tractable when parameterized by $k + n$.
\end{theorem}

\begin{proof}
Let $(\Sigma, G, B, k)$ be an instance of \PI{}. If $(\Sigma, G, B, k)$ is a \textsc{Yes}{} instance, by definition, there exists a $P$ with $\Card{P} \leq k$ such that every string $g \in G$ must be compatible with at least one $p \in P$. Therefore given $g$, the compatible $p$ must consist of, at each position, either the $\ast$ symbol, or the symbol at the same position in $g$.

\sloppypar This gives a direct bounded search tree algorithm for $\PI{}$. 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 \setminus \{h \in G \mid p \to h\}$ (note that this removes $g$ from further consideration). If there is a $b \in B$ such that $p \to b$, then we terminate the branch. If we reach depth $k$ and $G \neq \emptyset$, we terminate the branch. Otherwise if at any point we have $G = \emptyset$, we answer \textsc{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 $2^{n}$. The adjustment of $G$ and checks against $B$ at each node individually take $O(n)$ time, giving $O((\Card{G} + \Card{B})\cdot n)$ time at each node. Combined the algorithm takes $O(2^{kn}\cdot(\Card{G} + \Card{B})\cdot n)$ time, and the theorem follows.

\end{proof}

\begin{theorem}\label{thm:PI_FPT_G_n}
  \sloppypar \PI{} is fixed-parameter tractable when parameterized by $\Card{G} + n$.
\end{theorem}

\begin{proof}
The search tree approach used in the proof of Theorem~\ref{thm:PI_FPT_k_n} can also be adapted to the combined parameter $\Card{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 $2^{n}$, with the new set $G :=  G \setminus \{h \in G \mid p \to h\}$. If $p \to b$ for any $b \in B$, the branch is terminated. When we have $G = \emptyset$, we check whether the collected set $P$ of patterns in that branch. If $\Card{P} \leq k$ we answer \textsc{Yes}{}, otherwise the branch is terminated. If all branches terminate with no \textsc{Yes}{} answer, we answer \textsc{No}{}.
\end{proof}

\begin{theorem}\label{thm:PIP_FPT_k_r_Sigma_B}
\sloppypar \PIPS{} is fixed-parameter tractable when parameterized by $k + \Card{\Sigma} + d + r + \Card{B}$.
\end{theorem}

\begin{proof}
As each pattern can have at most $r$ many $\ast$ symbols, every other symbol in each pattern is fixed. Thus each pattern is compatible with $\Card{\Sigma}^{r}$ strings. This limits the number of strings in $G$ to $k\cdot\Card{\Sigma}^{r}$.

The tractability then follows from Theorem~\ref{PI_FPT_few_small_strings}.
\end{proof}

\section{Discussion}
\label{sec:discussion}

Complementing the classification results given above, we now discuss some related issues. Firstly (in Section~\ref{sec:discussion_parameters}), given the complex parameter landscape introduced, what problems remain unsolved, and which are the interesting parameterizations for future work? Secondly, we related \PI{} to some similar problems that give some small intuition as to sources of complexity in \PI{} (Section~\ref{sec:other_problems}).

\subsection{The Mire of Multivariate Analysis: Untangling the Parameters}
\label{sec:discussion_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 values\footnote{By non-trivial we mean values which differentiate the parameters -- for example, if $s > n$, $s$ becomes meaningless as any number of $\ast$ symbols would be allowed, within the limitation of length $n$ strings.}, are $r \leq n$, $s \leq n$ and $d \leq n$. We also note that $k \leq \Card{G}$ and $k \leq (\Card{\Sigma}+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

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.8]{patterns-venn}
  \caption{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 $\Card{G}$.}
  \label{fig:patterns-venn}
\end{figure}

A visual summary of the tractable, intractable and open cases for a simplified parameter space is given in Figure~\ref{fig:patterns-venn}. Given the relationships between $s$, $r$, $d$ and $n$, we reduce the parameter space to $k$, $\Card{\Sigma}$, $n$, $\Card{G}$ and $\Card{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~\ref{fig:patterns-venn} it is clear that the central parameter in the open cases is $\Card{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 open\footnote{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.}.

\subsection{Ties to Other Problems}
\label{sec:other_problems}

The \PI{} 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.

\subsubsection{Set Covering}
\label{sec:set_covering}

When the length $n$ of the strings is small, \PI{} can be easily reduced to \SetCover{}. Given an instance $(\Sigma, G, B, k)$ of \PI{}, we can generate the set $P$ of all patterns that are compatible with some string in $G$. We know that $\Card{P} \leq \Card{G}\cdot 2^{n}$. From $P$ we remove any pattern that is compatible with a string in $B$. Let $P'$ be the set thus obtained. For each $p \in P'$, let $s_{p} = \{g \in G \mid p \to g\}$, and let $S = \{s_{p} \mid p \in P'\}$. Taking $G$ as the base set, $(G,S,k)$ forms an instance of \SetCover{} (parameterized by $k$). This reduction can be performed in $O((\Card{B}+\Card{G})\cdot\Card{G}\cdot 2^{n}n)$ time.

This leads to the following theorem:

\begin{theorem}\label{thm:PI_in_W[2]_sometimes}
  $\PI{} \in \Wtwo{}$ when $n \leq f(k)\cdot\log\Card{I}$ where $\Card{I}$ is the overall size of the instance and $f(k)$ is a computable function of the parameter $k$.
\end{theorem}

\begin{proof}
  The reduction above is a parameterized reduction if $2^{n} \in O(g(k)\cdot\Card{I}^{c})$ for some computable function $g$.
\end{proof}

It is not clear that we retain \Wtwo{}-hardness in this case however, so we unfortunately do not obtain a \Wtwo{}-completeness result.

This does give us an immediate approximation algorithm for this case however. As \SetCover{} has a $1 + \log(\Card{S})$-factor linear time approximation algorithm~\cite{Johnson1974}, we obtain a $1 + \log(\Card{G}^{2}\cdot\log(\Card{I})\cdot 2^{f(k)})$-factor fpt-time approximation algorithm.

\subsubsection{Feature Set}
\label{sec:feature_set}

The \kFS{} problem bears a strong resemblance to the \PI{} problem\footnote{Indeed, variants of \kFS{} have also been considered for use in similar applications as \PI{}~\cite{CottaMoscato2005}.}, except in the \kFS{} 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 = \{i_{1}, \ldots, i_{k}\}$ 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 \in G$, let $p_{g}$ be the pattern where $p_{g}[i] = g[i]$ if $i \in I$ and $p_{g}[i] = \ast$ otherwise. We note that this gives a set of small patterns (\emph{i.e.}, $s = k$), however the number of patterns may be as large as $\Card{G}$.

Conversely, given a set of patterns $P$ with at most $s$ non-$\ast$ symbols in each pattern, the set $I = \{i \in [n] \mid \exists p \in P(p[i] \neq \ast)\}$ forms a feature set. Again we note that the size of the feature set may be as large as $\Card{G}\cdot s$.

If we consider a variant of $\PIp$ where we relax the constraint on the number of patterns in the solution, it is easy to see that this problem is in \Wtwo{}. This suggests that the solution size plays a significant role in raising the complexity of the problem from a parameterized perspective.

\section{Conclusion and Future Directions}
\label{sec:conclusion}

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 \PI{}. Although \PIp{} is \Wtwo{}-complete, the general problem is only \Wtwo{}-hard, and the containment of \PIP{} simply gives a loose upper bound, although does suggest that the problem is harder than \PIp{}. The problem, intuitively, also shares some similarities with $p$-\textsc{Hypergraph-(Non)-Dominating-Set} which is \Wthree{}-complete~\cite{ChenFlumGrohe2007}. $p$-\textsc{Colored-Hypergraph-(Non)-Dominating-Set} however is $\mathsf{W}^{\ast}[\mathsf{3}]$-complete~\cite{ChenFlumGrohe2007} and appears ``harder'' than \PI{}, hence we conjecture:

\begin{conjecture}\label{conj:PI_in_W[2]}
\sloppypar $\PI{}$ is $\Wthree{}$-complete when parameterized by $k$.
\end{conjecture}

There are also some interesting parameterizations for which the complexity remains open:

\begin{itemize}
\item \sloppypar \PIS{} parameterized by $k + \Card{\Sigma} + d$, and
\item \sloppypar \PIPS{} parameterized by $k + d + r$.
\end{itemize}

Turning to the parameter $\Card{G}$, results for the following combinations of parameters would also close some of the significant open cases:

\begin{itemize}
\item \sloppypar \PI{} parameterized by $k + \Card{\Sigma} + \Card{G}$,
\item \PI{} parameterized by $\Card{G} + \Card{\Sigma} + \Card{B}$, and
\item \PI{} parameterized by $k + \Card{B} + \Card{G}$.
\end{itemize}

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.

\section{Acknowledgements}
\label{sec: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.

\section{References}
\label{sec:references}

\bibliographystyle{plain}

redpajama_set_name: RedPajamaArXiv


A simplified way to read the Bible that offers younger readers a plan tailored just for them.
God has given us an immeasurable gift—his very words, recorded in the Bible for us to read. Structured reading plans provide a great way to read through the whole Bible, but they're usually not designed with kids in mind.
In Exploring the Bible: A Bible Reading Plan for Kids, David Murray presents a simplified way to read the Bible by offering younger readers a plan tailored just for them.
His 365-day plan guides children through key passages from Genesis to Revelation, helping them see and appreciate the big-picture storyline of the Bible. Each passage is also followed by a question to answer or a verse to write out, as well as space to write out a prayer— encouraging interaction with the text.
This book will instill in children the habit of being in direct contact with God's Word each day, equipping the next generation by laying the groundwork for a lifetime of Bible reading.
Thankyou - our grandsons are loving the book !
Bought the book for the Sunday School children and they loved it, as it provides them with activities to do daily at home too.


Livestock water tanks are covered under the "Livestock Water Tank Act of Colorado" sections 35-49-101 to 35-49-116, C.R.S. These structures include all reservoirs built after April 17, 1941, on watercourses which the state engineer has determined to be "normally dry" and having a capacity of not more than ten acre-feet and a vertical height not exceeding fifteen feet from the bottom of the channel to the bottom of the spillway. Again, as with erosion control dams, the height is measured from the lowest point of the upstream toe to the crest of the spillway. No livestock water tanks can be used for irrigation purposes.
Erosion control dams are governed under Colorado statute (see section 37-87-122, C.R.S. (1990). These types of structures may be constructed on water courses which have been determined by the state engineer to be normally dry (which for our purposes is dry more than 80% of the time). Structures of this type cannot exceed fifteen feet from the bottom of the channel to the bottom of the spillway and cannot exceed ten acre-feet at the emergency spillway level. The height of the dam is measured vertically from the lowest point of the upstream toe to the crest of the dam in contrast to those measured vertically from the centerline pursuant to section 37-87-105, C.R.S. (1990). Note: The structure can be larger than specified under section 37-87-122, however, it then will be evaluated and must be constructed pursuant to section 37-87-105.
Select "Sign out" below if you are ready to end your current session.


text:
NCHD county health departments scaling back operations
Tucker Sargent,
MACON, Georgia (41NBC/WMGT) – North Central Health District county health departments are limiting services to only the "most crucial public health services" due to the increasing number of local confirmed cases of COVID-19.
"Our goal is to protect the health of our clients, health department staff members, residents and communities by focusing our efforts on COVID-19 response," a NCHD news release said Sunday morning.
Public health departments in Baldwin, Crawford, Hancock, Houston, Jasper, Jones, Macon-Bibb, Monroe, Peach, Putnam, Twiggs, Washington and Wilkinson Counties will be limited to the following clinical services until further notice:
STD & HIV testing
Immunizations for children age 5 and younger
Tdap vaccination
Hepatitis A vaccination
Medicaid enrollment for women's health and pregnancy
WIC program vouchers
The NCHD says it also taking measures to keep county health departments compliant with social distancing guidelines.
"As a precautionary measure to limit the number of people closely gathered in waiting rooms, health departments are not accepting walk-in clients at this time and late clinic hours are suspended," the release said. "Effective immediately and until further notice, anyone in need of clinical services should call ahead to make an appointment."
Contact your local health department if you have any questions or to schedule an appointment.
For more information about COVID-19, including local case counts and guidance for organizations, visit NCHD52.org/coronavirus.
The South Central Health District, which includes county health departments in Bleckley, Dodge, Johnson, Laurens, Montgomery, Pulaski, Telfair, Treutlen, Wheeler and Wilcox Counties, made a similar announcement Sunday night.
Categories: Baldwin County, Bibb County, Crawford County, Hancock County, Health, Houston County, Jones County, Local News, Monroe County, Peach County, Twiggs County, Washington County, Wilkinson County
Tags: Coronavirus, COVID-19, Health Departments, North Central Health District

redpajama_set_name: RedPajamaCommonCrawl


A student who misses just two days of school each month — 18 days total in the year — is considered to be chronically absent. However, many parents don't realize that, even when excused or understandable, absences add up and can greatly impact a child's education. In the United States, more than 6 million children are chronically absent from school each year.
New research released today by the Ad Council found that an overwhelming majority (86%) of parents understand their child's school attendance plays a big role in helping them graduate from high school. However, nearly half (49%) of parents believe that it is okay for their children to miss three or more days of school per month – and that they won't fall behind academically if they do. In reality, missing just two days of school per month makes children more likely to fall behind and less likely to graduate.
The U.S. Department of Education announced the award of $144 million for 459 new grant awards under the Talent Search program. Commemorating 51 years since its inception, in 2016, these five-year grants will assist more than 300,000 youth across 49 states, Puerto Rico, Guam, the Federated States of Micronesia and Palau in gaining the skills needed to successfully graduate high school and prepare for college. Of the 459 applicants who competed successfully in the FY 2016 competition, 418 applicants will begin new awards in the 2016-2017 project year and future awards will be made to 41 applicants with one or more years remaining on their current Talent Search grants. This year's grant competition marked the first year of encouraging evidence-based strategies for both secondary completion and postsecondary enrollment.
U.S. Secretary of Education Arne Duncan announced today that ASCD will join the National Board for Professional Teaching Standards and the U.S. Department of Education as the third partner in Teach to Lead, which focuses on expanding opportunities for teacher leadership in ways that enhance student learning and make it possible for teachers to stay in the classroom while leading in the profession.
At around midday Monday at High Tech High School in North Bergen, N.J., about 40 students are crammed into a small classroom, anxiously waiting for Kendrick Lamar to walk into the room.
He glides in with crisp white kicks, a grey long-sleeve shirt, and hair twisting every which way. The 27-year-old rapper has a broad smile on his face. He seems almost as excited as the students, who just might be having their best day of school … ever.
Lamar is on top of the rap game at the moment. His latest album, To Pimp a Butterfly,came out earlier this year and debuted at No. 1 on Billboard's albums chart. It's a complex, multilayered piece of work that wrestles with themes around blackness and beauty.
The National PTA has designated June as the Month of the Rural Child, a time when parents and communities explore ways to become involved and support students in rural schools.
The U.S. Presidential Scholars Program was established by executive order of the President fifty years ago this month. The program recognizes and honors some of our nation's most distinguished graduating high school seniors and was expanded in 1979 to recognize students who demonstrate exceptional talent in the visual, creative, and performing arts.
Each year, 141 students are named as Presidential Scholars, one of the nation's highest honors for high school students.
In honor of the 50th anniversary of the program, ED has collected reflections from past winners, who explain how the program influenced their life and career.


Idm Crack . with serial keys can be downloaded from apk paradise. And there are both bit patch and bit patch for this. Downloading process of patch free download of Windows version and other versions..So, IDM Crack . is available that is an alternative to the IDM and work same as Activate your windows with kmspico activator with no cost..Idm crack full version serial key Free Download Works On Windows XP | Windows | Windows . | Windows |Linux and VISTA GHZ .Activate IDM with free IDM serial Key Working! You can download full version of IDM free for windows and Mac. Only Limited Keys available!.


text:
Leafs And Fans Hit The Road Together
Hayley Mann Staff Writer
As Goshen's men's soccer team suited up at Taylor University on Nov. 8 for the semifinal conference game, the atmosphere certainly didn't feel like an
away game.
"Our fans made it feel like we were playing at home—we were louder and more enthusiastic," Caleb Longenecker, a senior starter, said. "It definitely made it more exciting, and we wanted to make it a great game for all the people that showed up and believed in us."
The amount of support from students was due in large part to the Residence Life team for organizing charter bus transportation for students. Katie Dwyer-Zeman, assistant director of residence life and student activities, agreed to ride along as a supervisor. The bus was a splurge, but was well used with 40 out of 48 seats being filled.
"I think it was hugely important for our students to have easy access to support our men's soccer team on the road," Dwyer-Zeman said. "It gives our students a great opportunity to represent Goshen College to other schools and show them how much we care about and support our student athletes."
Belief in the men's soccer team has been high all year, with the addition of a new coach and restructuring of the program helping to fill the stands almost every home game. It even proved enough to fill the stands at two away games in a row.
With a louder student section than Taylor's, and evenly matched support from both Indiana Wesleyan and Goshen fans at the conference finals, Goshen College students proved they know how to bring together community, even two hours away on a record-cold night.
"[It] definitely helps in the second half to hear the fans cheering you on—makes you want to keep going and give them a good game," Jadon Chupp, a sophomore starter, said. "We have such amazing fans and we could really feel that at both conference games."
The Goshen fans also brought their energy to the conference championship game against Indiana Wesleyan University on Nov.15.
Though the men came up just short of claiming the championship, the fans were not deterred in any way, carrying right through to the end to sing, "We love you Goshen, we do."
The traditions and character that make Goshen College's soccer games unique were not lost or dampened by the weather, score or distance.
"I felt like I could actually influence the game by being loud and cheering with the rest of the fans," Thomas Leonard, a senior, said. "It seemed like the players would respond to our energy in the stands, and we got to show the other schools how unique Goshen is."
This was the first time the men's soccer program has gotten to the conference finals in seven years and the students showed their excitement and pride in the players.
"When bus and carloads of students travel two hours one way, two Saturdays in a row, it's because our students believe in our soccer team and appreciate the countless hours of hard work they put in all season," Dwyer-Zeman said. "That says a lot."
Inside-Out program returns after two-year hiatus
By Jakyra Green
By Sierra Ross Richer
Autism spectrum disorder social group seeks inclusivity
By Mariela Esparza


Japan Railways has appointed Sanjeev Sinha as Advisor for project of Ahmadabad-Mumbai High Speed Rail.
Twelve stations have been proposed for the line: Mumbai Bandra Kurla Complex, Thane, Virar, Boisar, Vapi, Bilimora, Surat, Bharuch, Vadodara, Anand, Ahmedabad and Sabarmati. Over two-third of the project will be in Gujarat and rest in Maharashtra.
The Mumbai-Ahmedabad bullet train project is being financed through a "soft loan" from Japan International Cooperation Agency with around 80 per cent of the Rs 1.08 lakh crore total cost.
"Repayment of loan is to begin after 15 years of receiving the loan, making it practically free since, this loan interest works out to roughly Rs 7-8 crore per month", said a railway statement. This loan is to be repaid to Japan in 50 years.
According to railway ministry officials, the operating speed of the bullet train will be 320 kilometers per hour and maximum speed will be 350 kilometers per hour. If the bullet train will stop at all 12 stations, then it will cover the distance in two hours and fifty-eight minutes. The funding for this project comes as the part of a low-interest loan extended to India by Japan. The high-speed train will considerably reduce travel time between Ahmedabad and Mumbai which are major commercials hubs.
From the total 508-km stretch, 92 percent of the route will be elevated, 6 percent will pass through tunnels, including tunnels under the sea, and the remaining 2 percent will be ground-based.
Already ground surveying using LiDAR technology and geotechnical investigations have been completed, as well as specifications for track, tunnels, bridges, signalling and telecoms. Expected to cost almost ₹1.10 lakh crore, the first Bullet Train is expected to be ply on Indian soil by 2022.
As the government mulls moving the deadline forward for completion of the project from March 2023 to August 15, 2022 when the country celebrates its 75th year of independence, Goyal said, keeping in mind the speed with which the government has implemented all projects he is confident that this project too will be completed before deadline. "The bullet train will bring in the latest global railway technology in India and place India on a par with developed countries", he said.
Goyal added that Shinkansen technology can be exported from India and the cost of technology can rapidly decrease, as it happened in LED bulbs.
Authorities estimate that the project will create 20,000 jobs during construction and later sustain 4,000 direct and 20,000 indirect jobs once it is operational. Four sub-groups with representatives from Indian industry, Japanese industry, DIPP, and the National High Speed Rail Corporation have been formed and are looking at systems and sub-systems to push "Make in India". The high-speed train is created to have ten cars with 750 people capacity and is slated to carry around 36000 passengers every day in a total of 70 rides both sides.
Ukraine has been wracked by conflict in its eastern regions since March 2014 after Russia's annexation of Crimea. Last week, Putin said that Russian Federation meant to draft a U.N.
The UN-backed CICIG played a key role in ousting Morales' predecessor Otto Perez Molina in 2015. The CICIG is widely respected in Guatemala.
Any loss of its tax-exempt status in Israel could seriously affect Amnesty International's ability to raise funds in the region. Representatives of the human rights group will be called for a hearing at Israel's Finance Ministry, Haaretz said.
But updates might not be as frequent for single-purpose smart devices like your smart refrigerator or a connected television. Your phones, laptops, speakers, vehicle entertainment systems - the list goes on and on to even the most mundane gadgets.
Iraqi Kurdish President Masoud Barzani walks behind a security service staff member during his visit in Kirkuk, Iraq September 12, 2017.
The Bureau of Criminal Apprehension's investigation into the Minneapolis police shooting of Justine Damond is over. Damond was shot and killed July 15th by Officer Mohamed Noor as she approached the squad auto he was riding in.
Equities analysts anticipate that Comtech Telecommunications Corp. will post $0.65 earnings per share for the current fiscal year. Noble Financial restated a "buy" rating on shares of Comtech Telecommunications Corp.in a report on Friday, June 9th.
Chen called the game a "romantic social game", stating that it's meant for even the most casual gamers to be able to get into. The downside, or upside, depending on where your loyalties lie, is that it's going to be Apple-exclusive...for now.
The Average Directional Index or ADX is a technical analysis indicator used to describe if a market is trending or not trending. Used as a coincident indicator, the CCI reading above +100 would reflect strong price action which may signal an uptrend.
The Gray family's attorney, Billy Murphy, says the Justice Department informed him on Tuesday that no charges would be filed. The six Baltimore PD police officers faced state criminal charges, including manslaughter and second-degree murder.


text:
Special Trick to Access Amazon Alexa On An Apple Watch
Rob Stratford
Apple's smartwatch lineup is filled with high-end gadgets such as the Watch Series 3 that offer a wide range of cool features and reliable hardware specs. On the downside of things, Apple Watches are limited to their iOS ecosystem. This is the cases for all Apple products and its one of the most annoying things about being an iOS fan. Ever since iOS was introduced, Apple made it loud and clear that it doesn't want its users to interact with other operating systems by not even allowing people to connect their iPhones to Android ones to Bluetooth.
Fortunately, there are many third-party apps which have been developed with the sole purpose of helping iOS fans get the most out of their iPhones and Apple Watches. With that being said, today we are going to share a tip that lets Apple Watch owners get access to Amazon's Alexa even though Apple might restrict them from this doing.
Siri is a great AI assistant, but it's still miles behind Alexa. Amazon struck gold when it developed Alexa because this AI assistant comes with so many powerful features that it made Amazon's Echo Dot a bestselling device. Therefore, no one can blame Apple fans for wanting to give Alexa a try and see how much more powerful it is than Siri.
Voice in a Can
The app that makes it possible for iOS fans to access Alexa directly on their Apple Watches is called Voice in a Can. The app is available on iTunes and it costs $1.99, but this is a small price to pay when considering how much more useful Alexa can be than Siri. Nonetheless, let's see how Alexa can be enabled on Apple Watches.
#1. Download Voice in a Can from iTunes and install it on the iPhone that is paired with your Apple Watch. We should mention that Voice in a Can requires an iPhone that runs on iOS 11. After the app has been installed, open it and log in with an Amazon account.
#2. After logging in with an Amazon account, you will be able to simply tap the "Ready" button and talk to Alexa.
#3. Open the Watch app on the paired iPhone and select the "My Watch" option. All that's left now is to open the Voice in a Can app on the Apple Watch and follow the instructions to authenticate yourself.
As previously mentioned, Apple puts lots of restrictions on its operating system. This means that Alexa will not be able to run at its full on potential on an Apple Watch. The limitations that Alexa will have on an Apple Watch are that it's not able to play audiobooks, podcasts and music. Other than that, Alexa will answer every question that you have for her.
Watch Complication
We advise all iOS fans who want to use Alexa on their Apple Watch to set up a special Watch complication for Voice in Can. This is a standalone app which means that it will work on an Apple Watch without needing to have an iPhone around. Not just that, but Voice in a Can doesn't require the Apple Watch to be connected to Wi-Fi or mobile data in order to work.
Before we end this, we need to mention that Apple is getting closer to launching to launching iOS 12 and this major update is expected to introduce lots of new features that will help take Siri to the next level. Let's hope Apple optimizes Siri's voice recognition software in iOS 12 so that the Apple AI assistant can finally compete against Alexa.
Apple Watch Alexa
Apple's iPhone XR is the Bestselling Smartphone in 2019


I was overwhelmed with my assignment today – my mothering and homemaking. My little ones have been bickering like crazy fighting over toys, food, and whatever else with piercing screams. I forgot to turn on my dishwasher, leaving me with a kitchen full of dirty dishes. A Realtor calls to show the house and gives me a 20 minute notice. I fly crazily around the house to get it picked up and then out the door with my kids, only to have her cancel just after we had loaded everyone into the car and drove away. I found myself asking myself, "How on earth can I ever train them to love each other? How can I manage all of this? How can I keep the peace when my emotions wants to stress out?" You would have seen me crying if you had been present today.
Then the Lord gently reminded me that maintaining joy in my tasks is my opportunity to worship my Creator. He has designed us, as women, to establish a peaceful home for God's glory.
Did you hear that? To be a godly woman means we worship the Creator in all the duties of life – everything from diapers, to dishes, to scrubbing toilets, to preparing meals, to decorating our homes. Each task is an act of worship to our Creator, because we are faithfully walking in His beautiful design. Worship is not limited to Sundays, or to actual singing, but it is doing all that we do for the glory of God, with a heart that desires to please Him. These are acts of worship when completed with a joyful heart. "Whether you eat or drink, or whatever you do, do all to the glory of God." (1 Cor. 10:31).
Don't fall under the lie that your assignment in the home is worthless, or less important. You have the opportunity to bring God glory through every mundane task. Washing the dishes is an opportunity to worship my Savior! Training my children is an opportunity to radiate God's beauty. Sing while you work, inwardly and externally, and God will be greatly glorified. The important thing is to keep your eyes on Jesus and do the next thing.
Ginger shares later, "True beauty radiates from a woman who gracefully walks the path designed uniquely for her. To walk the path of God's will is to show others the beauty of Christ. " God has assigned me the task of dedicating my life to nurturing my children, loving and working side by side with my husband in fulfilling the mission God has assigned us to love God and reach out in demonstrating that love to others. That is my calling and every small task will be my act of worship and He will give me wisdom to faithfully walk this path! His grace is sufficient!
Can Natural Living Become an Idol?
Thank you for such a wonderful post. Thank you for reminding me to keep my eyes on the Father, the Son and the Holy Spirit.
This article was so encouraging! I wanted to thank you, and let you know i've linked to you on my site to bless other moms!
Thanks for your comments. I have 5 beautiful children, the oldest is 8, and many days are tough. I am so grateful when I read this – how wonderful that there are other mothers out there magnifying their callings as women and mothers! It gives me hope for the entire world.
Timely words. Very encouraging. Thank you for sharing!
I'm a widow at the other end of the family spectrum helping to take care of my recently widowed 88-year-old mother. Ten years ago when I was in charge of my church nursery, I told my young helpers that they could change diapers to the glory of God. And I know it's true.
It's good to encourage and exhort one another–and absolutely necessary!
such good words to hear! You are an encouragement to so many mamas.
You make such a good point. I am trying to keep my home and my classroom peaceful. I have nearly been brought to tears in my classroom this year by a very challenging group of kids. I keep reminding myself of my purpose in their lives. Thank you for the reminder of serving in all aspects of life.
Such a good reminder, Lindsay. Thank you! It can be so hard, but it is so worth it!
Thank you for this encouraging post! I found myself a bit stressed out today, too, so your words are very timely for me.
Thank you for sharing such a beautiful and moving post. I've been battling my own challenges lately and this post inspires me to strive harder and longer and more cheerfully.
Wow, Lindsay…thank you so much for writing this. It was so encouraging and I was moved to tears! I've had a very sick husband at home for the last 3 days and was beginning to feel down, but your post was just the thing God used to remind me that my humble efforts at home are not in vain if they are done for Him. Thanks again!
Mmm…after struggling to pack up for a weekend away, deal with a teething three-month-old, and nurse the most sudden and heinous head cold of my life (at least since the last one), I definitely needed to hear that even doing dishes can be an act of worship…thank you for the encouragement!
amen! this is such an awesome blog. i just love it. sorry this is the first time i'm showing up to say it, but: thank you!!
Yes, Lindsay, you are so right on with this! I wrote a post about this a couple weeks ago, that speaks I think to exactly understand our purpose in our roles and that what we do at home is so valuable. I will totally need to get that book you mentioned…it sounds really good! I love the idea of bringing a little piece of heaven in my home. The word 'peace' seems to be ringing home for me lately. I very much want to create an environment of peace in my home. And with 5 kids, sometimes peace is a bit elusive.
Thanks again for a timely post. I had a pretty easy day today compared to sometimes, but I can totally understand where you are coming from. It's very hard to get my 4 yr old and almost 2 yr old to get along…constant fighting over toys. I can worship in showing them how to get along….thank you so much!
We have had our house on the market for a year and a half and just sold it! I have a 4, 2 1/2, and 5 month old. Showings cancelling at the last minute happened too many times to count and it is devastating for a brief moment. I tried to rejoice in the fact that atleast I had a clean house! Having little ones is a tough time to have the house on the market. Hang in there.
Oh girl I feel for you. I have three girls ages 4,3,and 18 months. I started homeschooling this year and yesterday I told my husband that I was not sure how long I could keep it up for. I complained that it was so hard to "do it all" and that I could just see my self gray in 5 years at 30. My husband told me that it is easier to just take them to school, it is easier to be easy on your kids and let them get away with things, it is easier to go out rather than taking the time to cook a meal yourself, it is easy to get divorce, it is easy to live an unholy life. Everything that is worthwhile and good takes HARD work, including disciplining kids, keeping a house organized, leading a holy life, etc. My husband always reminds me that God never promised us an easy life but he did promise not to leave us or forsake us. Lindsay, today you had a rough start and tomorrow it might be my turn ( I hope not) but we are all humans and we experience the same things. I enjoy your blog and I think you are one cool lady. Your smart, practical, trying to be a good christian, and I know you will be OK. Thanks for the recipe for the deodorant-I love it and my husband armpits are no longer blue from all the dyes. Thank you for all you do and the time you spend writing on your blog. God Bless you and your family.
Thank you for the reminder. Sometimes I forget that choosing to stay home with my daughter is just as important as the work I left as a nurse.
Excellent article today. I mostly think this way about my role in my home. It is an honor to be a stay at home Mom, homeschooling our 3 children. Sometimes I forget to "do all to the glory of God". Thank you for the reminder! God Bless you!
Thanks, I needed this today.
Sometimes I feel resentful because women really got jipped in all this "Equality" stuff. Now that women work full time we're not equal…we just do a double load!
I just wanted to share this book with you. It has helped me a lot and I believe it's biblical. It's short, sweet, and practical.
All the best…. bless you.
Thanks you for posting this. It is a blessing to hear such encouragement from fellow young mothers of two.
Thank you so so much for sharing! It helps to know that other moms struggle with imperfect children too! Sometimes I worry that the harder I try the more they fight!
I can't move, if I don't start my day w/worship or time in the Bible. If I don't my flesh starts acting up, I lose my joy, my peace etc. I get annoyed w/the kids, or co-workers.
You're correct worship isn't suppose to be just for Sundays, or any day you to church. It should be second by second minute by minute, hour by hour, day by day. I NEVER want to leave the presence of God. Only there will I be at absolute peace!
Lindsay, pull out some scriptures that will build you up. For instance, This is the day that the Lord has made I will REJOICE and be glad in it. Rejoice in the Lord always.
Just start confessing these, not just saying them, but by faith believe them.
I've been there Lindsay, and on occasion it still happens. the enemy LOVES to see his people down and out. But we as Christians must come against those thoughts. 2 Corinthians 10 tells us to take those thoughts into captivity. Any thought or imagination that goes against the truth of God's word must be casted down. We don't want a video footage of the every thing we have done wrong being played over and over again.
I'm praying for you Lindsay! Now go and REJOICE!
Thanks! This really speaks to me. I have truly been struggling the last few weeks, partly because of the exhaustion pregnancy brings.
Oh, I love that insightful quote from Heaven at Home. I just added it to my wishlist! I know we all have those kinds of days, and this is a good reminder that it's only by the grace of God that we can achieve anything worthwhile. It's all a gift from him. Thanks for sharing!
Thank you for this post and reminder. I work full-time outside of the home and my husband and I have no children…but I so desire to be able to be a full time homemaker and mother. I often struggle with frustration and sadness (translation: self pity) about this. I so appreciate the reminder that I am called to worship and glorify God regardless of my circumstances.
Even if a huge ocean lies between us (I live in Germany), I know your feelings oh so well. In my case it's not a realtor, it's my mother-in-law who loves to visit "in just 10 minutes".
Talking about fighting kids: My son used to hit my daughter from day one. The result was a baby who was afraid to sleep, who nearly "lived" the first year in a carrier and a mother who cried so many days that I can't count them anymore. When my husband arrived from home, I often fleed to our church, just to sit in the dark and cry.
But.. now they are two and four and , believe it or not, they really love and respect each other so much. It's such a joy to watch them now!!! In eight weeks baby no 3 will arrive and both can't wait to get to know little Luisa (they call her "Lissy").
Wishing you much strength all around the globe!
PS: I loved the book "Siblings without rivalry". First I thought it doesn't work, but now, after two years, I know better.
Hi Melanie… I also live in Germany! Where are you at? I live in Worms.
Thank you for the reminder that it is God I am serving and not man.
Much needed encouragement. Thank you.
Lindsay, thank you so much for this reminder. It's nice to knowthat I'm not the only one who struggles with maintaining joy during the hard days as a stay-at-home mama.
Thank you for being so real and for not pretending to have it all together. God's used you to bless my heart today.
This is a wonderful post. I have had people in my life make me feel like what I am doing (staying home with my daughter) is not significant, but this post reminds me that it isn't. Thank you for the reminder to find joy in the small moments.
*This post reminds me that it IS significant.
Thank you for this post…It came at the perfect time for me. With a 12 wk old and an almost 3 year old I feel like I spend many days running in circles. This reminder of the importance of what I do and to worship God in all I do was well needed–esp as I am up at 5 AM feeding baby G and working on a grocery list Blessings!
I have a almost 9 year old and almost 3 year old and completely understand. It can feel meaningless sometimes,but when it is all done and every one is snuggled in bed I feel really satisfied and happy and that have done well by my kids. I think that is all that God wants for us. It is not perfect every day,but all we can do it try,right.