# Set Covering Problem

## The Set Covering Decision Problem:

Given a universe of elements **U** and a family of sets **S** whose union covers **U**, is there a subset of **S** of size *k* that covers **U**? (a yes or no question)

For a more detailed description of the problem, read this: http://en.wikipedia.org/wiki/Set_cover_problem

The Set Covering Decision Problem is an NP complete problem, and we will describe a potential biological method to find a solution below. A similar problem is the optimization problem which asks to find the smallest possible number of sets in **S** that will cover **U**. The optimization problem is NP-hard and may be worth considering as well.

## The Idea:

Every element of the universe **U** is represented by its own reporter gene. We can then build the sets in **S**, potentially using Golden Gate Assembly. Then we can use the column method, with each column containing every set in **S**. The number of columns will be determined by *k*. If all genes report after Golden Gate Assembly, then a *yes* answer has been found.

## Example:

**U** = {Cre,Bla,CAT,RFP,GFP}

**S** = {{Cre, Bla, CAT},{Bla,RFP},{CAT,RFP},{RFP,GFP}}

*k* = 2

Column 1 = {{Cre + Bla + CAT},{Bla + RFP},{CAT + RFP},{RFP + GFP}} each with same sticky end that will attach to beginning of strands in Column 2

Column 2 = {{Cre + Bla + CAT},{Bla + RFP},{CAT + RFP},{RFP + GFP}}

If the answer is *yes*, then using the Golden Gate Assembly method with these columns will produce a strand of genes expressing Cre, Bla, CAT, RFP, and GFP, formed using only one subset in each column. It is easy to see that there is indeed a solution to the simple problem above. Combining {Cre, Bla, CAT} and {RFP, GFP} in any order will signal that the answer is *yes*.