# An exact algorithm with the time complexity of $O^{*}(1.299^{m})$ for the
weighed mutually exclusive set cover problem

Songjian Lu and Xinghua Lu

###### Abstract

In this paper, we will introduce an exact algorithm with a time complexity of
$O^{*}(1.299^{m})^{{\dagger}}$ ††footnotetext: †Note: Following the recent
convention, we use a star $*$ to represent that the polynomial part of the
time complexity is neglected. for the weighted mutually exclusive set cover
problem, where $m$ is the number of subsets in the problem. This problem has
important applications in recognizing mutation genes that cause different
cancer diseases.

Department of Biomedical Informatics,

University of Pittsburgh, Pittsburgh, PA 15219, USA

Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Introduction

The set cover problem is that: given a ground set $X$ of $n$ elements and a
collection ${\cal F}$ of $m$ subsets of $X$, try to find a minimum number of
subsets $S_{1},S_{2},\ldots,S_{h}$ in ${\cal F}$ such that
$\cup_{i=1}^{h}S_{i}=X$. If we add an additional constrain such that all
subsets in the solution are pairwise disjoint, then the set cover problem
becomes the mutually exclusive set cover problem. If we further assign each
subset in ${\cal F}$ a real number weight and search the solution with the
minimum weight, i.e. the sum of weights of subsets in the solution is
minimized, then the problem becomes the weighted mutually exclusive set cover
problem.

Recently, the weighted mutually exclusive set cover problem has found
important applications in cancer study to identify driver mutations [4, 12],
i.e. somatic mutations that cause cancers. As somatic mutations will change
the structures (and therefore the functions) of signaling proteins; thus,
perturb cancer pathways that regulate the expressions of genes in certain
important biological processes, such as cell death, cell proliferation etc.
The perturbations within a common cancer pathway are often found to be
mutually exclusive in a single cancer cell, i.e. each tumor usually has only
one perturbation on one given cancer pathways (one perturbation is enough to
cause the disease; hence, there is no need to wait for another perturbation).
Modern lab techniques can identify somatic mutations and gene expressions of
cancer cells. After preprocessing the data, we will obtain following
information for important biological processes, e.g. cell death: 1)which
cancer cells have disturbed the expressions of genes in the biological
process; 2) which genes have been mutated in those cancer cells; 3) how
possible each mutation is related to the given biological process (i.e. each
mutation is assigned a real number weight). Then next step is finding a set of
mutations such that each cancer cell has one and only one mutation in the
solution set (mutually exclusive) and the sum of weights of all genes in the
solution set is minimized, which is the weighted mutually exclusive set cover
problem.

While there is not much research on the mutually exclusive set cover or the
weighted mutually exclusive set cover problems, the set cover problem has been
paid much attention. The set cover, which is equivalent to the hitting set
problem, is a fundamental NP-hard problem in Karp’s 21 NP-complete problems
[8]. One research direction for the set cover problem is approximation
algorithms, e.g. papers [1, 5, 9, 11] gave polynomial time approximation
algorithms that find solutions whose sizes are at most $c\log n$ times the
size of the optimal solution, where $c$ is a constant. Second direction is
using $k$, the number of subsets in the solution, as parameter to design
fixed-parameter tractable (FPT) algorithms for the equivalent problem, the
hitting set problem. Those algorithms have a constrain such that each element
in $X$ is included in at most $d$ subsets in ${\cal F}$, i.e. sizes of all
subsets in the hittng set problem are upper bound by $d$; it is also called
the $d$-hitting set problem. For example, paper [13] gave an
$O^{*}(2.270^{k})$ algorithm for the $3$-hitting set problem, and paper [6]
further improved the time complexity to $O^{*}(2.179^{k})$. The third
direction is designing algorithms that use $n$ as parameter in the condition
that $n$ is much less than $m$. Papers [2, 7] designed algorithms with time
complexities of $O^{*}(2^{n})$ for the problem. The paper [2] also extended
the algorithm to solve the weighted mutually exclusive set cover problem with
the same time complexity. Paper [10] improved the time complexity to
$O^{*}(2^{\frac{\log_{2}d}{1+\log_{2}d}n})$ under the condition that at least
$\frac{n}{1+\log_{2}n}$ elements in $X$ are included in at most $d$ subsets in
${\cal F}$. This algorithm can also be extended to the weighted mutually
exclusive set cover problem with the same time complexity. However, in the
application of cancer study, neither $n$ is less than $m$ nor each element in
$x$ is included in bounded number of subsets in ${\cal F}$. Hence, there is a
need to design new algorithms.

In this paper, we will design a new algorithm that uses $m$ as parameter (in
application of cancer study, $m$ is smaller than $n$, where $n$ can be as
large as several hundreds). Trivially, if using $m$ as parameter, we can solve
the problem in time of $O^{*}(2^{m})$, where the algorithm basically just
tests every combination of subsets in ${\cal F}$. To our best knowledge, we
have not found any algorithm that is better than the trivial algorithms when
using $m$ as parameter. This paper will give the first un-trivial algorithm
with the time complexity of $O^{*}(1.299^{m})$ to solve the weighted mutually
exclusive set cover problem. We have tested this algorithm in the cancer
study, and the program can finish the computation practically when $m$ is less
than 100.

##  2 The weighted mutually exclusive set cover problem is NP-hard

The formal definition of the weighted mutually exclusive set cover problem is:
given a ground set $X$ of $n$ elements, a collection ${\cal F}$ of $m$ subsets
of $X$, and a weight function $w:{\cal F}\rightarrow[0,\infty)$, if ${\cal
F^{\prime}}=\\{S_{1},S_{2},\ldots,S_{h}\\}\subset{\cal F}$ such that
$\cup_{i=1}^{h}S_{i}=X$, and $S_{i}\cap S_{j}=\emptyset$ for any $i\neq j$,
then we say ${\cal F^{\prime}}$ is a mutually exclusive set cover of $X$ and
$\sum_{i=1}^{h}w(S_{i})$ is the weight of ${\cal F^{\prime}}$; the goal of the
problem is to find a mutually exclusive set cover of $X$ with the minimum
weight, or report that no such solution exists.

As we have not found the proof of NP-hardness for the weighted mutually
exclusive set cover problem, in this section, we will prove that the mutually
exclusive set cover problem is NP-hard; thus, prove that the weighted mutually
exclusive set cover problem is NP-hard.

We will prove the NP-hardness of the mutually exclusive set cover problem by
reducing another NP-hard problem, the maximum set packing problem, to it.
Remember that the maximum set packing problem is: given a collection ${\cal
F}$ of subsets, try to find an ${\cal S}\subset{\cal F}$ such that subsets in
${\cal S}$ are pairwise disjoint and $|{\cal S}|$ is maximized.

###### Theorem 2.1

The mutually exclusive set cover problem is NP-hard.
Proof.  Let ${\cal S}=\\{S_{1},S_{2},\ldots,S_{m}\\}$ be an instance of the
maximum set packing problem, where
$X^{\prime}=\cup_{i=1}^{m}S_{i}=\\{x_{1},x_{2},\ldots,x_{n}\\}$. We create an
instance of the mutually exclusive set cover problem such that:

  * •

$X=X^{\prime}\cup\\{T_{1},T_{2},\ldots,T_{m}\\}$, where
$T_{i}=\\{t_{i1},t_{i2},\ldots,t_{i(n+1)}\\}$ for all $1\leq i\leq m$;

  * •

${\cal F}={\cal F^{\prime}}\cup{\cal F^{\prime\prime}}\cup{\cal
F^{\prime\prime\prime}}$, where ${\cal
F^{\prime}}=\\{\\{x_{1}\\},\\{x_{2}\\},\ldots,\\{x_{n}\\}\\}$, ${\cal
F^{\prime\prime}}=\\{S_{1}\cup T_{1},S_{2}\cup T_{2},\ldots,S_{m}\cup
T_{m}\\}$, and ${\cal
F^{\prime\prime\prime}}=\cup_{i=1}^{m}\\{\\{t_{i1}\\},\\{t_{i2}\\},\ldots,\\{t_{i(n+1)}\\}\\}$.

Next, we will prove that if ${\cal P}=\\{P_{1},P_{2},\ldots,P_{k}\\}$ is a
solution of the mutually exclusive set cover problem, then ${\cal
S^{\prime}}=\\{S^{\prime}_{1},S^{\prime}_{2},\ldots,S^{\prime}_{k^{\prime}}\\}$
is a solution of the maximum set packing problem, where ${\cal P}\cap{\cal
F^{\prime\prime}}=\\{S^{\prime}_{1}\cup T^{\prime}_{1},S^{\prime}_{2}\cup
T^{\prime}_{2},\ldots,S^{\prime}_{k^{\prime}}\cup T^{\prime}_{k^{\prime}}\\}$.
Thus we will prove that the time to solve the maximum set packing problem is
bounded by the total time of transforming the maximum set packing problem into
the mutually exclusive set cover, and of solving the mutually exclusive set
cover problem. Therefore, the mutually exclusive set cover problem is NP-hard.

As subsets in ${\cal P}$ are pairwise disjoint, it is obvious that subsets in
${\cal S^{\prime}}$ are pairwise disjoint. Hence, if we suppose that ${\cal
S^{\prime}}$ is not the solution of the maximum set packing problem, then
there must exists a ${\cal
S^{\prime\prime}}=\\{S^{\prime\prime}_{1},S^{\prime\prime}_{2},\ldots,S^{\prime\prime}_{k^{\prime}}\\}\subset{\cal
S}$ such that subsets in ${\cal S^{\prime\prime}}$ are pairwise disjoint and
$k^{\prime}>k$. Thus we can make a new solution ${\cal P^{\prime}}$ of the
mutually exclusive set cover problem such that ${\cal P^{\prime}}$ includes
$\\{S^{\prime\prime}_{1}\cup T^{\prime\prime}_{1},S^{\prime\prime}_{2}\cup
T^{\prime\prime}_{2},\ldots,S^{\prime\prime}_{k^{\prime}}\cup
T^{\prime\prime}_{k^{\prime}}\\}\subset{\cal F^{\prime\prime}}$ and other
subsets in ${\cal F^{\prime}}$ and ${\cal F^{\prime\prime\prime}}$. If let
$|X^{\prime}-\cup_{i=1}^{k}S^{\prime}_{i}|=n_{1}$ and
$|X^{\prime}-\cup_{i=1}^{k^{\prime}}S^{\prime\prime}_{i}|=n_{2}$ (Note: any
$T_{i}$, which is not covered by a subset in ${\cal F^{\prime\prime}}$, needs
$n+1$ subsets in ${\cal F^{\prime\prime\prime}}$ to cover it; any $x_{i}\in
X^{\prime}$, which is not covered by a subset in ${\cal F^{\prime\prime}}$,
needs a subset in ${\cal F^{\prime}}$ to cover it), then

$|{\cal P}|=k+(m-k)(n+1)+n_{1},~{}~{}$

and

$|{\cal P^{\prime}}|=k^{\prime}+(m-k^{\prime})(n+1)+n_{2}.$

Therefore $|{\cal P}|-|{\cal P^{\prime}}|=(k^{\prime}-k)n+n_{1}-n_{2}>0$, i.e.
${\cal P^{\prime}}$ is a solution with less subsets in ${\cal F}$, which cases
contradiction that ${\cal P}$ is the solution of the mutually exclusive set
cover problem. Hence, ${\cal S^{\prime}}$ is a solution of the maximum set
packing problem.

##  3 The main Algorithm

In this section, we will introduce our new algorithm to solve the weighted
mutually exclusive set cover problem.

Let $(X,{\cal F},w)$ be an instance of the weighted mutually exclusive set
cover problem. We can use a bipartite graph to represent $(X,{\cal F},w)$ such
that all nodes on one sides are subsets in ${\cal F}$ while nodes on the other
side are elements in $X$, and if an element $u$ of $X$ is in subset $U$, i.e.
$u\in U$, then an edge is added between $u$ and $U$. For the convenience, let
us introduce some notations. The Figure 1 can help you to understand and
remember following notations.

Figure 1: Graph representation and some notations of the problem

For any $x\in X$, let $neighbor(x)=\\{S|S\in{\cal F}\text{ and }x\in S\\}$,
$degree(x)=|neighbor(x)|$, $partner(x)=\cup_{S\in neighbor(x)}S$. For any $y$
in $partner(x)$, let $neighbor_{in}=neighbor(y)\cap neighbor(x)$,
$degree_{in}(y)=|neighbor_{in}(y)|$, $neighbor_{out}=neighbor(y)-neighbor(x)$,
$degree_{out}(y)=|neighbor_{out}(y)|$.

Algorithm-1 WMES-Cover$((X,{\cal F},w),Solution_{partial},Solution_{final}))$
---
Input: An instance of the weighted mutually exclusive set cover problem, two
variables,
|  |  |  where $Solution_{final}$ is a global variable to keep the best solution.
Output: A minimum weight mutually exclusive set cover or “No Solution”.
1 |  if $X==\emptyset$ then
1.1 |  |  if $weight(Solution_{partial})<weight(Solution_{final})$ then replace $Solution_{final}$ with $Solution_{patial}$;
2 |  Find $x\in X$ such that $d=degree(x)$ is minimized;
3 |  if $d==0$ then return “No Solution”;
4 |  if $d==1$ then WMES-Cover$((X-\\{x\\},{\cal F}-neighbor(x),w),Solution_{partial}\cup neighnor(x),Solution_{final})$;
5 |  if $degree_{out}(y)==0$ for all $y\in partner(x)$ then
5.1 |  |  if there exists $S\in neighbor(x)$ such that $S==partner(x)$ then
5.1.1 |  |  |  WMES-Cover$((X-S,{\cal F}-neighbor(x),w),Solution_{partial}\cup\\{S\\},Solution_{final})$;
|  | else
5.1.2 |  |  |  return “No Solution”;
6 |  if $d==2$ then // Suppose $neighbor(x)=\\{S_{1},S_{2}\\}$; note that $S_{1}\subset X$ and $S_{2}\subset X$.
6.1 |  |  WMES-Cover$((X-S_{1},{\cal F}-\cup_{u\in S_{1}}neighbor(u),w),Solution_{partial}\cup\\{S_{1}\\},Solution_{final})$;
6.2 |  |  WMES-Cover$((X-S_{2},{\cal F}-\cup_{u\in S_{2}}neighbor(u),w),Solution_{partial}\cup\\{S_{2}\\},Solution_{final})$;
|  else // (Note: $d>2$)
6.3 |  |  if there exists a $y\in partner(x)$ such that $degree_{out}(y)=1$ then
6.3.1 |  |  |  Let $y\in partner(x)$ such that $degree_{out}(y)=1$ and $W^{\prime}\in neighbor_{out}(y)$;
6.3.2 |  |  |  if $|neighbor(x)-neighbor(y)|>0$ then // (Note: $|neighbor(x)-neighbor(y)|\leq 1$)
6.3.2.1 |  |  |  |  Find any $W\in neighbor(x)-neighbor(y)$;
6.3.2.2 |  |  |  |  WMES-Cover$((X-W^{\prime}\cup W,{\cal F}-\cup_{u\in W^{\prime}\cup W}neighbor(u),w),Solution_{partial}\cup\\{W^{\prime},W\\},Solution_{final})$;
6.3.2.3 |  |  |  |  WMES-Cover$((X,{\cal F}-\\{W^{\prime},W\\},w),Solution_{partial},Solution_{final})$;
|  |  | else
6.3.2.4 |  |  |  |  Find any $W\in neighbor(x)$;
6.3.2.5 |  |  |  |  WMES-Cover$((X-W,{\cal F}-\cup_{u\in W}neighbor(u),w),Solution_{partial}\cup\\{W\\},Solution_{final})$;
6.3.2.6 |  |  |  |  WMES-Cover$((X,{\cal F}-\\{W^{\prime},W\\},w),Solution_{partial},Solution_{final})$;
|  | else
6.3.3 |  |  |  Find a $y\in partner(x)$) such that $degree_{out}(y)$ is maximized;
6.3.4 |  |  |  Find a $Z\in neighbor_{in}(y)$;
6.3.5 |  |  |  WMES-Cover$((X-Z,{\cal F}-\cup_{u\in Z}neighbor(u),w),Solution_{partial}\cup\\{Z\\},Solution_{final})$;
6.3.6 |  |  |  WMES-Cover$((X,{\cal F}-\\{Z\\},w),Solution_{partial},Solution_{final})$;
Figure 2: Algorithm for the weighted mutually exclusive set cover problem.

The main algorithm, Algorithm-1, is shown in Figure 2. Basically, the
Algorithm-1 first finds an $x\in X$ with minimum degree and then branches at
one subset in $neighbor(x)$ (such as in step 6.2.2 and 6.2.3). For the
convenience, if $degree(x)=d$, then we say that Algorithm-1 is doing a
$d$-branch. Because of steps 3,4,5, when the program arrives at step 6, we
must have: 1) $d=degree(x)\geq 2$; 2) for any $u\in X$, $degree(u)\geq d$; 3)
there exists a $y\in partner(x)$ such that $degree_{out}(y)>0$.

The Algorithm-1 is basically searching the solution by going through a search
tree; hence, if knowing the number of leaves in the search tree, then we will
obtain the time complexity of the Algorithm-1. Next, we will estimate the
number of leaves in the search tree by studying the different cases of
branching. We begin from the $2$-branch.

###### Proposition 3.1

The search tree has at most $1.273^{m}$ leaves If only the 2-branches are
applied in Algorithm-1.
Proof.  Suppose that $degree(x)=2$ and $y\in partner(x)$ such that
$degree_{out}(y)>0$. Let $neighbor(x)=\\{S_{1},S_{2}\\}$.

In the case of $degree_{out}(y)=1$, let
$neighbor_{out}(y)=\\{S^{\prime\prime}\\}$. In the branches of choosing either
$S_{1}$ or $S_{2}$ into the solution, if $y$ is covered, then
$S^{\prime\prime}$ will be removed from the ${\cal F}$, or else if $y$ is not
covered yet, then $S^{\prime\prime}$ will be chosen into the solution in order
to cover $y$ (note: after $S_{1},S_{2}$ are removed, $degree(y)=1$ in the new
instance (at line 6.1.1 and 6.1.2 of Algorithm-1); thus, $S^{\prime\prime}$
will be included into the solution in the next call of the Algorithm-1 in this
branch). Hence, in any case, $3$ subsets in ${\cal F}$ will be removed. If
letting $T(k)$ be the number of leaves in the search tree when $|{\cal F}|=k$,
then we will obtain the following recurrence relation

$T(k)\leq
2T(k-3).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(1)}$

The characteristic equationof this recurrence relation is $r^{3}-2=0$ ‡
††footnotetext: ‡Note: Given a recurrence relation
$T(k)\leq\sum_{i=0}^{k-1}c_{i}T(i)$ such that all $c_{i}$ are nonnegative real
numbers, $\sum_{i=0}^{k-1}c_{i}>0$, and $T(0)$ represents the leaves, then
$T(k)\leq r^{k}$, where $r$ is the unique positive root of the characteristic
equation $t^{k}-\sum_{i=0}^{k-1}c_{i}t^{i}=0$ deduced from the recurrence
relation [3].; hence, we will have $T(m)<1.260^{m}$.

In the case of $degree_{out}(y)>1$, we consider following sub-cases.

Sub-case 1. Suppose $degree_{in}(y)=1$, and $y\in S_{1}$. Then at least
$S_{1}$ and $S_{2}$ will be removed from ${\cal F}$ for the branch of choosing
$S_{2}$ into the solution; at least $S_{1}$, $S_{2}$, and all subsets (at
least two) in $neighbor_{out}(y)$ will be removed for the branch of choosing
$S_{1}$ into the solution. Thus the recurrence relation of $T(k)$ is

$T(k)\leq
T(k-2)+T(k-4).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(2)}$

which leads to $T(m)<1.273^{m}$.

Sub-case 2. Suppose $degree_{in}(y)=2$. Then in either branch, $y$ is covered
by $S_{1}$ or $S_{2}$, which is chosen into the solution. Hence,
$S_{1},S_{2}$, and all subsets (at least two) in $neighbor_{out}(y)$ will be
removed from ${\cal F}$. Thus we will obtain the recurrence relation

$T(k)\leq
2T(k-4).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(3)}$

which leads to $T(m)<1.190^{m}$.

By considering all above cases, we obtain that $T(m)\leq 1.273^{m}$.

Now, we consider the case of doing $3$-branch. Remember that when Algorithm-1
is doing a $3$-branch, $degree(x)\geq 3$ for all $x\in X$.

###### Proposition 3.2

The search tree has at most $1.299^{m}$ leaves If only the $d$-branches for
$d<=3$ are applied in Algorithm-1.
Proof.  The cases of $2$-branches are considered in the last proposition. Now
we consider the cases of $3$-branches. Suppose that $degree(x)=3$ and $y\in
partner(x)$ such that $degree_{out}(y)>0$. Let
$neighbor(x)=\\{S_{1},S_{2},S_{3}\\}$.

If $degree_{out}(y)=1$, then $degree_{in}(y)\geq 2$ (as $degree(y)\geq 3$).
Let $\\{S^{\prime}\\}=neighbor_{out}(y)$. We further consider following sub-
cases.

Sub-case 1. Suppose $degree_{in}(y)=2$. Let $S_{1}\in
neighbor(x)-neighbor(y)$. The Algorithm-1 branches at $S_{1}$. The branch one
includes $S_{1}$ into the solution; thus, $S_{2},S_{3}$ will be removed. This
will further make $degree(y)=1$. Hence, $S^{\prime}$ will also be included
into the solution. Totally, in this branch, we will remove at least $4$
subsets from ${\cal F}$. In branch two, we will exclude $S_{1}$ from the
solution. Then either $S_{2}$ or $S_{3}$ must be included into the solution.
Thus $y$ is covered by $S_{2}$ or $S_{3}$, and $S^{\prime}$ will not be in the
solution. Therefore, in this branch, we know that at least $S_{1}$ and
$S^{\prime}$ will be removed. So we will obtain the recurrence relation

$T(k)\leq
T(k-2)+T(k-4),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(4)}$

which leads to $T(m)<1.273^{m}$.

Sub-case 2. Suppose $degree_{in}(y)=3$. Then $S^{\prime}$ will not in the
solution and any one of $S_{1},S_{3},S_{3}$ (one and only one of them must be
included into the solution to cover $x$) will cover $y$. The Algorithm-1 will
branch at any one of $S_{1},S_{2},S_{3}$. Without loss of generality, we
branch at $S_{1}$. In the branch of including $S_{1}$ into the solution,
$S_{1},S_{2},S_{3}$ will be removed, which will totally remove at least $4$
subsets. In the branch of excluding $S_{1}$ into the solution, $S_{1}$ will be
removed. Thus $2$ subsets will be removed. We will obtain the following
recurrence relation

$T(k)\leq
T(k-2)+T(k-4),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(5)}$

which leads to $T(m)<1.273^{m}$.

In the case of $degree_{out}(y)>1$, Let $S_{1}\in neighbor_{in}(y)$.
Algorithm-1 branches at $S_{1}$. In the first branch, $S_{1}$ is included into
the solution. Then $S_{1},S_{2},S_{3}$ and at least $2$ subsets in
$neighbor_{out}(y)$ will be removed. In the second branch, $S_{1}$ is
excluded, which will make $degree(x)=2$ in the new instance; hence, in this
branch, a $2$-branch will follow. Thus even considering the worst case of the
$2$-branch (the recurrence relation (2)), we will have

$T(k)\leq
2T(k-5)+T(k-3),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(6)}$

which will lead to $T(m)\leq 1.299^{m}$.

From all above cases and Proposition 3.1, we will have $T(m)\leq 1.299^{m}$.

Let us consider the case of doing $d$-branch for $d>3$.

###### Proposition 3.3

The search tree in Algorithm-1 has at most $1.299^{m}$ leaves.
Proof.  We only need to consider the cases of $d$-branches for $d>3$. Suppose
that $degree(x)=d$ and $y\in partner(x)$ such that $degree_{out}(y)>0$. Let
$neighbor(x)=\\{S_{1},S_{2},\ldots,S_{d}\\}$.

In the case of $degree_{out}(y)=1$, $degree_{in}(y)$ can only be $d-1$ or $d$.

Sub-case 1. Suppose $degree_{in}(y)=d-1$. Then there is one and only one
subset in $neighbor(x)-neighbor_{in}(y)$. Without loss of generality, we
suppose $S_{1}\not\in neighbor_{in}(y)$. Algorithm-1 will branch on $S_{1}$
such that in the branch of including $S_{1}$ into the solution, all $d$
subsets in $neighbor(x)$ and one subset in $neighbor_{out}(y)$ will be removed
(i.e. in this branch, at least $5$ subsets will be removed; in the branch of
excluding $S_{1}$ from the solution, one subset in
$\\{S_{2},S_{3},\ldots,S_{d}\\}$ will be included into the solution, which $y$
will be covered and the only subset in $neighbor_{out}(y)$ will be removed
(i.e. in this branch, two subsets will be removed). Therefore, we will have
following recurrence relation

$T(k)\leq
T(k-5)+T(k-2),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(7)}$

which leads to $T(m)<1.237^{m}$.

Sub-case 2. Suppose $degree_{in}(y)=d$. Without loss of generality, we suppose
that Algorithm-1 branches on $S_{1}$. Then it is easy to understand the we
will have the following recurrence relation

$T(k)\leq
T(k-5)+T(k-2),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(8)}$

which leads to $T(m)<1.237^{m}$.

In the case of $degree_{out}(y)>1$, suppose $S_{1}\in degree_{in}(y)$ and
Algorithm-1 branches on $S_{1}$. Then in the branch of including $S_{1}$ into
the solution, all subsets in $neighbor(x)$ and $neighbor_{out}(y)$ will be
removed (at least $6$ subsets will be removed). In the branch of excluding
$S_{1}$ into the solution, at least one subset $S_{1}$ will be removed. Hence,
we will have the recurrence relation

$T(k)\leq
T(k-6)+T(k-1),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(9)}$

which leads to $T(m)<1.286^{m}$.

Considering all above cases, Proposition 3.1, and Proposition 3.2, we have
$T(m)\leq 1.299^{m}$.

###### Theorem 3.4

The weighted mutually exclusive set cover problem can be solved by an
algorithm with a time complexity of $O^{*}(1.299^{m})$.
Proof.  Let $({\cal F},X,w)$ be an instance of the weighted mutually exclusive
set cover problem, where $X$ is a ground set of $n$ elements, $\cal{F}$ is a
collection of $m$ subsets of $X$, and $w:{\cal F}\rightarrow[0,\infty)$ is the
weight function. Now we prove that the problem can be solved by the
Algorithm-1 in time $O^{*}(1.299^{m})$.

The correctness of the algorithm is easy to understand. If there is an $x\in
X$ such that $degree(x)=0$, then $x$ cannot be covered by any subset in ${\cal
F}$. Thus, the problem has no solution. The step 3 of the Algorithm-1 deals
with this situation. If, for any given $x\in X$, $degree(x)=1$, then there
exists one and only one subset in ${\cal F}$ that covers $x$, i.e.
$neighbor(x)$ must be included into the solution. Thus $x$ and $neighbor(x)$
will be removed from the problem. This situation is dealt with in step 4. If
for all $y$ in $partner(x)$, $degree_{out}(y)=0$, then $partner(x)$ can only
be covered by subset(s) in $neighbor(x)$. By the exclusivity, at most one
subset in $neighbor(x)$ can be chosen into the solution. Thus, if finding a
subset $S$ in $neighbor(x)$ such that $S=partner(x)$, then Algoirhtm-1 will
include $S$ into the solution, or else the problem has no solution. The step 5
of the Algorithm-1 deals with this situation.

After the Algorithm-1 reaches step 6, we have: 1) for all $x^{\prime}\in X$,
$degree(x^{\prime})\geq degree(x)>1$ (as $x$ is the element in $X$ with the
minimum degree); 2) there is a $y\in partner(x)$ such that
$degree_{out}(y)>0$. If $d=neighbor(x)=2$, then one and only one subset in
$neighbor(x)$ will be in the solution. The step 6.1 and 6.2 correctly deals
with this situation. For the cases after step 6.2, the Algorithm-1 basically
chooses one subset $S$ in $neighbor(x)$ and branches on $S$ such that one
branch includes $S$ into the solution and the other branch excludes $S$ from
the solution (Note: when $degree_{out}(y)=1$, we used a small trick to include
or exclude the additional subset in $neighbor_{our}(y)$ into or from the
solution; please refer to sub-case 1 and sub-case 2 in the Proposition 3.3).
Therefore, Algorithm-1 will go through the search tree and find the solution
with the minimum weight (if the solution exists), which is saved in step 1.1.

By Proposition 3.3, the search tree has at most $1.299^{m}$ leaves. Hence, the
time complexity of the algorithm is bounded by $O^{*}(1.299^{m})$. If we
further notice that the time to process each node is bounded by $O(mn)$, then
the more accurate time complexity of the algorithm is $O(1.299^{m}mn)$.

##  4 Problem extension

In this paper, we first proved that the weighted mutually exclusive set cover
problem is NP-hard. Then we designed the first non-trivial algorithm, which
uses the $m$ as parameter, with a time complexity of $O^{*}(1.352^{m})$ for
the problem. the weighted mutually exclusive set cover problem has been used
to find the driver mutations in cancers [4, 12]. Our new algorithm can find
the optimal solution for the problem, which is better than solutions found by
the heuristic algorithms in the previous research [4, 12]. The exclusivity is
the extreme case. In practical applications, a cancer cell may have more than
one mutation to perturb a common pathway. Hence, a modified model is finding a
set of mutations with minimum weight sum such that each cancer cell has at
least one and at most t (t=2 or 3) mutations in the solutions, which leads to
the small overlapped set cover problem. Also, on application, some mutations
in cancer cells may not be detected because of errors. Thus, it is not always
ideal to find a solution mutations that cover all cancer cells. A modified
model is finding a set of mutually exclusive mutations that cover at least $r$
percent ($90\%$ or $95\%$) of cancer cells, which leads to the maximal set
cover problem. Our next research will design efficient algorithms for above
two new problems.

## References

  * [1] N. Alon, D. Moshkovitz, and S. Safra, Algorithmic Construction of Sets for $k$-Restrictions, ACM Transaction on Algorithms, 2(2), pp. 153-177, 2006.
  * [2] A. Bjölund, T. Husfeldt, M. Koivisto, Set partitioning via Inclusion-Exclusion. SIAM Journal on Computing, Special Issue for FOCS 2006.
  * [3] J. Chen, I, Kanj, and W. Jia, Vertex Cover: Further Observations and Further Improvements, Journal of Algorithm, 41, pp. 280-301, 2001\.
  * [4] G. Ciriello, E. Cerami, C. Sander, N. Schultz, Mutual exclusivity analysis identifies oncogenic netwrok modules, Genome research, 22(2), pp. 398-406, 2012.
  * [5] U. Feige, A Threshold of $\ln n$ for Approximation Set Cover, J. of the ACM, 45(4), pp. 634-652, 1998.
  * [6] H. Fernau, a top-down approach to search-trees: Improved algorithmics for $3$-Hitting Set, Algorithmica, 57, pp. 97-118, 2010\.
  * [7] Q. Hua, Y. Wang, D. Yu, F. Lau, Dynamic programming based algorithms for set multicover and multiset multicover problem. Theoretical Computer Science V411, pp. 2467-2474, 2010.
  * [8] R. Karp, Reducibility Among Combinatorial Problems, In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum, pp. 85-103, 1972.
  * [9] S. Kolliopoulos, N. Young, Approximation algorithms for covering/packing integer programs. J. Comput. Syst. Sci. 71(4), pp.495-505, 2005.
  * [10] S. Lu, X. Lu, A graph model and an exact algorithm for finding transcription factor modules, 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine, pp. 355-359, 2011.
  * [11] C. Lund, and M. Yannakakis, On the Hardness of Approximating Minimization Problem, J. of the Association for Computing Machinery, 45(5), pp. 960-981, 1994.
  * [12] C. Miller, S. Settle, E. Sulman, K. Aldape, A. Milosavljevic, Discovering functional modules by identifying recurrent and mutually ecxlusive mutational patterns in tumors, BMC medical genomics, 4, pp. 34, 2011.
  * [13] R. Niedermeier, and P. Rossmanith, An Effcient Fixed-parameter Algorithm for 3-Hitting Set, J. of Discrete Algorithms, 1(1), pp. 89-102, 2003.


* (104) Y. Mehtar-Tani, J. G. Milhano and K. Tywoniuk, Int. J. Mod. Phys. A 28 (2013), 1340013 doi:10.1142/S0217751X13400137 [arXiv:1302.2579 [hep-ph]].
  * (105) H. T. Li and I. Vitev, [arXiv:2010.05912 [hep-ph]].
  * (106) C. Andres, N. Armesto, H. Niemi, R. Paatelainen and C. A. Salgado, Phys. Lett. B 803 (2020), 135318 doi:10.1016/j.physletb.2020.135318 [arXiv:1902.03231 [hep-ph]].
  * (107) S. Klein, D. Tapia Takaki, J. Adam, C. Aidala, A. Angerami, B. Audurier, C. Bertulani, C. Bierlich, B. Blok and J. D. Brandenburg, et al. [arXiv:2009.03838 [hep-ph]].
  * (108) G. Aad et al. ATLAS, [arXiv:2101.10771 [nucl-ex]].
  * (109) G. Aad et al., ATLAS, Phys. Rev. Lett. 123 (2019) no.5, 052001 doi:10.1103/PhysRevLett.123.052001 [arXiv:1904.03536 [hep-ex]].
  * (110) V. Bertone, M. Cacciari, S. Frixione and G. Stagnitto, JHEP 03 (2020), 135 doi:10.1007/JHEP03(2020)135 [arXiv:1911.12040 [hep-ph]].