# Name of the problem to find the maximum number of characters covered by a set of strings

I am interested in the following problem. One has two collections $Q$ and $T$ of strings, and a set $A$ of alignments of strings in $Q$ to strings in $T$. I want to find a subset $A'$ of $A$ that (i) involves each element of $Q$ only once and (ii) maximizes the total number of characters in elements $T$ that are covered by an alignment in $A'$.

(To be precise: Let $a$ be an alignment in $A$. We can think of $a$ as a tuple $(q,t,f)$ where $q\in Q$, $t\in T$, and $f : \mathcal I_a \to \mathcal J_a$ is a bijection such that $f(i)=j$ if $a$ aligns the $i$th character of $q$ to the $j$th character of $t$. Here $\mathcal I_a \subset \{1,2,\dots,|q|\}$ and $\mathcal J_a \subset \{1,2,\dots,|t|\}$, where $|\cdot|$ means length. We can think of characters in elements of $T$ as pairs $(t,j)$ where $t\in T$ and $j\in\{1,2,\dots,|t|\}$. We say that $(t,j)$ is covered by an alignment in $A'$ if there exists $a=(q,t',f)\in A'$ such that $t=t'$ and $j\in\mathcal J_a$. (Note that there might exist several such $a\in A'$.) Let $\chi(t,j,A') = 1$ if such an $a\in A'$ exists, and 0 otherwise. We want to maximize the cardinality of $\{(t,j) : \chi(t,j,A')=1\}$ over $A'\subset A$ such that for all $q\in Q$, there exists at most one $a=(q',t,f)\in A'$ with $q=q'$.)

My question: What is a name for this problem, if any? Thanks in advance! I guess that it is related to maximum matchings and maximum coverage, but it's not quite the same as either.

• This sounds really close to the set cover problem. en.wikipedia.org/wiki/Set_cover_problem – Joshua Herman May 22 '12 at 4:16
• @Joshua Herman. Thanks. A big difference, though, unless I'm missing something, is that we don't require that all the characters in elements of T are covered; rather, we want to maximize the number of covered elements. – N F May 22 '12 at 13:22
• (The end of my previous comment should be: "rather, we want to maximize the number of covered characters.") – N F May 22 '12 at 13:33
• Ok then it is the maximum cover problem. en.wikipedia.org/wiki/Maximum_coverage_problem – Joshua Herman May 22 '12 at 16:07

## 1 Answer

This sounds like the maximum cover problem which is NP-hard.