### Program Information

Name: Set Cover
Domain: Optimization algorithms
Functionality: Solving the so-called set cover problem,which is also named key-lock problem.
Input:
M:An $p \times q$ matrix ,where an element $m_{i,j}$ of M is either 0 or 1, and $m_{i,j} = 1$ denotes that the ith key can open the jth lock(Type: Matrix)
Output:
C: An integer(Type: Integer) $K(k_{1},k_{2},\cdots,k_C)$: An array, where K contains C keys that can open all keys(Type: Array)

#### Reference

How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? http://dx.doi.org/10.1109/TSE.2013.46

### MR Information

#### MR1

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a column of “1” at the left of $M_s$, which means a lock that can be opened by all keys.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR2

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Changing the row order of $M_s$ between any pair of adjacent selected keys.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR3

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: The element $m^f_{i,j}$ of $M_f$ = 1 - the element $m^s_{(p-i+1),j}$of $M_s$
Output relation: $K_f = (k^f_{1},k^f_{2}, \cdots ,k^f_{C_f})$ $K_s = (k^s_{1},k^s_{2}, \cdots ,k^s_{C_s})$ $k^f_{1} \ne p - k_{1} + 1$

#### MR4

Source input: $M_s$ ; Source output: $C_s,K$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K$
Input relation: $M_f$ = The first $C_s$ rows are the same as the $k_{1}th$,$k_{2}th$, \cdots ,$k_{C_s}th$ rows of $M_s$, and the remaining $p-C_s$ rows stores the data corresponding to unselected keys.
Output relation: $C_f = C_s$ $K = (1,2,\cdots ,C_s)$

#### MR5

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Deleting one useless row of $M_s$, which means unselected keys.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR6

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a row of “0” at the bottom of $M_s$, which means a key that cannot open any lock.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR7

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a row that is the subset of one existing row at the bottom of $M_s$, which means a key whose opened locks are the subset of those of one existing key.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR8

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Deleting the jth column whose $m_{i_{1},j} = 0$ from $M_s$, which means a lock that cannot be opened by the first selected key.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR9

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding a row that is the same as one existing row at the bottom of $M_s$,which means a key that is the same as one existing key.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR10

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Deleting the first row and all columns whose first element value is “1” of $M_s$, which means deleting the first key and all the locks that it can open.
Output relation: $C_f = C_s -1$ $K_f = ( k^f_{1},k^f_{2},\cdots,k^f_{C_f})$, where $k^f_l = k^s_{l+1}$ if $k^s_{l+1}<k^s_{1}$ or $k^f_l = k^s_{l+1} -1$ if $k^s_{l+1}>k^s_{1}$.

#### MR11

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Adding some columns whose first element value is “1” and the other values are all “0”, which means adding some locks that can only be opened by the first key.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR12

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M^f_{2p \times q}$, where $m^f_{i,j} = m^s_{i,j}$and $m^f_{(p+i),j}= m^s_{i,j}$
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR13

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ = Changing the order of columns of $M_s$.
Output relation: $C_f = C_s$ $K_f = K_s$

#### MR14

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ is a new $(p+a) \times q$ (a is a positive integer) matrix, whose first p rows are identical to $M_s$.
Output relation: The number of locks that can be opened by $k^f_{1}$ is larger or equal to that of $k^s_{1}$.

#### MR15

Source input: $M_s$ ; Source output: $C_s,K_s$
Follow-up input: $M_f$ ; Follow-up output: $C_f,K_f$
Input relation: $M_f$ is a new $(p+a) \times (q+a)$ (a is a positive integer) matrix , the top-left $p \times q$ part is identical to $M_s$, the right-bottom $a \times a$ part is identical to a $a \times a$ unit matrix,and all the element in other parts are zero.
Output relation: $C_f = C_s + a$ $K_f = {k^s_{1},k^s_{2},\cdots,k^s_{C_s},p+1,p+2,\cdots,p+a}$

### Related

Insert title here