<p>This sounds like the <a href="http://en.wikipedia.org/wiki/Maximum_coverage_problem" rel="nofollow">maximum cover problem</a> which is NP-hard.</p>

CC BY-SA 3.0
2012-05-22T20:02:06.270Z
2012-05-22T20:02:06.270Z
Joshua Herman
<p>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'$.</p>

<p>(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'$.)</p>

<p>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.</p>

CC BY-SA 3.0
2012-05-22T04:16:20.410Z
This sounds really close to the set cover problem. http://en.wikipedia.org/wiki/Set_cover_problem
Joshua Herman
CC BY-SA 3.0
2012-05-22T13:22:15.137Z
@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
CC BY-SA 3.0
2012-05-22T13:33:35.840Z
(The end of my previous comment should be: "rather, we want to maximize the number of covered characters.")
N F
CC BY-SA 3.0
2012-05-22T16:07:42.893Z
Ok then it is the maximum cover problem. http://en.wikipedia.org/wiki/Maximum_coverage_problem
Joshua Herman
<cc.complexity-theory><reference-request><optimization>
Name of the problem to find the maximum number of characters covered by a set of strings
N F
# Name of the problem to find the maximum number of characters covered by a set of strings

(Asked by: username_0 on 2012-05-21)

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.

**Tags:** cc.complexity-theory, reference-request, optimization
> **Comments:**
> **username_1**: This sounds really close to the set cover problem. http://en.wikipedia.org/wiki/Set_cover_problem  
> **username_0**: @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.  
> **username_0**: (The end of my previous comment should be: "rather, we want to maximize the number of covered characters.")  
> **username_1**: Ok then it is the maximum cover problem. http://en.wikipedia.org/wiki/Maximum_coverage_problem  

---

## 1 answers

### Answer by username_1 on 2012-05-22. Score: 3

This sounds like the [maximum cover problem](http://en.wikipedia.org/wiki/Maximum_coverage_problem) which is NP-hard.


---

