# Clique Cover of Graphs with Bounded Degeneracy

Ahammed Ullah Purdue University

###### Abstract

Structural parameters of graph (such as degeneracy and arboricity) had rarely
been considered when designing algorithms for _(edge) clique cover_ problems.
Taking degeneracy of graph into account, we present a greedy framework and two
fixed-parameter tractable algorithms for _clique cover_ problems. We introduce
a set theoretic concept and demonstrate its use in the computations of
different objectives of _clique cover_. Furthermore, we show efficacy of our
algorithms in practice.

##  1 Introduction

A set of cliques $\mathcal{C}$ is an _(edge) clique cover_ of an undirected
graph if every edge of the graph is contained in at least one of the cliques
in $\mathcal{C}$. Computing a _clique cover_ with smallest number of cliques
is an NP-hard problem [59], and the problem is constant-factor inapproximable
unless $P=NP$ [49]. _Clique cover_ problems abstract an abundance of real-
world problems, arising in resource scheduling [64], causal structure learning
[51], stringology [[39], [53]], computational biology [[6], [12], [27], [57],
[58]], computational geometry [1], graph drawing [21], computer security [19],
database tiling [33], finite automata [37], compiler optimization [63],
overlapping community detection [68], and applied statistics [[20], [36],
[60]].

In the realm of parameterized complexity [[13], [18], [28]], a parameterized
problem $L\subseteq\sum^{*}\times\mathbb{N}$ is called fixed-parameter
tractable (FPT), if any $(x,p)\in L$ is decidable in time
$f(p).|(x,p)|^{O(1)}$, where $f(p)$ is computable and is independent of $x$,
but can grow arbitrarily with $p$. An algorithm is called fixed-parameter
tractable algorithm, if it decides $(x,p)\in L$ in time bounded by
$f(p).|(x,p)|^{O(1)}$. A parameterized decision problem of _clique cover_ is
as follows.

ECC Input: An undirected graph $G=(V,E)$, and a nonnegative integer $k$.
Output: If exists, a set of at most $k$ cliques of $G$ such that every edge of
$G$ is contained in at least one of the cliques in the set; otherwise ’no’.

_ECC_ is fixed-parameter tractable with respect to parameter $k$ [34]. Using
polynomial time data reduction rules, [34] have shown a kernel with $2^{k}$
vertices, and a search tree algorithm with time bound double exponential in
$k$. Unless the polynomial hierarchy collapses, no polynomial kernel exists
for _ECC_ [14]. Moreover, double exponential dependence on $k$ is necessary,
assuming the exponential time hypothesis [15].

In general, $k$ (clique cover size) is large [[2], [24], [30], [38], [62],
[64]], specially for sparse graphs. The results on lower bound of $k$, and the
results of [14] and [15] imply limited scope of designing tractable FPT
algorithms with $k$ as only parameter. Therefore, it is worthy exploring
different structural parameters of graph, such as degeneracy (a sparsity
measure of graph), as additional parameters along with $k$.

We follow the definitions of degeneracy by [23]. Degeneracy of a graph
$G=(V,E)$ is the smallest value $d$ such that every non-empty subgraph of $G$
contains a vertex of degree at most $d$ [48]. Equivalently, $d$ is the minimum
value for which $G$ has an orientation as a directed acyclic graph in which
all vertices have out-degree at most $d$ [10]. _Degeneracy ordering_ of $G$ is
an ordering of vertices in $V$ such that each vertex has at most $d$ neighbors
that come later in the ordering. Degeneracy ordering is computable in linear
time [52].

_Degeneracy_ is within a constant factors of other popular sparsity measures
of graph such as arboricity [[31], [46]] and thickness [17], and is also at
most equal to the treewidth [65] of graph; however, a graph may have bounded
degeneracy, but unbounded treewidth, for example, grid graphs. Degeneracy is
also known as the k-core number [4], width [29], linkage [43], and is
equivalent to the coloring number [25].

Throughout the paper we use following notations. For a graph $G=(V,E)$,
$n=|V|$ is the number of vertices, $m=|E|$ is the number of edges, $N(x)$
denote the set of neighbours of a vertex $x\in V$, $\Delta$ is maximum degree
of the vertices, and $d$ is the degeneracy of $G$. Let $u_{1},u_{2},...,u_{n}$
be a degeneracy ordering of $V$. $N_{d}(u_{i})$ denotes neighbours of $u_{i}$
that follow $u_{i}$ in the degeneracy order of $V$, i.e.,
$N_{d}(u_{i})=N(u_{i})\cap\\{u_{i+1},...,u_{n}\\}$. The definition of fixed-
parameter tractability encompasses more general cases such as when $p$ is a
vector of nonnegative integers. Let _ECC-d_ be the variant of the
parameterized decision problem _ECC_ that considers degeneracy of $G$
explicitly as parameter along with $k$. Suppressing factors polynomial in
input size, we express time bound of an FPT algorithm with $O^{*}(f(p))$.

###  1.1 Our Contributions.

We introduce a set theoretic concept (we call it _candidate clique sets_)
closely related to family of sets representing vertices of an intersection
graph [54] and use it to design greedy algorithms and FPT algorithms.

We define a greedily computable _clique cover_ and show that it admits
desirable characterizations. Combining _candidate clique sets_ with different
objectives of _clique cover_ , we derive characterizations useful in designing
and analyzing algorithms.

Using our derived characterizations, we describe a basic greedy framework that
can compute a _minimal_ (inclusion-wise) _clique cover_ in $O(m^{2})$ time.

We make use of _candidate clique sets_ and related characterizations to
improve the time bound of our greedy framework; for graphs of constant maximum
degree, this results in a family of linear time algorithms. We make the
improved greedy framework amenable to utilize degeneracy of input graph; this
also results in a family of linear time algorithms, for graphs of constant
degeneracy.

We present two FPT algorithms for _ECC-d_ with respect to parameter $(d,k)$.
One of our FPT algorithm is based on _candidate clique sets_ , and the other
FPT algorithm is based on maximal clique enumeration (listing all maximal
cliques in graph [23]). For graphs of constant degeneracy, time bounds of our
FPT algorithms have single exponential dependence on $k$.

For graphs satisfying $2^{k}>d$, our maximal clique enumeration based FPT
algorithm improves upon the time bound of the search tree algorithm of [34] by
a factor of $3^{k(2^{k}-d)}$.

Our greedy framework and FPT algorithm based on _candidate clique sets_
demonstrate a general design paradigm for different objectives of _clique
covers_. For example, we easily obtain a search tree algorithm for the
_assignment-minimum clique cover_ (_clique cover_ with a minimum total number
of vertices across all cliques) [[20], [36], [60]] with depth, number of
branches, and space use all bounded by polynomials in input size. Prior search
tree algorithm designed for this objective of _clique cover_ requires bounds
exponential in input size for depth, number of branches, and space use [20].

Our algorithms show excellent performance in practice. We show comparison
results of different metrics of our algorithms against the state of the art,
on random graphs, as well as on real-world graphs.

##  2 Related Works

Computing _clique cover_ with a minimum number of cliques is NP-hard [59],
even for planar graphs [9], or graphs with maximum degree six [40], whereas
the problem is solvable in polynomial time for some restricted classes of
graphs such as graphs with maximum degree five [40], chordal graphs [50], line
graphs [59], certain generalizations of line graphs [61], and circular-arc
graphs [41]. The minimum cardinality _clique cover_ problem is not
approximable within a factor of $n^{\epsilon}$, for some $\epsilon>0$ unless
$P=NP$ [49]; nothing better than a polynomial approximation ratio of
$O(n^{2}\frac{(\log\log n)^{2}}{(\log n)^{3}})$ is known [3]. Unlike _vertex
clique cover_ (set of disjoint cliques covering vertices of a graph;
equivalent to coloring the complement graph), _edge clique cover_ is fixed-
parameter tractable with respect to natural parameterization [35]. [6]
presented an FPT algorithm for _clique cover_ parameterized by treewidth. For
planar graphs, [6] also presented an FPT algorithm using branchwidth as
parameter and a polynomial-time approximation schemes. Several other
objectives of _clique cover_ also have been shown to be FPT including _clique
cover_ objectives that consider edge weights [[8], [12], [26], [56]].

Kellerman presented a heuristic algorithm (Kellerman heuristic) to solve
keyword conflict problem [42], equivalent to _clique cover_ [45]. [45]
proposed an extension to the Kellerman heuristic. Including the extension, the
time bound of the Kellerman heuristic is $O(nm^{2})$ [34]. Using additional
data structures, [34] improved the time bound to $O(nm)$. [11] presented a
general framework of heuristic algorithms and evaluated the framework for
different objectives of _clique cover_. Variants of algorithms from the
framework of [11] have $O(m\Delta)$ or $O(md)$ time bound. Improvement of
Kellerman heuristic [34] or heuristics proposed by [11] outperform other
heuristic algorithms [[36], [39], [60]] developed for the problem. [5]
designed a polynomial time algorithm that is asymptotically optimal for
certain random intersection graphs, but for arbitrary graphs, this algorithm
may not compute a _clique cover_.

##  3 Key Concepts

In this section we present a greedily computable _clique cover_ and its
characterizations. We introduce a set theoretic concept (_candidate clique
sets_) closely related to family of sets representing vertices of an
intersection graph. For the computations of different objectives of _clique
cover_ , we derive useful characterizations of _candidate clique sets_.

$1$$5$$3$$6$$2$$4$ Figure 1: A graph with six vertices and ten edges.

######  Definition 3.1 (Minimum Clique Cover)

A _minimum clique cover_ of a graph $G$ is a _clique cover_ with smallest
number of cliques among all _clique covers_ of $G$.

For the example graph of Figure 1, a _minimum clique cover_ is
$\mathcal{C}=\\{\\{1,3,5\\},\\{2,3,4\\},\\{3,4,5,6\\}\\}$. In this case all
the cliques of the _minimum clique cover_ are maximal cliques. But having a
_clique cover_ consisting only of maximal cliques is neither necessary nor
sufficient for a _minimum clique cover_.

######  Definition 3.2 (Minimal Clique Cover)

A _minimal clique cover_ $\mathcal{C}$ of a graph $G$ is a _clique cover_ of
$G$ such that no other _clique cover_ of $G$ is contained in $\mathcal{C}$,
i.e., $\mathcal{C}$ is an inclusion-wise minimal set of cliques that covers
all the edges of $G$.

A _minimum clique cover_ is also a _minimal clique cover_. Note that from a
_minimal clique cover_ it may be possible to remove vertices (or edges), given
that such removals still maintain a _clique cover_ of $G$. Any such removal of
vertices (or edges) from a _minimal clique cover_ would not affect number of
cliques in the _clique cover_.

In the example graph of Figure 1,
$\mathcal{C}=\\{\\{1,3,5\\},\\{2,3,4\\},\\{4,5,6\\},\\{3,6,5\\}\\}$ is a
_minimal clique cover_ of the graph, and size of the _clique cover_ is four.
From the clique $\\{3,6,5\\}$, we can remove vertex 5 (hence edges $\\{3,5\\}$
and $\\{6,5\\}$), but the size of the _clique cover_ would still be four.

It is easy to construct a _minimal clique cover_ by covering every edge with a
clique containing only the edge. But, computing a _minimal clique cover_ with
some desirable characterizations does not seem to be straightforward.
Therefore, we define a type of _clique cover_ that admits desirable
characterizations and can be efficiently turned into a _minimal clique cover_
, preserving the characterizations.

######  Definition 3.3 (Locally Minimal Clique Cover)

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a _clique cover_ of a subset
of edges of $G=(V,E)$, and $\\{x,y\\}$ be an uncovered edge of $G$. Let
$\mathcal{C}^{{}^{\prime}}$ be a clique cover of the edges covered in
$\mathcal{C}$ together with the edge $\\{x,y\\}$ constructed as follows.

(i) If edge $\\{x,y\\}$ can be covered by a clique contained in $\mathcal{C}$,
then we set $\mathcal{C}^{{}^{\prime}}$ to be a clique cover in which
$\\{x,y\\}$ is covered with exactly one of the cliques of $\mathcal{C}$ and
rest of the cliques of $\mathcal{C}$ are included.

(ii) Otherwise, we create a new clique $C_{k+1}$ containing only $\\{x,y\\}$,
and we set $\mathcal{C}^{{}^{\prime}}$ to be $\mathcal{C}\cup\\{C_{k+1}\\}$.

We call a _clique cover_ $\mathcal{C}$ _locally minimal_ if $\mathcal{C}$ is
obtained from an empty clique cover using aforesaid construction; i.e., for
every expansion of the cliques contained in $\mathcal{C}$, we either have used
(i) whenever applicable, or (ii) otherwise.

Note that a _locally minimal clique cover_ only ensures local minimality with
respect to an uncovered edge of interest; it does not ensure minimality with
respect to the edges already included in the clique cover. Nevertheless, it
allows characterizations of _clique covers_ desirable for designing and
analyzing algorithms.

###### Lemma 3.1

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a clique cover of a subset of
edges of $G=(V,E)$. If $\mathcal{C}$ is _locally minimal_ , then each vertex
$x$ appears at most $|N(x)|$ times in $\mathcal{C}$.

  * Proof.

Since $\mathcal{C}$ is _locally minimal_ , for an uncovered edge $\\{x,y\\}$
covered during the expansion of clique cover at hand, we can trace use of the
two rules described in Definition 3.3. Let $C^{{}^{\prime}}$ be the clique
cover immediately before covering the edge $\\{x,y\\}$. Before the expansion
of $C^{{}^{\prime}}$ for $\\{x,y\\}$, none of the cliques in $C^{{}^{\prime}}$
contained both $x$ and $y$: if $x$ and $y$ are both contained in a clique of
$C^{{}^{\prime}}$, then clearly $\\{x,y\\}$ is not uncovered. Number of
uncovered edges $\\{x,y\\}$ incident on a vertex $x$ is at most $|N(x)|$.
Therefore, number of such expansions of a _clique cover_ for a vertex $x$ is
at most $|N(x)|$. Hence the vertex $x$ appears at most $|N(x)|$ times in
$\mathcal{C}$.

###### Remark 3.1

The converse of characterization in Lemma 3.1 does not hold; i.e., each $x\in
V$ can appear at most $|N(x)|$ times in $\mathcal{C}$, but $\mathcal{C}$ may
not be _locally minimal_.

###### Lemma 3.2

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a clique cover of a subset of
edges of $G=(V,E)$. If $\mathcal{C}$ is _locally minimal_ , then
$C_{i}\not\subseteq C_{j},\forall i,j\in[1,k],i\neq j$ (no clique in
$\mathcal{C}$ is contained in another clique).

  * Proof.

We prove the contrapositive, i.e., if for some $i,j\in[1,k],i\neq j$,
$C_{i}\subseteq C_{j}$, then $\mathcal{C}$ is not locally minimal.

WLOG assume $C_{i}$ is being created first, and consider the first uncovered
edge $\\{x,y\\}$ for which $C_{j}$ is being created. Since $C_{i}\subseteq
C_{j}$, at any stage of the construction, for any $z\in C_{i}$, three cases
can arise: (1) $x\in C_{i}$, $\\{y,z\\}\in E$, (2) $y\in C_{i}$, $\\{x,z\\}\in
E$, (3) $x\not\in C_{i}$, $y\not\in C_{i}$ and $\\{x,z\\}\in E$, $\\{y,z\\}\in
E$. Clearly, for any of the three cases, rule (i) of Definition 3.3 applies
for $\\{x,y\\}$, but, rule (ii) of Definition 3.3 is being applied. Therefore,
$\mathcal{C}$ is not _locally minimal_.

###### Remark 3.2

The converse of characterization in Lemma 3.2 does not hold; i.e., it is
possible that no clique in $\mathcal{C}$ is contained in another clique, but
$\mathcal{C}$ may not be _locally minimal_.

###### Lemma 3.3

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a clique cover of a subset of
edges of $G=(V,E)$. If $\mathcal{C}$ is _locally minimal_ , then
$\forall\\{C_{i},C_{j}\\}\in\mathcal{C},i\neq j,\exists x\in C_{i},y\in
C_{j}$, $x\neq y$ such that $\\{x,y\\}\notin E$ (every pair of cliques in
$\mathcal{C}$ corresponds to a pair of vertices not connected by an edge in
$G$).

  * Proof.

We prove the contrapositive, i.e., if for some
$\\{C_{i},C_{j}\\}\in\mathcal{C}$ with $i\neq j$, this is the case that
$\forall x\in C_{i}$ and $\forall y\in C_{j}$, $x\neq y$, $\\{x,y\\}\in E$,
then $\mathcal{C}$ is not locally minimal.

WLOG assume $\mathcal{C}_{i}$ is being created first, and consider the first
uncovered edge $\\{y,z\\}$ for which $\mathcal{C}_{j}$ is being created.
Clearly, $\forall x\in\mathcal{C}_{i}$, $\\{x,z\\}\in E$ and $\\{x,y\\}\in E$,
and rule (i) of Definition 3.3 applies for $\\{y,z\\}$, instead rule (ii) of
Definition 3.3 is being applied. Therefore, $\mathcal{C}$ is not _locally
minimal_.

###### Remark 3.3

_Clique cover_ satisfying Lemma 3.2 does not imply it satisfies Lemma 3.3.
But, _clique cover_ satisfies Lemma 3.3 implies no clique is contained in
another clique, i.e., Lemma 3.3 is a stronger characterization than Lemma 3.2.

Note that it is the combination of the characterizations in Lemma 3.1, Lemma
3.2, and Lemma 3.3 that makes a _locally minimal clique cover_ desirable than
each standalone characterization. For example, it is easy to satisfy the
characterizations in Lemma 3.1 and Lemma 3.2 for a complete graph by covering
every edge with a clique containing only the edge. But, characterization in
Lemma 3.3 ensures that a single clique covers the complete graph. We can also
glean more information on _locally minimal clique cover_ using these
characterizations further. The following is a characterization of possible
redundancy of cliques in a _locally minimal clique cover_ in respect of a
_minimal clique cover_.

###### Lemma 3.4

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a _locally minimal clique
cover_ of $G=(V,E)$, and for any clique $C_{l}\in\mathcal{C}$, let
$\mathcal{C}^{{}^{\prime}}\subseteq\mathcal{C}$ such that
$C_{l}\not\in\mathcal{C}^{{}^{\prime}}$. Let $A$ denote the set of edges
contained in $C_{l}$, and let $B$ denote the union of the edges contained in
the cliques of $\mathcal{C}^{{}^{\prime}}$. If $A\subseteq B$, then
$|\mathcal{C}^{{}^{\prime}}|\geq 3$.

  * Proof.

We prove the contrapositive, i.e., if $|\mathcal{C}^{{}^{\prime}}|<3$, then
$A\not\subseteq B$.

If $|\mathcal{C}^{{}^{\prime}}|=1$, then by Lemma 3.2, $C_{l}$ cannot be
contained in another clique in $\mathcal{C}$. Hence let
$\mathcal{C}^{{}^{\prime}}=\\{C_{i},C_{j}\\}$.

If $|C_{l}|=2$, then the single edge in $C_{l}$ cannot be contained in any
other clique, otherwise it would violate the _locally minimal_ property of
$\mathcal{C}$. Therefore, $|C_{l}|>2$.

Let $D=C_{l}\cap C_{i}$ and $F=C_{l}\cap C_{j}$. If $D=F$ then it must be the
case that $|C_{l}|>|D|$ and $|C_{l}|>|F|$; otherwise $\mathcal{C}_{l}\subseteq
C_{i}$ and $\mathcal{C}_{l}\subseteq C_{j}$, i.e., $\mathcal{C}$ is not
_locally minimal_. Therefore, we can assume $D\neq F$.

$D\not\subseteq F$ and $F\not\subseteq D$; otherwise, $C_{l}\subseteq C_{i}$
or $C_{l}\subseteq C_{j}$, and $\mathcal{C}$ is not _locally minimal_. Since
$D\not\subseteq F$ and $F\not\subseteq D$, it must be the case that for some
$x\in D$, $x\not\in F$, and also for some $y\in F$, $y\not\in D$. Edge
$\\{x,y\\}\in A$, but neither $C_{i}$ not $C_{j}$ contains the edge
$\\{x,y\\}$.

Lemma 3.4 implies that in order to remove any redundant clique from a _locally
minimal clique cover_ , we would need to consider at least three cliques at a
time. For a clique containing many vertices, we may need to consider a large
number of cliques at a time to discern whether a clique is redundant in a
_locally minimal clique cover_.

We obtain bounds for total number of (repeatable) vertices and total number of
(repeatable) edges in a _locally minimal clique cover_ as follows.

###### Lemma 3.5

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a clique cover of a subset of
edges of $G=(V,E)$. If $\mathcal{C}$ is locally minimal, then
$\sum_{C_{l}\in\mathcal{C}}|C_{l}|=O(m)$.

  * Proof.

From Lemma 3.1, any vertex $x$ can appear at most $|N(x)|$ times in the cover
$\mathcal{C}$. Therefore $\sum_{C_{l}\in\mathcal{C}}|C_{l}|=\sum_{x\in
V}|\\{C_{l}|x\in C_{l}\\}|\leq\sum_{x\in V}|N(x)|=O(m)$.

###### Lemma 3.6

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a clique cover of a subset of
edges of $G=(V,E)$. If $\mathcal{C}$ is locally minimal, then
$\sum_{\\{x,y\\}\in E}|\\{C_{l}|\\{x,y\\}\in
C_{l},C_{l}\in\mathcal{C}\\}|=O(m\Delta)$.

  * Proof.

Consider any edge $\\{x,y\\}\in E$. Since we know from Lemma 3.1 that $x\in V$
can appear at most $|N(x)|$ times in $\mathcal{C}$, both $x$ and $y$ can
appear at most $\min\\{|N(x)|,|N(y)|\\}$ times in $\mathcal{C}$. Summing over
all the edges we get $\sum_{\\{x,y\\}\in
E}\min{\\{|N(x)|,|N(y)|\\}}\leq\sum_{\\{x,y\\}\in E}\Delta=O(m\Delta)$. It
follows that

$\sum_{\\{x,y\\}\in E}|\\{C_{l}|\\{x,y\\}\in C_{l},C_{l}\in\mathcal{C}\\}|$

$\leq\sum_{\\{x,y\\}\in E}\min{\\{|N(x)|,|N(y)|\\}}=O(m\Delta)$

######  Definition 3.4 (Intersection Graph Basis)

Let $X=\\{1,2,...,k\\}$, and consider a family of $n$ sets
$\mathcal{F}=\\{F_{1},F_{2},...,F_{n}\\}$, with $F_{i}\subseteq X$. The
_intersection graph_ of $\mathcal{F}$ has vertices $F_{i},i\in[1,n]$, and an
edge joins $F_{i}$ and $F_{j}$ when $F_{i}\cap F_{j}\neq\phi$, with $i\neq j$.
Every graph $G=(V,E)$ arises as the intersection graph of some family of sets;
i.e., there is an assignment of a set $F_{i}$ to each vertex $i$ of $V$ such
that for $\\{i,j\\}\in V$, and $i\neq j$, the following holds: $\\{i,j\\}\in
E\Leftrightarrow F_{i}\cap F_{j}\neq\phi$. Computing _(edge) clique cover_ of
$G$ is equivalent to computing a set $X$ such that $G$ is the intersection
graph of a family of subsets of $X$ [24]. Such a set $X$ with minimum
cardinality is called an intersection graph basis of $G$ [32]. Every element
$l\in X$ corresponds to a clique such that $\\{F_{i}|l\in F_{i}\\}$ is the
vertex set of the clique.

Next, we introduce concepts related to family of sets representing vertices of
an _intersection graph_.

######  Definition 3.5 (Candidate Clique)

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a _clique cover_ of a subset
of edges of $G=(V,E)$. $C_{l}\in\mathcal{C}$ is a _candidate clique_ of $x\in
V$, if either (i) $x\in C_{l}$, or (ii) $x\not\in C_{l}$ and $C_{l}\subseteq
N(x)$.

Consider the example graph in Figure 1, and a clique cover
$\mathcal{C}=\\{\\{1,3,5\\},\\{4,5,6\\}\\}$ of a subset of edges of the graph.
The clique $\\{1,3,5\\}$ is a _candidate clique_ for all the vertices
contained in the clique. The clique $\\{4,5,6\\}$ is a _candidate clique_ for
vertex 3, since the vertices in the clique are contained among the neighbors
of vertex 3.

######  Definition 3.6 (Candidate Clique Set)

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a _clique cover_ of a subset
of edges of $G=(V,E)$. A _candidate clique set_ $S_{x}$ for a vertex $x$ is
the set of (indices of) _candidate cliques_ of $x$ in $\mathcal{C}$, i.e.,
$S_{x}=\\{l|x\in C_{l}\textit{ or }(x\not\in C_{l}\textit{ and }C_{l}\subseteq
N(x)),1\leq l\leq k\\}$.

###### Remark 3.4

For a family of sets $\mathcal{F}$ such that $G=(V,E)$ is the intersection
graph of $\mathcal{F}$, it is the case that $\\{x,y\\}\in V,x\neq y$ following
holds: $F_{x}\cap F_{y}\neq\phi\Leftrightarrow\\{x,y\\}\in E$. For _candidate
clique sets_ , $S_{x}\cap S_{y}\neq\phi$ does not imply $\\{x,y\\}\in E$.

For the example graph of Figure 1, let $\mathcal{C}=\\{C_{1},C_{2},C_{3}\\}$
be a clique cover of a subset of edges of the graph, where
$C_{1}=\\{1,3,5\\}$, $C_{2}=\\{4,5\\}$, and $C_{3}=\\{2,4\\}$. The _candidate
clique set_ for vertex 3, $S_{3}=\\{1,2,3\\}$, since vertex 3 is contained in
$C_{1}$, and the vertices of both $C_{2}$ and $C_{3}$ are contained among the
neighbors of vertex 3. Vertex 6 is not contained in any clique of $C$, but
$C_{2}$ is contained among the neighbors of vertex 6, and $S_{6}=\\{2\\}$.

We can characterize the set of cliques that can cover an uncovered edge,
precisely through _candidate clique sets_ as follows.

###### Lemma 3.7

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a clique cover of a subset of
edges of $G=(V,E)$, and let $S_{x}$ be the _candidate clique set_ of a vertex
$x$ in $V$. Let $\\{x,y\\}\in E$ be an uncovered edge of $G$. For $l\in[1,k]$,
$l\in S_{x}\cap S_{y}$ if and only if $\\{x,y\\}$ can be covered by a clique
contained in $\mathcal{C}$.

  * Proof.

Only if: Since the edge $\\{x,y\\}$ is not covered by the cliques in
$\mathcal{C}$, both $x$ and $y$ are not contained in any of the cliques of
$\mathcal{C}$. Then by the definition of _candidate clique set_ , one of the
following holds for $C_{l}$: (i) $x\in C_{l}$, $y\not\in C_{l}$,
$C_{l}\subseteq N(y)$. (ii) $y\in C_{l}$, $x\not\in C_{l}$, $C_{l}\subseteq
N(x)$. (iii) $x\not\in C_{l}$, $y\not\in C_{l}$, $C_{l}\subseteq N(x)$,
$C_{l}\subseteq N(y)$.

No matter which of the three cases holds, both vertices $x$ and $y$ can be
included in $C_{l}$, and thus $\\{x,y\\}$ can be covered by $C_{l}$.

If: Since the edge $\\{x,y\\}$ can be covered by a clique contained in
$\mathcal{C}$, $\exists C_{l}\in\mathcal{C}$ in which $x$ or $y$ or both are
not contained, but can be added to. Since $\\{x,y\\}$ is an uncovered edge, if
$x$ is contained in $C_{l}$ then it must be the case $y\not\in C_{l}$ and
$C_{l}\subseteq N(y)$. It follows that if $x$ is contained in $C_{l}$ then
$l\in S_{x}$ and $l\in S_{y}$. Similarly, $l\in S_{x}$ and $l\in S_{y}$ for
the cases when $y\in C_{l}$ or both $x$ and $y$ are not contained in $C_{l}$.
Therefore, $l\in S_{x}\cap S_{y}$.

###### Remark 3.5

For an uncovered edge $\\{x,y\\}$, consider the choices of covering the edge
with a clique $C_{l}$ contained in $\mathcal{C}$ (clique cover at hand) as
follows.
(i) $x\in C_{l}$, $y\not\in C_{l}$, $C_{l}\subseteq N(y)$.
(ii) $y\in C_{l}$, $x\not\in C_{l}$, $C_{l}\subseteq N(x)$.
(iii) $x\not\in C_{l}$, $y\not\in C_{l}$, $C_{l}\subseteq N(x)$,
$C_{l}\subseteq N(y)$.
Assume, we choose to utilize only choice (i) to cover $\\{x,y\\}$. Then, we
are essentially restricted to order the vertices in $V$ in some order such
that vertex $x$ is placed before vertex $y$ in the order. Conversely, ordering
of vertices (or edges) may restrict our choices to cover $\\{x,y\\}$.
_Candidate clique_ concept abstracts away any restriction of choices that may
be imposed by any ordering of vertices (or edges), and presents us with all
potential choices at hand.

We obtain following result that helps us to bound several time and space
related quantities.

###### Lemma 3.8

Let $\mathcal{C}=\\{\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{k}\\}$ be
a clique cover of a subset of edges of $G=(V,E)$. If $\mathcal{C}$ is _locally
minimal_ , then $\sum_{x\in V}|S_{x}|=O(m+|\mathcal{C}|\Delta)$.

  * Proof.

Using the two conditions that a _candidate clique_ of a vertex could satisfy
(Definition 3.5), we can express the sum as follows.

(3.1) $\sum_{x\in V}|S_{x}|=\sum_{x\in V}|\\{l|x\in C_{l}\\}|+\sum_{x\in
V}|\\{l|x\not\in C_{l},C_{l}\subseteq N(x)\\}|$

We can bound the first sum on the right side using Lemma 3.5 to obtain

$\sum_{x\in V}|\\{l|x\in C_{l}\\}|=\sum_{C_{l}\in\mathcal{C}}|C_{l}|=O(m)$

We obtain a bound for the second term in the right-hand-side of Equation 3.1
as follows.

Since $\mathcal{C}$ is _locally minimal_ , we must have created every new
clique $C_{k+1}$ using rule (ii) of Definition 3.3. Immediately after covering
edge $\\{x,y\\}$, it must be the case that $k+1\in S_{z},\forall z\in(N(x)\cap
N(y))\cup\\{x,y\\}$.

On the other hand, whenever applicable we used rule (i) of Definition 3.3 to
expand the clique cover by an uncovered edge $\\{x,y\\}$. From Lemma 3.7, this
corresponds to having $l\in S_{x}\cap S_{y}$. But $C_{l}$ is an existing
clique, and all _candidate clique sets_ that include $l$ have already been
accounted for when we created $C_{l}$ using rule (ii) of Definition 3.3.

Therefore, any vertex $z$ such that $z\not\in C_{l}$, but $C_{l}\subseteq
N(z)$, must be a common neighbor of $x$ and $y$, such that the edge
$\\{x,y\\}$ required the creation of $C_{l}$ using rule (ii) of Definition
3.3. And $|\\{z|z\not\in C_{l},C_{l}\subseteq N(z)\\}|\leq|N(x)\cap
N(y)|=O(\Delta)$.

Summing over all cliques we get

$\sum_{C_{l}\in\mathcal{C}}|\\{x|x\not\in C_{l},C_{l}\subseteq
N(x)\\}|=O(|\mathcal{C}|\Delta)$

The sum on the left hand side of preceding equality is another way to express
the sum for which we needed a bound. To see this consider a bipartite graph
with vertices in $V$ on one side, and the cliques in $\mathcal{C}$ on the
other sides. In this bipartite graph, an edge connects a vertex to a clique if
condition (ii) of Definition 3.5 holds for the clique. Sum of degrees from one
side of this bipartite graph is equal to the sum of the degrees from the other
side. Hence we have the following equality.

$\sum_{x\in V}|\\{l|x\not\in C_{l},C_{l}\subseteq N(x)\\}|$
$=\sum_{C_{l}\in\mathcal{C}}|\\{x|x\not\in C_{l},C_{l}\subseteq N(x)\\}|$

It follows that

$\sum_{x\in V}|\\{l|x\not\in C_{l},C_{l}\subseteq
N(x)\\}|=O(|\mathcal{C}|\Delta)$

###### Property 3.1

Consider a graph $G$ whose connected components are triangle-free. Every edge
of $G$ has to be covered with a distinct clique. Therefore, every clique would
contribute to $S_{x}$ values of exactly 2 vertices, the end vertices of the
edge contained in the clique. And, $\sum_{x\in V}S_{x}=\sum_{x\in
V}|N(x)|=2m=\Theta(m)$. A similar bound is true for dense graphs, e.g., for a
complete graph $m=n^{2}$, and $\sum_{x\in V}|S_{x}|=n=O(m)$.

Using connection to _intersection graph basis_ , we obtain following
connection between _minimum clique cover_ and _candidate clique sets_.

###### Lemma 3.9

Let $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$ be a clique cover of $G=(V,E)$,
and let $S_{x}$ be the _candidate clique set_ of a vertex $x$ in $V$. If
$|\cup_{x\in V}S_{x}|$ is minimum over the family of _candidate clique sets_
resulting from the clique covers of $G$, then $\mathcal{C}$ is a _minimum
clique cover_ of $G$.

  * Proof.

Let $F_{x}=S_{x}\backslash\\{l|x\not\in C_{l}\\}$, $Y=\cup_{x\in V}F_{x}$, and
$Z=\cup_{x\in V}S_{x}$.

Note that $F_{x}=\\{l|x\in C_{l}\\}$, and by our assumption $|Z|$ is minimum.
Therefore, each of the clique indices in $Z$ is contained in $Y$, i.e.,
$|Y|=|Z|$.

$Y$ is an intersection graph basis of $G$, and $\\{F_{1},F_{2},...,F_{n}\\}$
is the family of subsets of $Y$ where $F_{i}$ corresponds to vertex $i\in V$.
To see this assume $|Y|$ is not minimum, i.e., $\exists l\in Y$, such that
$C_{l}$ can be removed from $\mathcal{C}$. Which contradicts our assumption
that $|Z|$ is minimum.

Since $Y$ is an intersection graph basis of $G$, $\mathcal{C}$ is a _minimum
clique cover_ of $G$ [[24], [64]].

##  4 Greedy Framework

We describe a greedy framework that computes _locally minimal clique cover_.
We show that _locally minimal clique cover_ computed by our greedy framework
can be efficiently turned into _minimal clique cover_. We start with a basic
greedy framework, and subsequently modify the basic framework to derive an
improved greedy framework with better time bound. We conclude the section
showing modifications of the improved greedy framework that make the time
bound attuned to degeneracy of graph.

###  4.1 Basic Greedy Framework.

Algorithm 1 Basic Greedy Framework

Input: A graph $G=(V,E)$
Output: A _locally minimal clique cover_ $\mathcal{C}$ of $G$

1: Select an ordering of edges in $E$, and process edges in that order in
steps 3-13

2: $k\leftarrow 0$

3: while $\\{x,y\\}\in E$ uncovered do

4: $S_{x}\leftarrow\\{l|C_{l}$ is _candidate clique_ of $x$, $1\leq l\leq
k\\}$

5: $S_{y}\leftarrow\\{l|C_{l}$ is _candidate clique_ of $y$, $1\leq l\leq
k\\}$

6: if $S_{x}\cap S_{y}\neq\phi$ then

7: Select $l\in S_{x}\cap S_{y}$

8: $C_{l}\leftarrow C_{l}\cup\\{x,y\\}$

9: else

10: $k\leftarrow k+1$

11: $C_{k}\leftarrow\\{x,y\\}$

12: end if

13: end while

14: return $\mathcal{C}$

Our basic greedy framework is described in Algorithm 1. Algorithm 1 strictly
follows the two rules defined for _locally minimal clique cover_. To apply
rule (i) of Definition 3.3, it uses characterization described in Lemma 3.7.
At every iteration, it computes set of _candidate cliques_ for two end
vertices of an uncovered edge $\\{x,y\\}$ (step 4 and 5). If there is an index
of a clique $C_{l}$ contained in the _candidate clique sets_ of $x$ and $y$,
it covers the edge using $C_{l}$ (step 7 and 8). Otherwise, it creates a new
clique containing only $\\{x,y\\}$ (step 10 and 11). After the execution of
steps 1 - 13, we have following result.

###### Lemma 4.1

For a graph $G=(V,E)$, Algorithm 1 computes a _locally minimal clique cove_ r
$\mathcal{C}$ of $G$.

  * Proof.

After every iteration of steps 4-12, Algorithm 1 maintains the invariant that
the _clique cover_ computed for the subset of edges covered after the
iteration is _locally minimal_. This is straightforward to see as steps 8 and
11 are the only steps where we modified the _clique cover_.

The invariant holds for either of the steps: step 8 directly follows from rule
(i) of Definition 3.3, and Lemma 3.7, and, step 11 is a straightforward use of
rule (ii) of Definition 3.3. Therefore, after the execution of steps 1-13 we
have a _locally minimal clique cover_.

For the data structures, we assume that the graph is represented by its
adjacency lists, and that each list is stored in a hash table. With universal
hashing or simple uniform hashing, an element can be accessed, or inserted, or
deleted in $O(1)$ average time per operation. We can also convert every list
to an ordered list taking $O(m\log\Delta)$ time in total, and then insertion,
or deletion, or access of any element would take $O(\log\Delta)$ time. For the
_candidate clique sets_ , we assume similar data structure as adjacency lists,
where each list maintains _candidate clique set_ of a vertex.

For step 7 in Algorithm 1, one can do substantial computation per selection
without affecting our obtained time bounds; but, for all our analysis, we
stick to simple choices such as selecting a smallest clique, or a largest
clique, or clique created earliest, or a random clique. For the next analysis
we assume an edge ordering as follows. Sort the vertices from lowest to
highest degree and then select vertices in that order. For each selected
vertex, cover all the edges incident on the vertex. With the choices of edge
ordering and clique selection, we obtain following result.

###### Lemma 4.2

For a graph $G=(V,E)$, Algorithm 1 computes a _locally minimal clique cover_
$\mathcal{C}$ of $G$, taking $O(m^{2})$ time and $O(m)$ space.

  * Proof.

Lemma 4.1 shows the proof of _locally minimal clique cover_. Now, we show the
analysis for time and space bounds.

For step 1, our choice of edge ordering takes $O(n\log n)$ time. Isolated
vertices would not affect execution of Algorithm 1. Therefore, for rest of the
steps we can assume $n=O(m)$, and time bound for this step would be dominated
by the time bounds of the other steps shown next.

For steps 4 and 5, for each clique $C_{l}$ we need to check whether $C_{l}$ is
contained in the neighborhood of $x$ and $y$, or whether $x$ and $y$ are
contained in $C_{l}$. For each such $C_{l}$, it takes
$O(min\\{|C_{l}|,|N(x)|,|N(y)|\\})$ time. Combining the fact that
$\sum_{l=1}^{k}|C_{l}|=O(m)$ from Lemma 3.5, we get time bounds of steps 4 and
5 for the entire execution of the algorithm as follows. $O(\sum_{\\{x,y\\}\in
E}\sum_{l=1}^{k}min\\{|C_{l}|,|N(x)|,|N(y)|\\})=O(\sum_{\\{x,y\\}\in
E}\sum_{l=1}^{k}|C_{l}|)=O(\sum_{\\{x,y\\}\in E}m)=O(m^{2})$.

For our choices of clique selection, step 7 takes $O(m)$ time, since,
$|\mathcal{C}|=O(m)$ and $|S_{x}|=|S_{y}|=O(m)$. And, step 8 takes $O(\Delta)$
time: to make sure that any uncovered edge among $x$, $y$ and vertices of
$C_{l}$ is being identified as covered. Steps 10 and 11 take $O(1)$ time.

It is straightforward to see that the algorithm utilizes at most two sets of
_candidate clique_ sets at steps 4 and 5, and each of them takes $O(m)$ space.

Combining preceding bounds, we conclude that Algorithm 1 does $O(m^{2})$
computations, using $O(m)$ space.

####  4.1.1 Computing _Minimal Clique Cover_.

In light of the characterization in Lemma 3.4, we need efficient ways for
finding cliques that may be redundant in a _locally minimal clique cover_. We
can obtain a _minimal clique cover_ from an arbitrary clique cover in
different ways. For example, we can compute all removable assignments
(vertices or edges that can be removed) in a clique cover similar to [20], and
remove assignments repeatedly until no such assignments are removable. Here,
we are going to exploit the characterization we obtained for _locally minimal
clique cover_ in Lemma 3.6. We describe fast realization of a post-processing
step proposed by [45] to get _minimal clique cover_ , and analyze the step for
_locally minimal clique cover_.

Algorithm 2 Post-Process

Input: A graph $G=(V,E)$, and a _clique cover_ $\mathcal{C}$ of $G$
Output: A _minimal clique cover_ $\mathcal{C}^{{}^{\prime}}$ of $G$

1: $\forall\\{x,y\\}\in E$ compute $AppCount(\\{x,y\\})$ denoting number of
times $\\{x,y\\}$ appears in $\mathcal{C}$

2: $\mathcal{C}^{{}^{\prime}}\leftarrow\phi$

3: for each $C_{l}\in\mathcal{C}$ do

4: if $AppCount(\\{x,y\\})>1$, $\forall\\{x,y\\}\in C_{l},x\neq y$ then

5: $AppCount(\\{x,y\\})\leftarrow AppCount(\\{x,y\\})-1$, $\forall\\{x,y\\}\in
C_{l},x\neq y$

6: else

7:
$\mathcal{C}^{{}^{\prime}}\leftarrow\mathcal{C}^{{}^{\prime}}\cup\\{C_{l}\\}$

8: end if

9: end for

10: return $\mathcal{C}^{{}^{\prime}}$

Algorithm 2 shows our realization of post-processing step proposed by [45]. At
step 1, it enumerates all edges contained in the cliques of $\mathcal{C}$, and
for every edge of graph, starts keeping track of number of appearances of the
edge in $\mathcal{C}$. If for a clique $C_{l}$, all of its edges appear more
than once in $\mathcal{C}$ (step 4), then we discard $C_{l}$ and decrease
appearance counts for all the edges contained in $C_{l}$ (step 5). Otherwise,
we add $C_{l}$ to the _minimal clique cover_ (step 7). Following is
straightforward to show.

###### Lemma 4.3

A _minimal clique cover_ with all the characterizations of _locally minimal
clique cover_ can be obtained from a _locally minimal clique cover_ in
$O(m\Delta)$ time, using $O(m)$ space.

  * Proof.

_Minimal Clique Cover_. When step 4 is true, $\mathcal{C}_{l}$ can be
discarded, and we do not include $C_{l}$ in minimal clique cover
$\mathcal{C}^{{}^{\prime}}$. In step 5, accounting for the fact that $C_{l}$
is discarded, we affect that by decreasing count of $C_{l}$ for the edges
contained in $C_{l}$. On the other hand, if for any $C_{l}$, step 4 is false,
then we know $C_{l}$ contains at least one edge that is not covered by
remaining cliques in $C$, and $C_{l}$ must be included in the _minimal clique
cover_. We make sure this in step 7.

Time and Space. From Lemma 3.6, we know total number of appearances of edges
in a locally minimal clique cover is $O(m\Delta)$. Since we only enumerate
every edge contained in $\mathcal{C}$ once in step 1, once in step 4, and at
most once in step 5, entire post-processing step takes $O(m\Delta)$ time. We
only use $O(m)$ counters initialized at step 1, therefore, space bound is
$O(m)$.

###  4.2 Improved Greedy Framework.

Our basic greedy framework sets the stage for computing _locally minimal
clique cover_ , thereby _minimal clique cover_ , in simplest possible terms.
Now, we describe modifications of the basic framework that saves us from
repeated computations of _candidate clique sets_ in step 4 and 5 of Algorithm
1. To this end, we outline two parts incremental computations for _candidate
clique sets_ as follows.

  1. 1.

Whenever a new clique $C_{k}=\\{x,y\\}$ is created, we add $k$ to the
_candidate clique sets_ of common neighbors of $x$ and $y$; and also to the
_candidate clique sets_ of $x$ and $y$.

  2. 2.

Whenever an existing clique $C_{l}$ is extended by an uncovered edge
$\\{x,y\\}$, we remove $l$ from the _candidate clique set_ of a vertex $z$,
such that both vertices $x$ and $y$ are not in $N(z)$. And we do this for all
such vertices, except for the cases $z=x$ or $z=y$.

For the first of part of computation since we just have created
$C_{k}=\\{x,y\\}$, for every common neighbor of $x$ and $y$, say $z$,
$C_{k}=\\{x,y\\}$ is contained in $N(z)$. Therefore, $k$ must be added to
$S_{z}$.

For the second of part of computation since we just have included $\\{x,y\\}$
to $C_{l}$, every $z\in V$ such that $l$ is contained in $S_{z}$, must contain
both $x$ and $y$ in $N(z)$. Otherwise, we must remove $l$ from $S_{z}$, and
restore validity of all _candidate clique sets_.

For the second part, to find $z$ so that we can remove $l$ from $S_{z}$, we
select a vertex from $C_{l}$, say $w$, arbitrarily. Because, every such $z$ is
a common neighbor of vertices contained in $C_{l}$, processing only the
neighbors of $w$, $N(w)$, would suffice.

$z_{1}$$z_{2}$$x$$y$$u_{2}$$u_{1}$$\mathcal{C}_{k}$ Figure 2: Except $u_{1}$
and $u_{2}$, all other vertices would have $C_{k}$ as _candidate clique_ after
the creation of $C_{k}$
$z_{1}$$z_{2}$$w_{1}$$w_{2}$$w_{3}$$y$$x$$\mathcal{C}_{l}$ Figure 3: While
including $x$ and $y$ to $C_{l}$, we would remove $l$ from _candidate clique
set_ of $z_{2}$, $S(z_{2})$, since $x$ is not in $N(z_{2})$. Thick edge
between a vertex and the clique $C_{l}$ denotes the vertices in the clique are
contained in the neighborhood of the vertex. Algorithm 3 Improved Greedy
Framework

Input: A graph $G=(V,E)$
Output: A _minimal clique cover_ $\mathcal{C}$ of $G$

1: Select an ordering of edges in $E$, and process edges in that order in
steps 3-13

2: $k\leftarrow 0$

3: while $\\{x,y\\}\in E$ uncovered do

4: if $S_{x}\cap S_{y}\neq\phi$ then

5: Select $l\in S_{x}\cap S_{y}$

6: Select a vertex $w\in C_{l}$ arbitrarily. $\forall z\in
N(w)\backslash\\{x,y\\}$, remove $l$ from $S_{z}$, if both $x$ and $y$ are not
in $N(z)$

7: $C_{l}\leftarrow C_{l}\cup\\{x,y\\}$

8: else

9: $k\leftarrow k+1$

10: $C_{k}\leftarrow\\{x,y\\}$

11: Add $k$ to $S_{z}$, $\forall z\in(N(x)\cap N(y))\cup\\{x,y\\}$

12: end if

13: end while

14: $\mathcal{C}\leftarrow$ Post-Process($G$, $\\{C_{1},C_{2},...,C_{k}\\}$)

15: return $\mathcal{C}$

Figure 2 shows a schematic for the first part of the computation, and Figure 3
shows a schematic for the second part of the computation. Incorporating these
two parts incremental computations of _candidate clique sets_ , we can discard
computation of _candidate clique sets_ in steps 4 and 5 of Algorithm 1.
Modified algorithm is outlined in Algorithm 3 with two parts incremental
computations added in steps 6 and 11. These modifications of Algorithm 1 would
compute same _clique cover_ as Algorithm 1. Therefore, following is
straightforward to show.

###### Lemma 4.4

For a graph $G=(V,E)$, Algorithm 3 computes a _minimal clique cover_
$\mathcal{C}$ of $G$.

  * Proof.

All we need to verify that steps 6 and 11 agree with what would have been
computed in step 4 and 5 of Algorithm 1.

Step 11 follows from Definition 3.5, we added index of $C_{k}$ to exactly the
same sets of _candidate clique sets_ that would have been computed in step 4
and 5 of Algorithm 1.

For step 6, since we are including $\\{x,y\\}$ to $C_{l}$. After this
inclusion, according to the definition of _candidate clique_ , for any $z\in
V$ with $\\{z,x\\}\not\in E$ or $\\{z,y\\}\not\in E$, $C_{l}$ would not have
been computed as _candidate clique_ in step 4 and 5 of Algorithm 1. And, we
make sure to remove $l$ from exactly those $S_{z}$ at step 6 of Algorithm 3.

With the bound established in Lemma 3.8, we obtain following characterizations
of Algorithm 3.

###### Theorem 4.1

For a graph $G=(V,E)$, Algorithm 3 computes a _minimal clique cover_
$\mathcal{C}$ of $G$, taking $O(m\Delta+|\mathcal{C}|\Delta^{2})$ time and
$O(m+|\mathcal{C}|\Delta)$ space; and for $\sum_{x\in V}|S_{x}|=O(m)$, it
takes $O(m\Delta)$ time and $O(m)$ space.

  * Proof.

Lemma 4.4 shows the proof of _minimal clique cover_. Now, we show the analysis
for $\sum_{x\in V}|S_{x}|=O(m)$; the general case follows from replacing the
sum with the bound obtained in Lemma 3.8.

In every iteration, step 4 would take $O(min\\{|S_{x}|,|S_{y}|\\})$ time. All
iterations of step 4 would take $O(\sum_{\\{x,y\\}\in
E}min\\{|S_{x}|,|S_{y}|\\})=O(\sum_{\\{x,y\\}\in E}|S_{x}|)$ time. But, any
$x\in V$ would contribute at most $|N(x)|$ time in $\sum_{\\{x,y\\}\in
E}|S_{x}|$, and using the bound $\sum_{x\in V}|S_{x}|=O(m)$, we get following
time bound for all iterations of step 4. $O(\sum_{\\{x,y\\}\in
E}|S_{x}|)=O(\sum_{x\in V}|S_{x}||N(x)|)=O(\Delta\sum_{x\in
V}|S_{x}|)=O(m\Delta)$.

Analysis of step 4 also applies to step 5. And, for our choices of clique
selection, step 5 would also take $O(m\Delta)$ time for all iterations.

Step 6 would take $O(1)$ time to select $w$, and $O(\Delta)$ time to remove
index of $\mathcal{C}_{l}$ from all $S_{z}$ of relevant $z\in N(w)$. Step 7
would also take $O(\Delta)$ time. As shown in Lemma 4.3, step 14 would take
$O(m\Delta)$ time, and $O(m)$ space.

For _candidate clique sets_ , we only have used $\sum_{x\in V}|S_{x}|=O(m)$
space. Combining preceding bounds, we conclude that for $\sum_{x\in
V}|S_{x}|=O(m)$, Algorithm 3 does $O(m\Delta)$ computations, using $O(m)$
space.

###  4.3 Degeneracy Ordering.

We describe modifications of our improved greedy framework that takes
degeneracy of input graph into account. For edge ordering in step 1 of
Algorithm 3, we make use of _degeneracy ordering_ , and for graphs of constant
degeneracy, show a family of linear time algorithms. To integrate degeneracy
in the time bound, we modify the steps outlined in Algorithm 3 as follows.

  1. 1.

In step 1, compute $u_{1},u_{2},...,u_{n}$ (degeneracy ordering of $V$) and
$N_{d}(u_{i}),\forall i\in[1,n]$. Cover edges incident from $u_{1}$ to
vertices in $N_{d}(u_{1})$ first, then cover edges incident from $u_{2}$ to
vertices in $N_{d}(u_{2})$, and so on.

  2. 2.

In step 6, scan $C_{l}$, and select a vertex $w$ such that $w$ comes earliest
in the degeneracy ordering among the vertices contained in $C_{l}$. Then
instead of $N(w)$ use $N_{d}(w)$.

  3. 3.

In step 11, if $x$ precedes $y$ in the degeneracy ordering of $V$, then use
$N_{d}(x)\cap N(y)$ instead of $N(x)\cap N(y)$. Otherwise, use $N_{d}(y)\cap
N(x)$ instead of $N(x)\cap N(y)$.

  4. 4.

Discard step 14.

Note that since every non-empty subgraph must have at least one vertex with
degree at most $d$, it must be the case $|C_{l}|\leq d+1,\forall
C_{l}\in\mathcal{C}$. With the above-stated modifications, the correctness of
steps 1-13 of Algorithm 3 is retained, and we obtain following result.

###### Lemma 4.5

For a graph $G=(V,E)$, Algorithm 3 with the above-stated modifications
computes a _locally minimal clique cover_ $\mathcal{C}$ of $G$.

  * Proof.

Modification of step 1 does not effect validity of _clique cover_. Let for an
uncovered edge $\\{x,y\\}$, $x$ precedes $y$ in the degeneracy order of $V$.
With the edge ordering outlined in step 1 of the above-stated modifications,
we only need to propagate _candidate clique sets_ information to vertices that
follow $x$ in the degeneracy ordering of $V$. In step 11, we make sure this by
updating _candidate clique sets_ of vertices contained in $N_{d}(x)\cap N(y)$.

In step 6, we make sure we update $S_{z}$ of all $z$ that are yet to be
processed by selecting a vertex $w$ contained in $C_{l}$ such that among the
vertices of $C_{l}$, $w$ comes earliest in the degeneracy ordering of $V$.
Note that this is exactly the vertex $x$ that we added in step 11 when we
created the clique with index $l$. Therefore, $N_{d}(w)$ of step 6 is the same
list as of $N_{d}(x)$ of step 11 when we added $C_{l}=\\{x,y\\}$ to the
_clique cover_. And, through $N_{d}(w)$ we get hold of all $z\in V$, whose
$S_{z}$ may contain $C_{l}$ as _candidate clique_.

Taking the above-stated modifications into account, we get a tighter bound
than the bound of 3.8 as follows.

###### Lemma 4.6

Let $\mathcal{C}=\\{\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{k}\\}$ be
a _clique cover_ of a subset of edges of $G=(V,E)$. If $\mathcal{C}$ is
_locally minimal_ and computed following the above-stated modifications of
Algorithm 3, then $\sum_{x\in V}|S_{x}|=O(m+|\mathcal{C}|d)$.

  * Proof.

Step 1 and 2 of the above-stated modifications do not include any new clique
index to any set of $\mathcal{S}$. Only step 3 of the above-stated
modifications adds clique index to sets of $\mathcal{S}$ and we account for
the effects as follows.

For every new clique $C_{l}$ we created using rule (ii) of Definition 3.3,
there are choices of _candidate clique sets_ to which we include clique index
$l$. With step 3 of the above-stated modifications, we deviate from the
choices of _candidate clique sets_ in the proof of Lemma 3.8. Assume $x$
precedes $y$ in the degeneracy order of $V$. Then with the deviation
introduced with step 3 of the above-stated modifications, we include $l$ to
the _candidate clique sets_ of vertices $z$, $S_{z}$, such that
$z\in(N_{d}(x)\cap N(y))\cup\\{x,y\\}$. Therefore, any vertex $z$ such that
$z\not\in C_{l}$ it must be the case $|\\{z|z\not\in C_{l},C_{l}\subseteq
N(z)\\}|\leq|N_{d}(x)\cap N(y)|=O(d)$. And we get following change from the
proof of Lemma 3.8.

$\sum_{x\in V}|\\{l|x\not\in C_{l},C_{l}\subseteq N(x)\\}|=O(|\mathcal{C}|d)$

We obtain following characterizations of Algorithm 3 through Lemma 4.6.

###### Theorem 4.2

For a graph $G=(V,E)$, Algorithm 3 with the above-stated modifications
computes a _locally minimal clique cover_ $\mathcal{C}$ of $G$, taking
$O(n+md+|\mathcal{C}|d^{2})$ time and $O(m+|\mathcal{C}|d)$ space, and for
$\sum_{x\in V}|S_{x}|=O(m)$, it takes $O(n+md)$ time and $O(m)$ space.

  * Proof.

Lemma 4.5 shows the proof of _locally minimal clique cover_. Now, we show the
analysis for $\sum_{x\in V}|S_{x}|=O(m)$; the general case follows from
replacing the sum with the bound obtained in Lemma 4.6.

Computing degeneracy ordering takes $O(m+n)$ time. Computing
$N_{d}(u_{i}),\forall i\in[1,n]$ also takes $O(m+n)$ time.

Step 4 would take $O(\sum_{\\{x,y\\}\in E}min\\{|S_{x}|,|S_{y}|\\})$
$=O(\sum_{\\{x,y\\}\in E}|S_{x}|)$ time. Under degeneracy ordering any $x\in
V$ would contribute at most $d$ times in $\sum_{\\{x,y\\}\in E}|S_{x}|$.

Therefore, step 4 in total would take $O(\sum_{\\{x,y\\}\in
E}|S_{x}|)=O(\sum_{x\in V}|S_{x}|d)$

$=O(d\sum_{x\in V}|S_{x}|)=O(md)$ time. Same $O(md)$ time bound applies to
step 5, for our choices of clique selection.

Step 6 and 7 would take $O(d)$ time as $|C_{l}|\leq d+1$, and we are only
traversing $N_{d}(w)$. Step 11 takes $O(|N_{d}(x)\cap N(y)|)=O(d)$ time.

Combining preceding bounds, we conclude that for $\sum_{x\in V}|S_{x}|=O(m)$,
our modifications of Algorithm 3 under degeneracy ordering does $O(n+md)$
computations, using $O(m)$ space.

##  5 FPT Algorithms

We present two FPT algorithms for _ECC-d_. Our FPT algorithms are based on two
different design paradigms: one algorithm is based on _candidate clique sets_
(Section 5.1), and the other algorithm is based on maximal clique enumeration
(Section 5.2). To further corroborate versatility of _candidate clique sets_
for computing _clique cover_ with different objectives, we briefly describe an
exact algorithm for the _assignment-minimum clique cover_ problem (Section
5.1.1).

###  5.1 FPT Algorithm Based on _Candidate Clique Sets_.

Our basis for computing a _minimum clique cover_ of a graph using _candidate
clique sets_ is laid out in Lemma 3.9. Here we make sure that the computation
takes degeneracy of graph into account. Algorithm 4 solves the parameterized
decision problem _ECC-d_ : if there is a clique cover of $G$ with no more than
$k$ cliques, then Algorithm 4 returns it; otherwise, it returns $\phi$. By
iteratively increasing value of $k$, starting from $1$, and calling Algorithm
4 with each value of $k$, we can compute a _minimum clique cover_.

In step 4 of Algorithm 4, we select an uncovered edge that helps us to bound
number of branching required at each node of the search tree. For an uncovered
edge selected in step 4, we consider each of the _candidate cliques_ that can
cover the edge (steps 5-13), and branch into each of such choices (step 8).
_Prepare_ subroutine (step 6) prepares _candidate clique sets_ for inclusion
of $\\{x,y\\}$ in $C_{l}$, and saves containment status of $x$ and $y$ in
$C_{l}$. If a branch fails at step 8, _Restore_ subroutine (step 12) undoes
the changes made in steps 6-7. If none of the branches in steps 5-13 succeeds,
and parameter $k$ permits, then we try one final branch at steps 14-21. In
this branch, we extend the _clique cover_ with a new clique containing only
$\\{x,y\\}$ (step 15). If the final branch fails, we restore the _clique
cover_ (step 20), and return to parent of this node (step 22).

Algorithm 4 CandidateCliqueFPT

Input: A graph $G=(V,E)$, _Clique cover_ $\mathcal{C}$ (of a subset of edges
in $E$), _Candidate clique sets_ $\mathcal{S}$, an integer $k$
Output: If exists, a _clique cover_ $\mathcal{C}$ of $G$ with
$|\mathcal{C}|\leq k$; otherwise $\phi$

1: if $\mathcal{C}$ covers $G$ then

2: return $\mathcal{C}$

3: end if

4: Select an uncovered edge $\\{x,y\\}$ such that $y\in N_{d}(x)$, and in the
degeneracy order of $V$, $x$ follows any other vertex with such a neighbour
$y$

5: for each $l\in S_{x}\cap S_{y}$ do

6: $Prepare(G,\mathcal{C},\mathcal{S},l,\\{x,y\\},W,x_{l},y_{l})$

7: $C_{l}\leftarrow C_{l}\cup\\{x,y\\}$

8: $Q\leftarrow CandidateCliqueFPT(G,\mathcal{C},\mathcal{S},k)$

9: if $Q\neq\phi$ then

10: return $Q$

11: end if

12: $Restore(G,\mathcal{C},\mathcal{S},l,\\{x,y\\},W,x_{l},y_{l})$

13: end for

14: if $k>0$ then

15: $AddNewClique(G,\mathcal{C},\mathcal{S},\\{x,y\\})$

16: $Q\leftarrow CandidateCliqueFPT(G,\mathcal{C},\mathcal{S},k-1)$

17: if $Q\neq\phi$ then

18: return $Q$

19: end if

20: $RemoveNewClique(G,\mathcal{C},\mathcal{S})$

21: end if

22: return $\phi$

Algorithm 5 AddNewClique

Input: A graph $G=(V,E)$, _Clique cover_ $\mathcal{C}$ (of a subset of edges
in $E$), _Candidate clique sets_ $\mathcal{S}$, an edge $\\{x,y\\}$
Output: A new clique added to $\mathcal{C}$, and updated _candidate clique
sets_

1: $p\leftarrow|\mathcal{C}|+1$

2: $C_{p}\leftarrow\\{x,y\\}$

3: $R_{p}\leftarrow(N(x)\cap N(y))\cup\\{x,y\\}$

4: for each $z\in R_{p}$ do

5: $S_{z}\leftarrow S_{z}\cup\\{p\\}$

6: end for

7: return $\mathcal{C},\mathcal{S}$

We could have made copies of $\mathcal{C}$ and $\mathcal{S}$ in steps 6 and 15
and could have branched modifying the copies. The algorithm would still be
FPT, but we would incur $O(m+k\Delta)$ space and time cost per node in the
search tree. Instead, we outline computations in the subroutines, which help
us to keep space use down to $O(m+k\Delta)$ in total, and to bound time spent
per node to $O(\Delta)$. Next, we expand on the subroutines.

For each clique $C_{l}$, we use a data structure $R_{l}$, which keeps track of
vertices that have $C_{l}$ as _candidate cliques_ , i.e., $R_{l}=\\{z\in
V|l\in S_{z}\\}$. _AddNewClique_ subroutine (Algorithm 5) initializes this
data structure, for every new clique it adds to the _clique cover_. Also, at
each node, _Prepare_ and _Restore_ subroutines share some data structure,
namely $W$, $x_{l}$ (indicator of whether $C_{l}$ contains $x$), $y_{l}$
(indicator of whether $C_{l}$ contains $y$), to facilitate the modification of
$\mathcal{C}$ and $\mathcal{S}$ and their restoration.

Algorithm 6 Prepare

Input: A graph $G=(V,E)$, _Clique cover_ $\mathcal{C}$ (of a subset of edges
in $E$), _Candidate clique sets_ $\mathcal{S}$, clique index $l$, an edge
$\\{x,y\\}$, $W$, $x_{l}$, $y_{l}$
Output: _Candidate clique sets_ prepared for covering $\\{x,y\\}$ with
$C_{l}$, $W$, $x_{l}$, $y_{l}$

1: $W\leftarrow\phi$

2: for each $z\in R_{l}\backslash\\{x,y\\}$ do

3: if $\\{x,z\\}\not\in E$ or $\\{y,z\\}\not\in E$ then

4: $W\leftarrow W\cup\\{z\\}$

5: $S_{z}\leftarrow S_{z}\backslash\\{l\\}$

6: end if

7: end for

8: $R_{l}\leftarrow R_{l}\backslash W$

9: Compute and set values of indicator variables $x_{l}$ and $y_{l}$ denoting
whether $x\in C_{l}$ and $y\in C_{l}$ respectively

10: return $\mathcal{S},W,x_{l},y_{l}$

Algorithm 7 Restore

Input: A graph $G=(V,E)$, _Clique cover_ $\mathcal{C}$ (of a subset of edges
in $E$), _Candidate clique sets_ $\mathcal{S}$, $l$, an edge $\\{x,y\\}$, $W$,
$x_{l}$, $y_{l}$
Output: $C_{l}$ and corresponding _candidate clique sets_ restored

1: for each $z\in W$ do

2: $R_{l}\leftarrow R_{l}\cup\\{z\\}$

3: $S_{z}\leftarrow S_{z}\cup\\{l\\}$

4: end for

5: Using indicator variables $x_{l}$ and $y_{l}$, restore containment of $x$
and $y$ in $C_{l}$

6: return $\mathcal{C},\mathcal{S}$

As outlined in Algorithm 6, _Prepare_ subroutine removes $l$ from the
candidate clique sets of vertices in $R_{l}$ that cannot have $C_{l}$ as
_candidate clique_ after inclusion of $\\{x,y\\}$ to $C_{l}$, and moves these
vertices from $R_{l}$ to $W$. _Prepare_ subroutine also sets the values of
$x_{l}$ and $y_{l}$. _Restore_ subroutine (Algorithm 7) simply undoes the
changes made by step 7 and _Prepare_ subroutine, using $W$, $x_{l}$, and
$y_{l}$. Similarly, _RemoveNewClique_ subroutine (Algorithm 8) undoes the
modifications done to _clique cover_ and _candidate clique sets_ in
_AddNewClique_ subroutine. Note that all four subroutines have $O(\Delta)$
time bound.

Algorithm 8 RemoveNewClique

Input: A graph $G=(V,E)$, _Clique cover_ $\mathcal{C}$ (of a subset of edges
in $E$), _Candidate clique sets_ $\mathcal{S}$
Output: $\mathcal{C}$ and $\mathcal{S}$ restored by removing the last clique
added by _AddNewClique_

1: $p\leftarrow|\mathcal{C}|$

2: $\mathcal{C}\leftarrow\mathcal{C}\backslash C_{p}$

3: for each $z\in R_{p}$ do

4: $S_{z}\leftarrow S_{z}\backslash\\{p\\}$

5: end for

6: return $\mathcal{C},\mathcal{S}$

Next, we show correctness, time and space bounds, depth of the search tree,
and number of branches at each node of the search tree of Algorithm 4.

###### Lemma 5.1

Algorithm 4 correctly solves the parameterized problem _ECC-d_.

  * Proof.

Let $(G,(d,k))$ is an instance of _ECC-d_. Denote Algorithm 4 with $A_{x}$.

Consider a family of algorithms $A$ that consider uncovered edges $\\{x,y\\}$
in arbitrary order in step 4 of Algorithm 4. Clearly, $A_{x}\in A$.

Now, if $(G,(d,k))$ is a ’yes’ instance, then any algorithm $A_{y}\in A$ will
report it. This is because $A_{y}$ considers all possible ways to cover every
uncovered edge: either $\\{x,y\\}$ has to be covered with one of the existing
cliques $C_{l}$ such that $l\in S_{x}\cap S_{y}$ (step 5-13), or $\\{x,y\\}$
cannot be covered with any of the existing cliques (step 14-21). $A_{y}$
considers all such possible ways and allows search tree of depth with $k$
cliques. Similarly, if $(G,(d,k))$ is a ’no’ instance, then $A_{y}$ returns
$\phi$, denoting a ’no’ instance.

###### Lemma 5.2

In a search tree with at most $k$ cliques, Algorithm 4 takes $O(m+k\Delta)$
space.

  * Proof.

Let $T_{i}$ be a node in the search tree of Algorithm 4 when an uncovered
$\\{x,y\\}$ is covered with a new clique in steps 14-21 of Algorithm 4. In
$T_{i}$ we must have created the new clique only because all branches of steps
5-13 have failed. Any node $T_{j}$ such that $T_{i}$ is an ancestor of $T_{j}$
in the search tree would not select $\\{x,y\\}$ as uncovered. Since, number of
uncovered edge $\\{x,y\\}$ incident on any $x\in V$ is at most $|N(x)|$,
characterization of Lemma 3.1 holds for any _clique cover_ produced by
Algorithm 4.

In the proof of Lemma 3.8, since we have established that the part of the
proof related to Lemma 3.1 holds, it is straightforward to see that rest of
the proof holds for any _clique cover_ produced by Algorithm 4. It follows
that characterization of Lemma 3.8 holds for _candidate clique sets_
$\mathcal{S}$ used in Algorithm 4.

Entire $R_{l}$ data structures capture the same information as entire
_candidate clique sets_ $\mathcal{S}$, i.e., $\sum|R_{l}|=O(m+k\Delta)$. At
each node, in _Prepare_ subroutine, a vertex is either kept in $R_{l}$ or
moved to $W$. Therefore, space usage of $W$ data structures in total is
already accounted for, i.e., Algorithm 4 has $O(m+k\Delta)$ space bound.

###### Lemma 5.3

In a search tree with at most $k$ cliques, depth of the search tree of
Algorithm 4 is at most $dk$.

  * Proof.

Every new clique starts with two vertices (step 15), and each expansion of a
clique (steps 5-13) with an uncovered edge $\\{x,y\\}$ will add one new vertex
to the clique. Since $\forall C_{l}\in\mathcal{C},|C_{l}|\leq d+1$, number of
total possible expansions of a clique is $d$. Therefore, in a search tree with
at most $k$ cliques, depth of the search tree is at most $dk$.

###### Lemma 5.4

Number of branches at any node of the search tree of Algorithm 4 is at most
$\lfloor\frac{d^{2}}{4}\rfloor+1$.

  * Proof.

Let $N_{p}(u_{i})$ denote neighbours of $u_{i}$ that precede $u_{i}$ in the
degeneracy order of $V$, i.e.,
$N_{p}(u_{i})=N(u_{i})\cap\\{u_{1},u_{2},...,u_{i-1}\\}=N(u_{i})\backslash
N_{d}(u_{i})$.

Invariant: At any node in the search tree of Algorithm 4, if $x=u_{i}$, then
$\forall C_{l}\in\mathcal{C},C_{l}\subseteq\\{u_{i},...,u_{n}\\}$.

Preceding invariant holds trivially by our choice of uncovered edge
$\\{x,y\\}$ for each node. Since for any $x=u_{i}$, we only consider $y\in
N_{d}(x)$, any $z\in N_{p}(x)$ will not be included in any $C_{l}$ until we
process a node where $x=z$.

From the invariant it follows that for any $C_{l}\in\mathcal{C}$ such that
$l\in S_{x}$, either $x\in C_{l}$ or ($x\not\in C_{l}$ and $C_{l}\subseteq
N_{d}(x)$). But, for uncovered $\\{x,y\\}$, this must be the case that
$x\not\in C_{l}$. Therefore, we only need to consider the case $C_{l}\subseteq
N_{d}(x)$. The vertices of $N_{d}(x)$ can appear in most
$\lfloor\frac{|N_{d}(x)|^{2}}{4}\rfloor\leq\lfloor\frac{d^{2}}{4}\rfloor$
cliques [24]. It follows that $|S_{x}\cap
S_{y}|\leq\lfloor\frac{d^{2}}{4}\rfloor$.

Therefore, number of branches in step 5-13 is bounded by
$\lfloor\frac{d^{2}}{4}\rfloor$. Considering the branch for new clique at step
14-21, number of total branches at each node of the search tree is at most
$\lfloor\frac{d^{2}}{4}\rfloor+1$.

###### Theorem 5.1

For _ECC-d_ , Algorithm 4 is an FPT algorithm with time bound
$O^{*}(d^{O(dk)})$.

  * Proof.

Lemma 5.1 shows the correctness proof for Algorithm 4. From Lemma 5.4, number
of branches at any node of the search tree of Algorithm 4 is at most
$\lfloor\frac{d^{2}}{4}\rfloor+1$, and from Lemma 5.3, in a search tree with
at most $k$ cliques, depth of the search tree of Algorithm 4 is at most $dk$.

It follows that in a search tree with at most $k$ cliques, total number of
nodes is at most $(\lfloor\frac{d^{2}}{4}\rfloor+1)^{dk}$, i.e., time bound of
Algorithm 4 is $O^{*}(d^{O(dk)})$.

Each of the subroutines of Algorithm 4 has $O(\Delta)$ time bound. If _clique
cover_ size is $k$, considering $O(m+n)$ time to compute degeneracy ordering
of $V$ and all $N_{d}(x)$ lists, time bound to compute a _minimum clique
cover_ using Algorithm 4 is $O(m+n+\Delta
k(\lfloor\frac{d^{2}}{4}\rfloor+1)^{dk})$.

Note that we can exploit _candidate clique sets_ further. For example, we can
select uncovered edge arbitrarily, in step 4 of Algorithm 4, and still obtain
an FPT algorithm with respect to parameters $k$ and $\Delta$. Applicability of
_candidate clique sets_ may extend far beyond what we have demonstrated so
far. This paradigm of computing _clique cover_ may give rise to better
algorithms for many other objectives of _clique covers_. We show an example
next.

####  5.1.1 _Assignment-Minimum Clique Cover_.

An objective of _clique cover_ that has found application in problems
requiring statistical data visualization is called _assignment-minimum clique
cover_ [[20], [36], [60]]. The objective of this _clique cover_ is to find a
_clique cover_ $C$ of $G$ such that among the _clique covers_ of $G$, $C$ has
a minimum total number of vertices contained in the cliques of $C$, i.e.,
$\sum_{C_{l}\in\mathcal{C}}|C_{l}|$ is minimum. Prior search tree algorithm
for this objective of _clique cover_ requires bounds exponential in input size
for depth, number of branches, and space use [20]. Next, we describe
straightforward modifications of Algorithm 4 that solves this _clique cover_
problem exactly, but with polynomial bounds on depth, number of branches, and
space use.

For the _assignment-minimum clique cover_ , we would run modifications of
Algorithm 4 with parameter $k$ set to $m$, since no _clique cover_ would
require more than $m$ cliques. We would discard steps 9-11 and steps 17-19,
since we would need to explore all _clique covers_ with at most $m$ cliques.
Let $\mathcal{C}^{AM}$ denote a _clique cover_ with minimum total number of
vertices among the _clique covers_ explored in the search tree. Initially,
$\mathcal{C}^{AM}$ would be empty. In step 2 of Algorithm 4, while returning,
we would compare $\mathcal{C}^{AM}$ with $\mathcal{C}$, and if $\mathcal{C}$
has smaller total number of vertices than $\mathcal{C}^{AM}$, then we would
set $\mathcal{C}^{AM}$ to be $\mathcal{C}$. This algorithm has space bound
$O(m\Delta)$ (Lemma 5.2), depth bound $O(dm)$ (Lemma 5.3), and $O(d^{2})$
number of branches (Lemma 5.4).

###  5.2 FPT Algorithm Based on Maximal Clique Enumeration.

Our maximal clique enumeration based FPT algorithm follows similar structural
pattern as of the search tree algorithm of [34], but with crucial differences.
Using a heuristic, [34] select an uncovered edge at each node of the search
tree and enumerate all maximal cliques containing the edge. The expectation is
that the heuristic would reduce number of nodes in the search tree.
Nevertheless, at each node, search tree algorithm of [34] searches maximal
cliques in a subgraph containing at most $2^{k}$ vertices. We utilize
degeneracy ordering to choose an edge, and restrict the search for maximal
cliques in the later neighbours (in the degeneracy ordering) of an end vertex
of the edge. At each node, our algorithm searches maximal cliques in a
subgraph containing at most $d$ vertices.

Algorithm 9 MaximalCliqueFPT

Input: A graph $G=(V,E)$, _Clique cover_ $\mathcal{C}$ (of a subset of edges
in $E$), an integer $k$
Output: If exists, a _clique cover_ $\mathcal{C}$ of $G$ with
$|\mathcal{C}|\leq k$; otherwise $\phi$

1: if $\mathcal{C}$ covers $G$ then

2: return $\mathcal{C}$

3: end if

4: if $k\leq 0$ then

5: return $\phi$

6: end if

7: Select an uncovered edge $\\{x,y\\}$ such that $y\in N_{d}(x)$, and in the
degeneracy order of $V$, $x$ precedes any other vertex with such a neighbour
$y$

8: for each maximal clique $R$ containing $\\{x,y\\}$ in the subgraph induced
by $(N_{d}(x)\cap N(y))\cup\\{x,y\\}$ do

9: $Q\leftarrow MaximalCliqueFPT(G,\mathcal{C}\cup\\{R\\},k-1)$

10: if $Q\neq\phi$ then

11: return $Q$

12: end if

13: end for

14: return $\phi$

Algorithm 9 outlines our maximal clique enumeration based FPT algorithm that
solves _ECC-d_. In step 7 of Algorithm 9, we select an uncovered edge that
helps us to bound number of maximal cliques need to be enumerated at each node
of the search tree. More specifically, we select an edge $\\{x,y\\}$ such that
$y\in N_{d}(x)$ and all neighbours of $x$ that precedes $x$ in the degeneracy
order of $V$ do need not to be considered in the search of maximal cliques for
$\\{x,y\\}$. Finally, we branch into each of the choices of maximal cliques in
steps 8-13. We obtain following results.

###### Lemma 5.5

Algorithm 9 correctly solves the parameterized problem _ECC-d_.

  * Proof.

Let $N_{p}(u_{i})$ denote neighbours of $u_{i}$ that precede $u_{i}$ in the
degeneracy order of $V$, i.e.,
$N_{p}(u_{i})=N(u_{i})\cap\\{u_{1},u_{2},...,u_{i-1}\\}=N(u_{i})\backslash
N_{d}(u_{i})$. Let $(G,(d,k))$ is an instance of _ECC-d_. Denote Algorithm 9
with $A_{x}$.

Consider a family of algorithms $B$ that consider uncovered edges $\\{x,y\\}$
in arbitrary order in step 7 of Algorithm 9, and in steps 8-13 branches into
each of the choices of maximal cliques containing $\\{x,y\\}$ in the subgraph
induced by $(N(x)\cap N(y))\cup\\{x,y\\}$.

Now, if $(G,(d,k))$ is a ’yes’ instance, then any algorithm $B_{y}\in B$ will
report it. This is because $B_{y}$ considers all possible ways to cover every
uncovered edge: $\\{x,y\\}$ can be covered with one of the maximal cliques
containing $\\{x,y\\}$ in the subgraph induced by $(N(x)\cap
N(y))\cup\\{x,y\\}$. $B_{y}$ considers all such possible maximal cliques, and
allows search tree of depth with $k$ cliques. Similarly, if $(G,(d,k))$ is a
’no’ instance, then $B_{y}$ returns $\phi$, denoting a ’no’ instance.

$A_{x}$ deviates from the family of algorithms $B$: $A_{x}$ considers maximal
cliques containing $\\{x,y\\}$ in the subgraph induced by $(N_{d}(x)\cap
N(y))\cup\\{x,y\\}$. Next, we show that this deviation is safe.

Invariant: At any node in the search tree of Algorithm 9, if $x=u_{i}$, then
all edges incident on $\\{u_{1},u_{2}...,u_{i-1}\\}$ are covered.

Preceding invariant holds trivially, by our choice of uncovered edge
$\\{x,y\\}$, for each node in the search tree.

Note that $y\in N_{d}(x)\subseteq\\{u_{i+1},...,u_{n}\\}$ and $N_{d}(x)\cap
N(y)\subseteq\\{u_{i+1},...,u_{n}\\}$. Now, the vertices that are not
considered by $A_{x}$ in the enumeration of maximal cliques are $(N(x)\cap
N(y))\backslash(N_{d}(x)\cap N(y))=N_{p}(x)\cap
N(y)\subseteq\\{u_{1},...,u_{i-1}\\}$. By the invariant, all edges incident on
$\\{u_{1},....,u_{i-1}\\}$ are covered when we are considering maximal cliques
for $\\{x,y\\}$. Therefore, it is safe to consider only maximal cliques in the
subgraph induced by $(N_{d}(x)\cap N(y))\cup\\{x,y\\}$.

Using the Moon-Moser bound of [55], we get desired time bound for Algorithm 9.

###### Theorem 5.2

For _ECC-d_ , Algorithm 9 is an FPT algorithm with time bound
$O^{*}(3^{O(dk)})$.

  * Proof.

Lemma 5.5 shows the correctness proof for Algorithm 9. Next, we show the
fixed-parameter tractability of Algorithm 9.

Since $|N_{d}(x)\cap N(y)|\leq d$, by the Moon-Moser bound [55], number of
maximal cliques in a subgraph induced by vertices of $N_{d}(x)\cap N(y)$ is at
most $3^{\frac{d}{3}}$, i.e., number of maximal cliques enumerated at each
node of the search tree is at most $3^{\frac{d}{3}}$. Therefore, total number
of nodes in the search tree is at most $3^{\frac{dk}{3}}$, i.e., time bound of
Algorithm 9 is $O^{*}(3^{O(dk)})$.

At each node of the search tree of Algorithm 9, we need to enumerate maximal
cliques of a subgraph containing $|N_{d}(x)\cap N(y)|=O(d)$ vertices. Assuming
maximal clique enumeration algorithm uses space proportional to the size of
input graph, in a search tree with at most $k$ cliques, space use of Algorithm
9 is $O(m+d^{2}k)$.

Using the Moon-Moser bound [55] for the search tree algorithm of [34], we
obtain $O^{*}(3^{O(k2^{k})})$ time bound. It follows that for $2^{k}>d$,
Algorithm 9 improves upon the time bound of the search tree algorithm of [34]
by a factor of $3^{k(2^{k}-d)}$.

We can also compare the algorithms using time bounds of maximal clique
enumeration algorithms. Using the time bound of [22], we get
$O^{*}{}(d^{k}3^{O(dk)})$ and $O^{*}(2^{k^{2}}3^{O(dk)})$ time bounds for
Algorithm 9 and search tree algorithm of [34] respectively. For $2^{k}>d$,
this results in $(\frac{2^{k}}{d})^{k}$ factor improvement of time bound by
Algorithm 9 on the time bound of the search tree algorithm of [34].

Note that our FPT algorithm based on maximal clique enumeration (Algorithm 9)
has better dependency on $d$ in the time bound than our FPT algorithm based on
_candidate clique sets_ (Algorithm 4): $O^{*}(3^{O(dk)})$ vs.
$O^{*}(d^{O(dk)})$. Therefore, we expect Algorithm 9 to perform better than
Algorithm 4 on dense graphs.

##  6 Experimental Analyses

In this section we present a summary of our experimental analyses of our FPT
algorithms (Section 6.1) and greedy framework (Section 6.2). We compare
runtimes and other metrics of our algorithms against the state of the art, on
random graphs, as well as on real-world graphs. We ask reader to consult
Appendix A for further details of the results discussed in this section.

We ran our experiments on an AMD Epyc 7662 processors based system (part of
Purdue University Community Cluster) called
Bell111rcac.purdue.edu/compute/bell. Nodes in the cluster has 128 cores, each
core running at 2.0 GHz, with 16 MB unified L3 Cache. Bell nodes have 256-1024
GB memory, and run CentOS 7 operating system. We implemented our algorithms in
the C++ programming language and compiled using gcc compiler (version 9.3.0)
with the -O3 optimization flag. Our implementations are freely available upon
request (will be available at github.com).

###  6.1 Experimental Analysis of FPT algorithms

####  6.1.1 Dataset.

In this analysis we evaluated all our algorithms using random graphs from the
$G(n,p)$ model. Varying $n$ (150-1000) and $p$ (0.035 - 0.11), we generated 16
ensembles of $G(n,p)$, each containing 32 random graphs. Appendix A.1 contains
details of the dataset and related statistics.

####  6.1.2 Algorithms Tested.

We have found that prepossessing with data reduction rules such as presented
by [34] is crucial for the search tree algorithms. In our study we have not
found any graph instance which has application of interleaving data reduction
rules in the search tree (as done in [34]). Therefore, we used data reduction
rules of [34] as prepossessing steps for our FPT algorithms. We implemented
and tested four algorithms: two of our FPT algorithms outlined in Algorithm 4
(_CFPT_) and Algorithm 9 (_MFPT_), the FPT algorithm of [34] (_GFPT_), and the
FPT algorithm of [34] without interleaving the data reduction rules (_GFPT-
NI_). We evaluated _MFPT_ with three different _Bron-Kerbosch_ [7] based
maximal clique enumeration algorithms: [44] (_Koch_), [67] (_TTT_), [22]
(_ELS_); and based on our evaluation, we used _ELS_ based implementation for
_MFPT_ , _GFPT_ , and _GFPT-NI_ (Appendix A.7).

####  6.1.3 Experimental Results.

All tested algorithms were allowed to run up to 4 hours on each of the 512
graphs. Let _completion rate_ denote percentage of number of graphs (in each
of the graph ensembles) for which _clique covers_ were computed within 4
hours. _Completion rates_ are significantly small from _GFPT_ (18.75%-46.88%)
and _GFPT-NI_ (31.25%-68.75%) (Appendix A.2). Both _CFPT_ (_completion rates_
93.75% -100%) and _MFPT_ (_completion rates_ 96.88% -100%) computed _clique
cover_ of all 32 graphs of most of the graph ensembles.

Table 1: Average runtimes of _GFPT_ , _CFPT_ , and _MFPT_. Each of the row statistics is on the instances on which _GFPT_ terminated within 4 hours (Appendix A.2). Graph | Average Runtime (seconds)
---|---
_GFPT_ | _CFPT_ | _MFPT_
er_150_0100 | 3123.58 | 8.62 | 7.90
er_150_0102 | 3545.24 | 8.98 | 22.11
er_150_0104 | 2939.30 | 12.56 | 5.21
er_150_0106 | 4121.85 | 23.70 | 22.75
er_150_0108 | 4071.08 | 2.64 | 9.97
er_150_0110 | 4117.19 | 0.61 | 7.14
er_250_0070 | 2570.21 | 13.66 | 4.59
er_260_0070 | 3190.58 | 2.14 | 3.45
er_270_0070 | 3724.74 | 5.06 | 9.04
er_280_0070 | 2001.80 | 8.56 | 11.10
er_290_0070 | 3327.44 | 13.34 | 26.33
er_300_0070 | 3921.95 | 2.21 | 9.98
er_200_009 | 4437.79 | 6.24 | 12.18
er_500_005 | 4425.95 | 1.99 | 7.39
er_750_0040 | 5227.85 | 1.82 | 5.18
er_1000_0035 | 3405.49 | 2.80 | 6.20

Table 1 shows the runtime comparisons of _GFPT_ , _CFPT_ , and _MFPT_. Both of
our algorithms show significantly better performance than _GFPT_ : _CFPT_ is
approximately 100-5000 times faster than _GFPT_ , and _MFPT_ is approximately
250-900 times faster than _GFPT_ (see Appendix A.3 for geometric mean of
ratios of runtimes).

_GFPT-NI_ showed better performance than _GFPT_ on some of the graph ensembles
(Table 8, Appendix A.3). _GFPT_ and _GFPT-NI_ have the same search tree for
all our test graphs, since in our study we have not found any application of
data reduction rules during the execution of the search tree algorithm of
[34]. The reduction of runtime of _GFPT-NI_ , compared to _GFPT_ , comes from
the time saved by not attempting to apply data reduction rules at each node of
the search tree (for a graph with $n$ vertices, data reduction rules have
$O(n^{4}$) time bound [34]). But, even with this savings in runtimes,
performance of _GFPT-NI_ are nowhere close to the performances of our
algorithms.

The reason for stunning performances of our algorithms is in the fact that the
search trees generated by our algorithms are remarkably small. Table 2 shows
comparison results of number of nodes in the search trees of _GFPT_ and
_MFPT_. Search trees of _GFPT_ (or _GFPT-NI_) and _MFPT_ are directly
comparable: every node in the search tree corresponds to a new clique, added
to _clique cover_. Search trees of _MFPT_ are approximately 50-150 times
smaller than search trees of _GFPT_ (or _GFPT-NI_). Note that these massive
reductions of number of nodes in the search trees are only on the graphs on
which _GFPT_ terminated within 4 hours. With increased time cut off ($>$ 4
hours), these reductions would get even larger: both _CFPT_ and _MFPT_ can
solve graph instances in minutes, which _GFPT_ could not solve in 24 hours.

Search trees of _CFPT_ are not directly comparable with search trees of other
algorithms: search tree of _CFPT_ has depth bound $dk$ (Lemma 5.3), whereas
search trees of other algorithms have depth bound $k$. Nevertheless, _CFPT_
shows even better performance than _MFPT_ on most of the graph ensembles,
despite the fact that _MFPT_ has better dependency on $d$ in the time bound
than _CFPT_ : $O^{*}(3^{O(dk)})$ vs. $O^{*}(d^{O(dk)})$.

Table 2: Average number of nodes (in million) generated in the search trees of _GFPT_ (or _GFPT-NI_) and _MFPT_. Last column shows geometric mean of ratios of number of nodes in the search tree of _GFPT_ to number of nodes in the search tree of _MFPT_. Graph | Average number of | Geometric mean
---|---|---
search tree nodes | of ratios of
(in million) | number of search
_GFPT_ | _MFPT_ | tree nodes
er_150_0100 | 2387.42 | 36.16 | 82.90
er_150_0102 | 4542.24 | 77.11 | 82.51
er_150_0104 | 4702.10 | 86.70 | 86.52
er_150_0106 | 3266.89 | 36.06 | 111.32
er_150_0108 | 3730.83 | 36.09 | 137.56
er_150_0110 | 6287.48 | 111.71 | 85.79
er_250_0070 | 2335.21 | 14.83 | 98.83
er_260_0070 | 5622.55 | 27.29 | 144.26
er_270_0070 | 4440.97 | 36.18 | 111.81
er_280_0070 | 781.74 | 18.62 | 44.37
er_290_0070 | 3116.29 | 56.33 | 58.73
er_300_0070 | 2075.01 | 26.86 | 64.44
er_200_009 | 4443.24 | 105.26 | 107.83
er_500_005 | 4410.74 | 24.63 | 153.69
er_750_0040 | 3649.86 | 67.32 | 126.41
er_1000_0035 | 3400.76 | 27.74 | 94.64

###  6.2 Experimental Analysis of Greedy Framework

####  6.2.1 Dataset.

Our dataset for this analysis consists of 30 real-world graphs with number of
edges ranging from approximately 1 million to 1.8 billion (Appendix A.4). The
dataset contains 21 brain networks from networkrepository.com [66], 6 social
networks from the Stanford Large Network Dataset Collection [47], and 3 gene
regulatory networks from the Suite Sparse Matrix Collection (sparse.tamu.edu
[16]).

####  6.2.2 Algorithms Tested.

Our graphs of this analysis are not solvable by the FPT algorithms in a
reasonable amount of time (24 hours). Therefore, we consider fast variants of
the state of the art heuristic algorithms. We tested four algorithms:
improvement of the Kellerman heuristic [42] by [34] (_g-ALG_), the _ECC-rc_
variant of heuristic algorithm by [11] (_c-ALG_), two of our algorithms,
outlined in Algorithm 3 (_CCSG_) and modifications of _CCSG_ for degeneracy
ordering outlined in Section 4.3 (_CCSD_). For _CCSG_ (also for _g-ALG_), we
used degree based edge ordering (edges incident on low degree vertices are
processed first), and for both _CCSG_ and _CCSD_ we selected largest clique in
step 5 of Algorithm 3.

####  6.2.3 Metrics of Comparison.

Our metric to compare quality of _clique cover_ is relative reduction of
_clique cover size_. For relative reduction, we do not consider _trivial
cliques_ 222A _trivial clique_ is an edge whose end vertices do not share any
common vertex in their neighbourhood. Any algorithm must cover every such edge
by a clique containing only the edge. of a graph in the _clique cover_ , since
_trivial cliques_ are common among all _clique covers_. Therefore, if number
of cliques (_without trivial cliques_) produced by algorithm ’A’, and
algorithm ’B’ are ’a’, and ’b’, respectively, then relative reduction of
_clique cover_ size by ’B’ (relative to ’A’) is (1 - $\frac{b}{a})\times 100$.

For the performance comparison we use relative performance: if ’a’ is the
runtime of algorithm ’A’, and ’b’ (in same unit as ’a’) is the runtime of
algorithm ’B’, then relative performance of ’B’ (relative to ’A’) is the ratio
of ’a’ to ’b’.

####  6.2.4 Experimental Results.

All tested algorithms were allowed to run up to 24 hours on each of the graphs
of the dataset. Out of 30 graphs (Appendix A.4), _c-ALG_ terminated on 29
graphs, and _g-ALG_ terminated only on 13 graphs. Our algorithms terminated on
all the graphs within 3 hours: longest time taken by _CCSG_ is 2.57 hours, and
by _CCSD_ is 2.26 hours.

Table 3: Average relative reduction of _clique cover_ size by CCSD and _CCSG_ (relative to g-ALG and c-ALG). Algorithm | Average relative reduction
---|---
compared | CCSG | CCSD
g-ALG | 27.14 | 30.15
c-ALG | 13.15 | 16.36
Table 4: Geometric mean of relative performances of CCSD and _CCSG_ (relative to g-ALG and c-ALG). Algorithm | Mean relative performance
---|---
compared | CCSG | CCSD
g-ALG | 80.22 | 93.91
c-ALG | 2.51 | 2.91

For the graphs on which _g-ALG_ and _c-ALG_ terminated within 24 hours, Table
3 and Table 4 summarize comparison of _CCSG_ and _CCSD_ against _g-ALG_ and
_c-ALG_ on the two metrics (details are in Appendix A.5). On both metrics,
both of our algorithms outperformed _g-ALG_ and _c-ALG_. Notably, our
algorithms are approximately 90 times faster on average than _g-ALG_ , and
_clique cover_ size of our algorithms are approximately 30% smaller on average
compared to _g-ALG_.

$10^{6}$$10^{7}$$10^{8}$$10^{9}$$10^{6}$$10^{7}$$10^{8}$$10^{9}$$10^{10}$$m$$CCS_{max}$CCSG$m$$2m$$3m$
Figure 4: $CCS_{max}=max\\{\sum_{x\in V}|S_{x}|\\}$ vs. $m$ for all 30 test
graphs of Table 9.

All tested algorithms used same post-processing step (by [45]). For the entire
dataset, average and maximum relative reduction of _clique cover_ size by
post-processing in CCSG are only 0.05 and 0.1 respectively: this gives strong
experimental verification of extremely rare redundancy in _locally minimal
clique cover_ (Lemma 3.4). Also, for the graphs of Appendix A.1, _clique
cover_ sizes from our greedy algorithms are only 1% to 2% larger on average
than the optimal _clique cover_ sizes; but our greedy algorithms are orders of
magnitude faster than the FPT algorithms (Appendix A.6).

$10^{6}$$10^{7}$$10^{8}$$10^{9}$$10^{6}$$10^{8}$$10^{10}$$10^{12}$$m$$CCS_{tsi}$CCSG$m\Delta$$md$
Figure 5: Total size of the intersections at step 4 of Algorithm 3
($CCS_{tsi}$) vs. $m$ for all 30 test graphs of Table 9. Both $m\Delta$ and
$md$ values show that they are consistent upper bounds of $CCS_{tsi}$.

In Theorem 4.1 and Theorem 4.2 we have described results for the cases when
the bound $\sum_{x\in V}|S_{x}|=O(m)$ holds. We have found that the bound
holds for all our test graphs. Algorithm 3 grows and shrinks the value of the
$\sum_{x\in V}|S_{x}|$. In Figure 4, we show the maximum value of the sum
$CCS_{max}=max\\{\sum_{x\in V}|S_{x}|\\}$ in the entire execution of the
algorithm. Also, in Figure 5, we plotted total size of the intersections
$CCS_{tsi}$ at step 4 of Algorithm 3, which is bounded by $\sum_{\\{x,y\\}\in
E}min\\{|S_{x}|,|S_{y}|\\}$. $CCS_{tsi}$ is the dominating time of Algorithm
3. To avoid cluttering the plots, we omitted similar results of _CCSD_.

$10^{6}$$10^{7}$$10^{8}$$10^{9}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$10^{9}$$m$Time
(ms)CCSGCCSD$y=x$ Figure 6: Runtimes (milliseconds) of _CCSG_ and _CCSD_ vs.
$m$ for all 30 real-world graphs of the dataset.

In Figure 6, we show runtimes (milliseconds) of _CCSG_ and _CCSD_ against
number of edges of graph. We conclude that for the test graphs of Table 9,
both _CCSG_ and _CCSD_ exhibit linear time bound.

##  7 Conclusions

We have presented a set theoretic concept and its use as a design paradigm for
computing different objectives of _clique covers_. We have shown that
integration of structural parameters of graph along with natural parameter can
lead to design of better algorithms for _clique cover_ problems, both in
asymptotic time bound and in practice. We have provided detailed comparison
results of different metrics of our algorithms against the state of the art,
substantiating excellent performance of our algorithms.

Motivated by real-world applications, recently, a number of _clique cover_
problems have been studied [[12], [26]] that consider edge weights of graph.
We believe (alluding to the polynomial bounds we have shown for the
_assignment-minimum clique cover_ [20]) our set theoretic concept and its use
in utilizing structural parameters of graph would prompt further studies of
these edge weighted _clique cover_ problems.

## References

  * [1] Pankaj K Agarwal, Noga Alon, Boris Aronov, and Subhash Suri.  Can visibility graphs be represented compactly?  Discrete & Computational Geometry, 12(3):347–365, 1994.
  * [2] Noga Alon.  Covering graphs by the minimum number of equivalence relations.  Combinatorica, 6(3):201–206, 1986.
  * [3] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi.  Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.  Springer Science & Business Media, 2012.
  * [4] Vladimir Batagelj and Matjaz Zaversnik.  An o (m) algorithm for cores decomposition of networks.  arXiv preprint cs/0310049, 2003.
  * [5] Michael Behrisch and Anusch Taraz.  Efficiently covering complex networks with cliques of similar vertices.  Theoretical Computer Science, 355(1):37–47, 2006.
  * [6] Mathieu Blanchette, Ethan Kim, and Adrian Vetta.  Clique cover on sparse networks.  In 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 93–102. SIAM, 2012.
  * [7] Coen Bron and Joep Kerbosch.  Algorithm 457: finding all cliques of an undirected graph.  Communications of the ACM, 16(9):575–577, 1973.
  * [8] L Sunil Chandran, Davis Issac, and Andreas Karrenbauer.  On the parameterized complexity of biclique cover and partition.  In 11th International Symposium on Parameterized and Exact Computation, pages 1–13. Schloss Dagstuhl, 2017.
  * [9] Maw-Shang Chang and Haiko Müller.  On the tree-degree of graphs.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 44–54. Springer, 2001.
  * [10] Marek Chrobak and David Eppstein.  Planar orientations with low out-degree and compaction of adjacency matrices.  Theoretical Computer Science, 86(2):243–266, 1991.
  * [11] Alessio Conte, Roberto Grossi, and Andrea Marino.  Large-scale clique cover of real-world networks.  Information and Computation, 270:104464, 2020.
  * [12] Madison Cooley, Casey S Greene, Davis Issac, Milton Pividori, and Blair D Sullivan.  Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition.  arXiv preprint arXiv:2106.00657, 2021.
  * [13] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [14] Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström.  Clique cover and graph separation: New incompressibility results.  ACM Transactions on Computation Theory (TOCT), 6(2):1–19, 2014\.
  * [15] Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk.  Known algorithms for edge clique cover are probably optimal.  SIAM Journal on Computing, 45(1):67–83, 2016.
  * [16] Timothy A Davis and Yifan Hu.  The university of florida sparse matrix collection.  ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011\.
  * [17] Alice M Dean, Joan P Hutchinson, and Edward R Scheinerman.  On the thickness and arboricity of a graph.  Journal of Combinatorial Theory, Series B, 52(1):147–151, 1991\.
  * [18] Rodney G Downey and Michael R Fellows.  Fundamentals of parameterized complexity, volume 4.  Springer, 2013.
  * [19] Alina Ene, William Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, and Robert E Tarjan.  Fast exact and heuristic methods for role minimization problems.  In Proceedings of the 13th ACM symposium on Access control models and technologies, pages 1–10, 2008.
  * [20] John M Ennis, Charles M Fayle, and Daniel M Ennis.  Assignment-minimum clique coverings.  Journal of Experimental Algorithmics (JEA), 17:1–1, 2012.
  * [21] David Eppstein, Michael T Goodrich, and Jeremy Yu Meng.  Confluent layered drawings.  Algorithmica, 47(4):439–452, 2007.
  * [22] David Eppstein, Maarten Löffler, and Darren Strash.  Listing all maximal cliques in sparse graphs in near-optimal time.  In International Symposium on Algorithms and Computation, pages 403–414. Springer, 2010.
  * [23] David Eppstein, Maarten Löffler, and Darren Strash.  Listing all maximal cliques in large sparse real-world graphs.  Journal of Experimental Algorithmics (JEA), 18:3–1, 2013.
  * [24] Paul Erdös, Adolph W Goodman, and Louis Pósa.  The representation of a graph by set intersections.  Canadian Journal of Mathematics, 18:106–112, 1966.
  * [25] Paul Erdős and András Hajnal.  On chromatic number of graphs and set-systems.  Acta Mathematica Academiae Scientiarum Hungarica, 17(1-2):61–99, 1966.
  * [26] Andreas Emil Feldmann, Davis Issac, and Ashutosh Rai.  Fixed-parameter tractability of the weighted edge clique partition problem.  In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [27] Andres Figueroa, James Borneman, and Tao Jiang.  Clustering binary fingerprint vectors with missing values for dna array data analysis.  Journal of Computational biology, 11(5):887–901, 2004.
  * [28] Jörg Flum and Martin Grohe.  Parameterized complexity theory.  Springer Science & Business Media, 2006.
  * [29] Eugene C Freuder.  A sufficient condition for backtrack-free search.  Journal of the ACM (JACM), 29(1):24–32, 1982.
  * [30] Alan Frieze and Bruce Reed.  Covering the edges of a random graph by cliques.  Combinatorica, 15(4):489–497, 1995.
  * [31] Harold N Gabow and Herbert H Westermann.  Forests, frames, and games: algorithms for matroid sums and applications.  Algorithmica, 7(1):465–497, 1992.
  * [32] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [33] Floris Geerts, Bart Goethals, and Taneli Mielikäinen.  Tiling databases.  In International conference on discovery science, pages 278–289. Springer, 2004.
  * [34] Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  Data reduction, exact, and heuristic algorithms for clique cover.  In Proceedings of the Meeting on Algorithm Engineering & Expermiments, pages 86–94. Society for Industrial and Applied Mathematics, 2006\.
  * [35] Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  Data reduction and exact algorithms for clique cover.  Journal of Experimental Algorithmics (JEA), 13:2, 2009.
  * [36] Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Hans-Peter Piepho, and Ramona Schmid.  Algorithms for compact letter displays: Comparison and evaluation.  Computational Statistics & Data Analysis, 52(2):725–736, 2007\.
  * [37] Hermann Gruber and Markus Holzer.  Inapproximability of nondeterministic state and transition complexity assuming p$\neq$ np.  In International Conference on Developments in Language Theory, pages 205–216. Springer, 2007.
  * [38] András Gyárfás.  A simple lower bound on edge coverings by cliques.  Discrete Mathematics, 85(1):103–104, 1990.
  * [39] Joel Helling, PJ Ryan, WF Smyth, and Michael Soltys.  Constructing an indeterminate string from its associated graph.  Theoretical Computer Science, 710:88–96, 2018.
  * [40] Douglas N Hoover.  Complexity of graph covering problems for graphs of low degree.  Journal of Combinatorial Mathematics and Combinatorial Computing, 11(187-208):7, 1992.
  * [41] Wen-Lian Hsu and Kuo-Hui Tsai.  Linear time algorithms on circular-arc graphs.  Information Processing Letters, 40(3):123–129, 1991.
  * [42] Eduardo Kellerman.  Determination of keyword conflict.  IBM Technical Disclosure Bulletin, 16(2):544–546, 1973.
  * [43] Lefteris M Kirousis and Dimitris M Thilikos.  The linkage of a graph.  SIAM Journal on Computing, 25(3):626–647, 1996.
  * [44] Ina Koch.  Enumerating all connected maximal common subgraphs in two graphs.  Theoretical Computer Science, 250(1-2):1–30, 2001.
  * [45] Lawrence T. Kou, Larry J. Stockmeyer, and Chak-Kuen Wong.  Covering edges by cliques with regard to keyword conflicts and intersection graphs.  Communications of the ACM, 21(2):135–139, 1978.
  * [46] Łukasz Kowalik.  Approximation scheme for lowest outdegree orientation and graph density measures.  In International Symposium on Algorithms and Computation, pages 557–566. Springer, 2006.
  * [47] Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * [48] Don R Lick and Arthur T White.  k-degenerate graphs.  Canadian Journal of Mathematics, 22(5):1082–1096, 1970.
  * [49] Carsten Lund and Mihalis Yannakakis.  On the hardness of approximating minimization problems.  Journal of the ACM (JACM), 41(5):960–981, 1994.
  * [50] Shaohan Ma, Walter D Wallis, and Julin Wu.  Clique covering of chordal graphs.  Utilitas Mathematica, 36:151–152, 1989.
  * [51] Alex Markham and Moritz Grosse-Wentrup.  Measurement dependence inducing latent causal models.  In Conference on Uncertainty in Artificial Intelligence, pages 590–599. PMLR, 2020.
  * [52] David W Matula and Leland L Beck.  Smallest-last ordering and clustering and graph coloring algorithms.  Journal of the ACM (JACM), 30(3):417–427, 1983.
  * [53] Ryan McIntyre and Michael Soltys.  An improved upper bound and algorithm for clique covers.  Journal of Discrete Algorithms, 48:42–56, 2018.
  * [54] Terry A McKee and Fred R McMorris.  Topics in intersection graph theory.  SIAM, 1999.
  * [55] John W Moon and Leo Moser.  On cliques in graphs.  Israel journal of Mathematics, 3(1):23–28, 1965.
  * [56] Egbert Mujuni and Frances Rosamond.  Parameterized complexity of the clique partition problem.  In Proceedings of the fourteenth symposium on Computing: the Australasian theory-Volume 77, pages 75–78, 2008.
  * [57] Dana S Nau, George Markowsky, Max A Woodbury, and D Bernard Amos.  A mathematical analysis of human leukocyte antigen serology.  Mathematical Biosciences, 40(3-4):243–270, 1978.
  * [58] Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstadter, Max Reuter, Olivier Duron, and Marie-France Sagot.  Mod/resc parsimony inference: Theory and application.  Information and Computation, 213:23–32, 2012.
  * [59] James Orlin.  Contentment in graph theory: covering graphs with cliques.  In Indagationes Mathematicae (Proceedings), volume 80, pages 406–424. Elsevier, 1977.
  * [60] Hans-Peter Piepho.  An algorithm for a letter-based representation of all-pairwise comparisons.  Journal of Computational and Graphical Statistics, 13(2):456–466, 2004.
  * [61] Erich Prisner.  Clique covering and clique partition in generalizations of line graphs.  Discrete applied mathematics, 56(1):93–98, 1995.
  * [62] Norman J Pullman.  Clique coverings of graphs—a survey.  Combinatorial Mathematics X, pages 72–85, 1983.
  * [63] Subramanian Rajagopalan, Manish Vachharajani, and Sharad Malik.  Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints.  In Proceedings of the 2000 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, pages 157–164, 2000\.
  * [64] Fred S Roberts.  Applications of edge coverings by cliques.  Discrete Applied Mathematics, 10(1):93–109, 1985.
  * [65] Neil Robertson and Paul D Seymour.  Graph minors. iii. planar tree-width.  Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984.
  * [66] Ryan A. Rossi and Nesreen K. Ahmed.  The network data repository with interactive graph analytics and visualization.  In AAAI, 2015.
  * [67] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi.  The worst-case time complexity for generating all maximal cliques and computational experiments.  Theoretical computer science, 363(1):28–42, 2006.
  * [68] Jierui Xie, Stephen Kelley, and Boleslaw K Szymanski.  Overlapping community detection in networks: The state-of-the-art and comparative study.  Acm Computing Surveys, 45(4):1–35, 2013.

##  A Additional Details of Experimental Analyses

###  A.1 Dataset for the analysis of Section 6.1.

In our preliminary experiments, we found that many random graph instances that
are solvable by _CFPT_ and _MFPT_ in minutes are not solvable by _GFPT_ or
_GFPT-NI_ in 24 hours. Therefore, by extensive testing we selected $n$ and $p$
such that $G(n,p)$ instances are likely to be solvable by _GFPT_ in 4 hours.
These graphs are chosen so that search trees of _GFPT_ are not too small for
comparison, but not too large for 4 hours time cut off. For each fixed $n$ and
$p$ of Table 5, we generated as many random graphs as needed to find 32 random
graphs that have number of uncovered edges between 45 and 70, after the
application of data reduction rules of [34].

Table 5: Our test graphs from the $G(n,p)$ model. For fixed $n$ and $p$, we collected 32 $G(n,p)$ instances, i.e., each row stands for an ensemble of 32 random graphs. Graph | $n$ | $p$ |  $m$ (average) |  $d$ (average) |  $\Delta$ (average)
---|---|---|---|---|---
er_150_0100 | 150 | 0.100 | 1126.22 | 10.34 | 25.44
er_150_0102 | 150 | 0.102 | 1147.81 | 10.63 | 25.38
er_150_0104 | 150 | 0.104 | 1163.41 | 10.84 | 26.38
er_150_0106 | 150 | 0.106 | 1168.22 | 10.75 | 26.25
er_150_0108 | 150 | 0.108 | 1183.09 | 11.06 | 26.25
er_150_0110 | 150 | 0.110 | 1196.81 | 11.06 | 26.19
er_250_007 | 250 | 0.070 | 2218.44 | 12.28 | 30.91
er_260_007 | 260 | 0.070 | 2393.63 | 12.91 | 31.66
er_270_007 | 270 | 0.070 | 2564.31 | 13.22 | 31.78
er_280_007 | 280 | 0.070 | 2739.75 | 13.78 | 32.25
er_290_007 | 290 | 0.070 | 2921.41 | 14.16 | 32.91
er_300_007 | 300 | 0.070 | 3110.97 | 14.81 | 34.13
er_200_009 | 200 | 0.090 | 1765.94 | 12.31 | 29.31
er_500_005 | 500 | 0.050 | 6233.88 | 17.84 | 40.97
er_750_004 | 750 | 0.040 | 11238.00 | 21.56 | 48.31
er_1000_0035 | 1000 | 0.035 | 17413.44 | 25.63 | 53.84

###  A.2 _Completion Rates_ of FPT algorithms.

Table 6 shows percentage of number of graphs (in each of the graph ensembles)
for which _clique covers_ were computed within 4 hours by the FPT algorithms.

Table 6: Completion rates of the FPT algorithms in 4 hours on the 32 graphs of each of the graph ensembles of Table 5. Graph | _GFPT_ | _GFPT-NI_ | _CFPT_ | _MFPT_
---|---|---|---|---
er_150_0100 | 46.88 | 62.50 | 96.88 | 100.00
er_150_0102 | 43.75 | 65.63 | 100.00 | 100.00
er_150_0104 | 31.25 | 53.13 | 93.75 | 96.88
er_150_0106 | 43.75 | 62.50 | 93.75 | 96.88
er_150_0108 | 31.25 | 50.00 | 100.00 | 100.00
er_150_0110 | 18.75 | 31.25 | 96.88 | 100.00
er_250_007 | 40.63 | 46.88 | 100.00 | 96.88
er_260_007 | 34.38 | 56.25 | 100.00 | 96.88
er_270_007 | 28.13 | 50.00 | 100.00 | 100.00
er_280_007 | 43.75 | 46.88 | 100.00 | 100.00
er_290_007 | 31.25 | 46.88 | 100.00 | 100.00
er_300_007 | 37.50 | 43.75 | 100.00 | 96.88
er_200_009 | 34.38 | 53.13 | 100.00 | 96.88
er_500_005 | 31.25 | 50.00 | 100.00 | 100.00
er_750_004 | 28.13 | 46.88 | 100.00 | 96.88
er_1000_0035 | 37.50 | 68.75 | 100.00 | 96.88

###  A.3 Runtimes of FPT algorithms.

Table 7 and Table 8. Each of the row statistics is on the instances on which
_GFPT_ or _GFPT-NI_ terminated in 4 hours (see Table 6 for completion rate).

Table 7: Average runtime (in seconds) of _GFPT_ , _CFPT_ , and _MFPT_. Fifth and sixth columns show geometric mean of ratios of runtime of _GFPT_ to runtime of _CFPT_ and _MFPT_ respectively. Graph | Average Runtime (seconds) | Geometric mean of ratios of runtimes
---|---|---
_GFPT_ | _CFPT_ | _MFPT_ | _CFPT_ | _MFPT_
er_150_0100 | 3123.58 | 8.62 | 7.90 | 459.80 | 404.41
er_150_0102 | 3545.24 | 8.98 | 22.11 | 496.08 | 316.72
er_150_0104 | 2939.30 | 12.56 | 5.21 | 157.78 | 370.58
er_150_0106 | 4121.85 | 23.70 | 22.75 | 461.25 | 408.18
er_150_0108 | 4071.08 | 2.64 | 9.97 | 1267.09 | 567.08
er_150_0110 | 4117.19 | 0.61 | 7.14 | 4814.52 | 519.39
er_250_0070 | 2570.21 | 13.66 | 4.59 | 379.88 | 539.54
er_260_0070 | 3190.58 | 2.14 | 3.45 | 1323.85 | 547.84
er_270_0070 | 3724.74 | 5.06 | 9.04 | 500.22 | 304.70
er_280_0070 | 2001.80 | 8.56 | 11.10 | 438.50 | 240.49
er_290_0070 | 3327.44 | 13.34 | 26.33 | 496.22 | 249.87
er_300_0070 | 3921.95 | 2.21 | 9.98 | 3395.05 | 408.77
er_200_009 | 4437.79 | 6.24 | 12.18 | 1458.80 | 406.40
er_500_005 | 4425.95 | 1.99 | 7.39 | 1501.51 | 645.31
er_750_0040 | 5227.85 | 1.82 | 5.18 | 2376.71 | 877.33
er_1000_0035 | 3405.49 | 2.80 | 6.20 | 906.00 | 452.02
Table 8: Average runtime (in seconds) of _GFPT-NI_ , _CFPT_ , and _MFPT_.
Fifth and sixth columns show geometric mean of ratios of runtime of _GFPT-NI_
to runtime of _CFPT_ and _MFPT_ respectively.

Graph | Average Runtime (seconds) | Geometric mean of ratios of runtimes
---|---|---
_GFPT-NI_ | _CFPT_ | _MFPT_ | _CFPT_ | _MFPT_
er_150_0100 | 1682.99 | 13.58 | 21.01 | 136.23 | 97.15
er_150_0102 | 3199.13 | 45.69 | 44.96 | 113.52 | 92.12
er_150_0104 | 3280.49 | 233.21 | 52.09 | 72.80 | 105.75
er_150_0106 | 2280.25 | 35.05 | 21.77 | 136.50 | 129.77
er_150_0108 | 2570.26 | 12.97 | 20.85 | 338.74 | 166.53
er_150_0110 | 4312.95 | 54.09 | 66.32 | 694.26 | 96.58
er_250_0070 | 1587.49 | 13.40 | 8.62 | 98.75 | 113.62
er_260_0070 | 3801.74 | 39.39 | 16.39 | 322.02 | 170.75
er_270_0070 | 3325.30 | 8.21 | 22.35 | 243.79 | 128.06
er_280_0070 | 523.17 | 8.52 | 10.85 | 87.87 | 50.40
er_290_0070 | 2148.48 | 13.09 | 34.77 | 188.97 | 64.34
er_300_0070 | 1466.10 | 2.14 | 15.53 | 724.81 | 74.41
er_200_009 | 3086.79 | 16.72 | 18.90 | 468.59 | 123.09
er_500_005 | 3283.63 | 3.67 | 14.74 | 493.49 | 172.50
er_750_0040 | 2581.47 | 3.48 | 43.97 | 544.25 | 123.23
er_1000_0035 | 2324.95 | 4.03 | 18.02 | 298.09 | 81.38

###  A.4 Dataset for the analysis of Section 6.2.

Table 17 provides mappings of brain networks listed in Table 9 to their
original names in networkrepository.com.

Table 9: Dataset of real-world graphs. First 21 graphs are brain networks, middle 3 graphs are gene regulatory networks, and last 6 graphs are social networks. Graph |  $n$ 333Isolated vertices are not counted. | $m$ | $d$ |  $\Delta$ |  Trivial Cliques
---|---|---|---|---|---
Brain-1 | 177,584 | 15,669,037 | 386 | 5,419 | 12,051
Brain-2 | 763,149 | 40,258,003 | 308 | 3,951 | 5,928
Brain-3 | 737,579 | 50,037,313 | 523 | 5,233 | 5,418
Brain-4 | 835,832 | 59,548,327 | 460 | 4,614 | 4,508
Brain-5 | 851,113 | 67,658,067 | 483 | 7,272 | 3,985
Brain-6 | 428,842 | 79,114,771 | 605 | 7,793 | 4,987
Brain-7 | 935,265 | 87,273,967 | 367 | 9,475 | 1,611
Brain-8 | 924,284 | 94,370,886 | 414 | 8,135 | 1,778
Brain-9 | 701,145 | 103,134,404 | 600 | 11,205 | 5,965
Brain-10 | 714,571 | 112,519,748 | 561 | 6,686 | 5,639
Brain-11 | 791,219 | 121,907,663 | 767 | 4,841 | 4,754
Brain-12 | 742,862 | 131,926,773 | 754 | 7,685 | 6,073
Brain-13 | 692,397 | 140,102,158 | 888 | 8,811 | 5,355
Brain-14 | 727,487 | 150,443,553 | 1,054 | 7,889 | 5,648
Brain-15 | 748,521 | 159,835,566 | 1,807 | 11,354 | 5,868
Brain-16 | 728,874 | 171,231,873 | 806 | 9,679 | 4,448
Brain-17 | 774,886 | 181,569,095 | 1,040 | 15,687 | 3,745
Brain-18 | 707,284 | 191,224,983 | 964 | 8,638 | 2,930
Brain-19 | 776,644 | 201,198,184 | 960 | 10,129 | 3,963
Brain-20 | 753,905 | 209,976,387 | 1,522 | 14,033 | 4,353
Brain-21 | 784,262 | 267,844,669 | 1,200 | 21,743 | 3,672
human_gene1 | 21,890 | 12,323,680 | 2,047 | 7,938 | 945
human_gene2 | 14,022 | 9,027,024 | 1,902 | 7,228 | 326
mouse_gene | 43,126 | 14,461,095 | 1,045 | 8,031 | 5,551
com-DBLP | 317,080 | 1,049,866 | 113 | 343 | 73,142
com-Amazon | 334,863 | 925,872 | 6 | 549 | 211,212
com-Youtube | 1,134,890 | 2,987,624 | 51 | 28,754 | 1,590,346
com-LiveJournal | 3,997,962 | 34,681,189 | 360 | 14,815 | 5,809,704
com-Orkut | 3,072,441 | 117,185,083 | 253 | 33,313 | 15,988,540
com-Friendster | 65,608,366 | 1,806,067,135 | 304 | 5,214 | 361,040,101

###  A.5 Comparison Results of Greedy Algorithms.

Table 10 and Table 11 show show comparisons of _clique cover_ sizes and
runtimes of our greedy algorithms against _g-ALG_. Table 12 and Table 13 show
comparisons of _clique cover_ sizes and runtimes of our greedy algorithms
against _c-ALG_.

Table 10: Clique cover size $|\mathcal{C}|$ of _g-ALG_ and relative reduction of clique cover size of _CCSG_ and _CCSD_ (relative to _g-ALG_) for the test graphs shown in Table 9. Out of 30 instances of Table 9, g-ALG terminated only on 13 instances within 24 hours. Graph | m | $|\mathcal{C}|$ | Relative Reduction
---|---|---|---
_g-ALG_ | _CCSG_ | _CCSD_
Brain-1 | 15,669,037 | 1,271,237 | 3.63 | 0.53
Brain-2 | 40,258,003 | 1,356,286 | 33.74 | 38.84
Brain-3 | 50,037,313 | 1,373,963 | 35.70 | 40.10
Brain-4 | 59,548,327 | 1,629,884 | 35.23 | 40.53
Brain-5 | 67,658,067 | 1,704,729 | 36.08 | 41.43
Brain-7 | 87,273,967 | 2,062,624 | 36.07 | 41.82
Brain-8 | 94,370,886 | 2,098,627 | 36.12 | 41.85
Brain-9 | 103,134,404 | 1,801,620 | 44.16 | 48.24
Brain-10 | 112,519,748 | 1,915,655 | 45.08 | 49.08
Brain-11 | 121,907,663 | 2,133,026 | 44.49 | 48.61
com_DBLP | 1,049,866 | 238,870 | 0.76 | 0.70
com_Amazon | 925,872 | 447,488 | 0.50 | 0.61
com_Youtube | 2,987,624 | 2,191,576 | 1.20 | -0.39
Average relative reduction | 27.14 | 30.15
Table 11: Runtimes of _g-ALG_ and relative performances of _CCSG_ and _CCSD_ (relative to g-ALG) on the test graphs of Table 9. Out of 30 instances of Table 9, g-ALG terminated only on 13 instances within 24 hours. Graph | m | Time (seconds) | Relative Performance
---|---|---|---
_g_ALG_ | _CCSG_ | _CCSD_
Brain-1 | 15669037 | 79,834.90 | 848.53 | 936.25
Brain-2 | 40258003 | 2,930.59 | 45.91 | 56.51
Brain-3 | 50,037,313 | 11,065.80 | 123.33 | 151.51
Brain-4 | 59,548,327 | 11,097.10 | 100.28 | 124.69
Brain-5 | 67,658,067 | 12,319.00 | 92.76 | 113.82
Brain-7 | 87,273,967 | 12,987.80 | 69.92 | 89.67
Brain-8 | 94,370,886 | 16,010.10 | 75.78 | 95.30
Brain-9 | 103,134,404 | 55,937.60 | 194.45 | 249.38
Brain-10 | 112,519,748 | 53,891.40 | 175.69 | 224.94
Brain-11 | 121,907,663 | 53,756.10 | 161.83 | 206.78
com_DBLP | 1,049,866 | 1.83 | 2.27 | 2.07
com_Amazon | 925,872 | 2.02 | 1.79 | 1.76
com_Youtube | 2,987,624 | 7,150.57 | 1068.57 | 1073.20
Geometric mean of relative performances | 80.22 | 93.91
Table 12: _Clique cover_ size $|\mathcal{C}|$ of _c-ALG_ and relative reduction of _clique cover_ size of _CCSG_ and _CCSD_ (relative to _c-ALG_) for the test graphs shown in Table 9. For com_Friendster, _c-ALG_ did not terminate in 24 hours, in the meantime included more than 942.57 million cliques in the _clique cover_ Graph | $m$ | $|\mathcal{C}|$ | Relative Reduction
---|---|---|---
_c-ALG_ | _CCSG_ | _CCSD_
Brain-1 | 15,669,037 | 1,422,541 | 13.97 | 11.20
Brain-2 | 40,258,003 | 1,019,877 | 11.76 | 18.54
Brain-3 | 50,037,313 | 1,009,000 | 12.32 | 18.32
Brain-4 | 59,548,327 | 1,195,909 | 11.64 | 18.87
Brain-5 | 67,658,067 | 1,230,938 | 11.40 | 18.81
Brain-6 | 79,114,771 | 2,648,702 | 12.95 | 13.92
Brain-7 | 87,273,967 | 1,480,951 | 10.94 | 18.94
Brain-8 | 94,370,886 | 1,504,777 | 10.88 | 18.87
Brain-9 | 103,134,404 | 1,187,423 | 15.13 | 21.34
Brain-10 | 112,519,748 | 1,253,065 | 15.91 | 22.03
Brain-11 | 121,907,663 | 1,393,330 | 14.91 | 21.24
Brain-12 | 131,926,773 | 1,309,727 | 16.51 | 22.09
Brain-13 | 140,102,158 | 1,280,755 | 16.73 | 22.21
Brain-14 | 150,443,553 | 1,328,541 | 16.89 | 22.19
Brain-15 | 159,835,566 | 1,384,057 | 16.74 | 22.31
Brain-16 | 171,231,873 | 1,447,271 | 16.63 | 22.40
Brain-17 | 181,569,095 | 1,555,077 | 15.67 | 22.61
Brain-18 | 191,224,983 | 1,490,147 | 16.64 | 23.04
Brain-19 | 201,198,184 | 1,585,659 | 17.11 | 22.94
Brain-20 | 209,976,387 | 1,553,300 | 16.38 | 22.87
Brain-21 | 267,844,669 | 2,827,079 | 17.47 | 20.80
human_gene1 | 12,323,680 | 177,210 | 20.38 | 13.65
human_gene2 | 9,027,024 | 114,916 | 19.48 | 12.79
mouse_gene | 14,461,095 | 479,361 | 19.00 | 12.09
com-DBLP | 1,049,866 | 238,573 | 0.58 | 0.52
com-Amazon | 925,872 | 448,157 | 0.79 | 0.89
com-Youtube | 2,987,624 | 2,202,876 | 3.02 | 1.46
com-LiveJournal | 34,681,189 | 14,137,013 | 4.11 | 3.23
com-Orkut | 117,185,083 | 45,361,490 | 5.49 | 4.17
Average relative reduction | 13.15 | 16.36
|  | Number of cliques (million)
com-Friendster | 1,806,067,135 | >942.57 | 919.20 | 922.49
Table 13: Runtimes of _c-ALG_ and relative performances of _CCSG_ and _CCSD_ (relative to c-ALG) on the test graphs of Table 9. Graph | m | Time (seconds) | Relative Performance
---|---|---|---
_c-ALG_ | _CCSG_ | _CCSD_
Brain-1 | 15,669,037 | 169.53 | 1.80 | 1.99
Brain-2 | 40,258,003 | 170.81 | 2.68 | 3.29
Brain-3 | 50,037,313 | 226.00 | 2.52 | 3.09
Brain-4 | 59,548,327 | 321.15 | 2.90 | 3.61
Brain-5 | 67,658,067 | 338.52 | 2.55 | 3.13
Brain-6 | 79,114,771 | 862.73 | 1.88 | 2.10
Brain-7 | 87,273,967 | 481.30 | 2.59 | 3.32
Brain-8 | 94,370,886 | 557.21 | 2.64 | 3.32
Brain-9 | 103,134,404 | 653.28 | 2.27 | 2.91
Brain-10 | 112,519,748 | 701.67 | 2.29 | 2.93
Brain-11 | 121,907,663 | 795.12 | 2.39 | 3.06
Brain-12 | 131,926,773 | 1065.05 | 2.71 | 3.45
Brain-13 | 140,102,158 | 1059.41 | 2.45 | 3.08
Brain-14 | 150,443,553 | 1261.73 | 2.72 | 3.31
Brain-15 | 159,835,566 | 1478.49 | 2.91 | 3.58
Brain-16 | 171,231,873 | 1517.51 | 2.75 | 3.35
Brain-17 | 181,569,095 | 1511.06 | 2.41 | 3.02
Brain-18 | 191,224,983 | 1767.84 | 2.77 | 3.49
Brain-19 | 201,198,184 | 1968.44 | 3.06 | 3.82
Brain-20 | 209,976,387 | 1974.25 | 2.60 | 3.20
Brain-21 | 267,844,669 | 2996.41 | 2.30 | 2.82
human_gene1 | 12,323,680 | 494.86 | 1.84 | 1.70
human_gene2 | 9,027,024 | 352.61 | 1.80 | 1.72
mouse_gene | 14,461,095 | 260.90 | 1.95 | 2.00
com_DBLP | 1,049,866 | 2.58 | 3.21 | 2.92
com_Amazon | 925,872 | 3.50 | 3.11 | 3.05
com_Youtube | 2,987,624 | 16.53 | 2.47 | 2.48
com_LiveJournal | 34,681,189 | 194.50 | 3.02 | 3.04
com_Orkut | 117,185,083 | 1150.58 | 3.11 | 3.33
Geometric Mean of relative performances | 2.51 | 2.91
|  | Time (hour)
com_Friendster | 1,806,067,135 | >24 | 2.57 | 2.26

###  A.6 Comparison results of _CCSG_ and FPT algorithms.

Table 14 show comparison results of _CCSG_ and _MFPT_ , and Table 15 show
comparison results of _CCSG_ and _CFPT_.

Table 14: Average _clique cover_ size $|\mathcal{C}|$ and runtime of _CCGS_ and _MFPT_ on the graph ensembles of Table 5. Second last column shows geometric mean of ratios of _clique cover_ size of _CCSG_ to _clique cover_ size of _MFPT_. Last column shows geometric mean of ratios of runtime of _MFPT_ to runtime of _CCSG_. Graph |  $|\mathcal{C}|$ (average) | Runtime (average) | Geo. mean of ratios | Geo. mean of ratios
---|---|---|---|---
_CCSG_ | _MFPT_ | _CCSG_ | _MFPT_ | of clique cover size | of runtime
er_150_0100 | 622.03 | 611.41 | 0.001 | 354.19 | 1.017 | 30,800.67
er_150_0102 | 625.03 | 613.66 | 0.001 | 569.32 | 1.018 | 46,283.01
er_150_0104 | 627.03 | 615.65 | 0.001 | 319.25 | 1.018 | 30,700.69
er_150_0106 | 625.74 | 613.55 | 0.001 | 1,037.81 | 1.020 | 40,508.13
er_150_0108 | 629.94 | 617.72 | 0.001 | 706.91 | 1.020 | 52,906.64
er_150_0110 | 640.88 | 627.53 | 0.001 | 884.55 | 1.021 | 187,999.12
er_250_0070 | 1,312.32 | 1,295.90 | 0.002 | 218.06 | 1.013 | 10,727.51
er_260_0070 | 1,401.39 | 1,383.90 | 0.002 | 763.76 | 1.013 | 16,957.37
er_270_0070 | 1,495.16 | 1,476.22 | 0.002 | 393.62 | 1.013 | 27,719.52
er_280_0070 | 1,580.63 | 1,555.97 | 0.002 | 1,503.47 | 1.016 | 35,949.35
er_290_0070 | 1,677.81 | 1,651.78 | 0.002 | 377.25 | 1.016 | 32,558.44
er_300_0070 | 1,775.19 | 1,748.48 | 0.002 | 707.30 | 1.015 | 27,660.49
er_200_009 | 973.03 | 955.81 | 0.001 | 126.28 | 1.018 | 21,467.68
er_500_005 | 3,732.63 | 3,685.84 | 0.005 | 1,213.04 | 1.013 | 13,188.51
er_750_0040 | 6,822.45 | 6,738.94 | 0.009 | 786.22 | 1.012 | 5,692.55
er_1000_0035 | 10,551.19 | 10,417.03 | 0.015 | 708.18 | 1.013 | 2,426.77
Table 15: Average _clique cover_ size $|\mathcal{C}|$ and runtime of _CCGS_ and _CFPT_ on the graph ensembles of Table 5. Second last column shows geometric mean of ratios of _clique cover_ size of _CCSG_ to _clique cover_ size of _CFPT_. Last column shows geometric mean of ratios of runtime of _CFPT_ to runtime of _CCSG_. Graph |  $|\mathcal{C}|$ (average) | Runtime (average) | Geo. mean of ratios | Geo. mean of ratios
---|---|---|---|---
_CCSG_ | _CFPT_ | _CCSG_ | _CFPT_ | of clique cover size | of runtime
er_150_0100 | 622.03 | 611.32 | 0.001 | 214.37 | 1.018 | 19,290.66
er_150_0102 | 625.03 | 613.66 | 0.001 | 114.41 | 1.019 | 20,203.29
er_150_0104 | 626.77 | 615.47 | 0.001 | 475.88 | 1.018 | 31,971.71
er_150_0106 | 625.80 | 613.87 | 0.001 | 190.10 | 1.019 | 27,537.44
er_150_0108 | 629.94 | 617.72 | 0.001 | 427.45 | 1.020 | 27,949.53
er_150_0110 | 640.42 | 627.10 | 0.001 | 295.32 | 1.021 | 40,520.17
er_250_0070 | 1,312.97 | 1,296.38 | 0.002 | 248.23 | 1.013 | 7,433.56
er_260_0070 | 1,401.78 | 1,384.13 | 0.002 | 407.72 | 1.013 | 6,065.27
er_270_0070 | 1,495.16 | 1,476.22 | 0.002 | 154.87 | 1.013 | 7,374.01
er_280_0070 | 1,580.63 | 1,555.97 | 0.002 | 252.40 | 1.016 | 8,149.40
er_290_0070 | 1,677.81 | 1,651.78 | 0.002 | 68.65 | 1.016 | 5,138.18
er_300_0070 | 1,775.09 | 1,748.44 | 0.002 | 306.79 | 1.015 | 4,740.27
er_200_009 | 973.75 | 956.25 | 0.001 | 78.18 | 1.018 | 8,253.58
er_500_005 | 3,732.63 | 3,685.84 | 0.005 | 26.11 | 1.013 | 5,397.34
er_750_0040 | 6,823.72 | 6,740.56 | 0.009 | 63.14 | 1.012 | 921.63
er_1000_0035 | 10,547.88 | 10,414.22 | 0.015 | 49.08 | 1.013 | 379.11

###  A.7 _MFPT_ based on different maximal clique enumeration algorithms.

For maximal clique enumeration, [34] used a variant of _Bron-Kerbosch_
algorithm [7] proposed by [44]. We evaluated _MFPT_ with three different
_Bron-Kerbosch_ based algorithms: [44] (_Koch_), [67] (_TTT_), [22] (_ELS_)
and found that implementation of _MFPT_ based on _ELS_ performs better than
implementations based on _Koch_ and _TTT_. Our implementation of _ELS_ is
comparable to _ELS-bare_ [23], and our implementations of _Koch_ and _TTT_ are
comparable to _TTT-lists_ [23]. Table 16 shows the comparison results of
different implementations of _MFPT_. Three of our tested algorithms (_MFPT_ ,
_GFPT_ , and _GFPT-NI_) are based on maximal clique enumeration, and for all
three algorithms, we have used _ELS_.

Table 16: Average runtime (in seconds) of _MFPT_ using different maximal clique enumeration algorithms: _Koch_ [44], _TTT_ [67], and _ELS_ [23]. Graph | Average runtime (second) of MFPT
---|---
Koch | TTT | ELS
er_150_0100 | 399.74 | 394.22 | 354.19
er_150_0102 | 649.06 | 629.29 | 569.32
er_150_0104 | 347.66 | 345.65 | 319.25
er_150_0106 | 663.60 | 661.24 | 612.69
er_150_0108 | 783.42 | 781.28 | 706.91
er_150_0110 | 966.23 | 963.55 | 884.55
er_250_0070 | 236.07 | 232.80 | 218.06
er_260_0070 | 844.45 | 840.69 | 763.76
er_270_0070 | 426.90 | 415.12 | 393.62
er_280_0070 | 1659.90 | 1620.85 | 1503.47
er_290_0070 | 407.90 | 405.58 | 377.25
er_300_0070 | 788.59 | 772.98 | 707.30
er_200_009 | 140.98 | 138.34 | 126.28
er_500_005 | 1338.58 | 1330.68 | 1213.04
er_750_0040 | 413.96 | 408.33 | 379.77
er_1000_0035 | 764.38 | 741.85 | 708.18

###  A.8 Brain Networks.

Table 17.

Table 17: Mappings of names of the brain networks shown in Table 9 to their original names in networkrepository.com [66] Graph | Brain Network Name
---|---
Brain-1 | bn-human-BNU_1_0025890_session_1
Brain-2 | bn-human-Jung2015_M87125334
Brain-3 | bn-human-Jung2015_M87104509
Brain-4 | bn-human-Jung2015_M87119472
Brain-5 | bn-human-Jung2015_M87104300
Brain-6 | bn-human-Jung2015_M87118347
Brain-7 | bn-human-Jung2015_M87102575
Brain-8 | bn-human-Jung2015_M87122310
Brain-9 | bn-human-BNU_1_0025914_session_2
Brain-10 | bn-human-BNU_1_0025916_session_1
Brain-11 | bn-human-Jung2015_M87118219
Brain-12 | bn-human-BNU_1_0025889_session_2
Brain-13 | bn-human-BNU_1_0025873_session_2-bg
Brain-14 | bn-human-BNU_1_0025868_session_1-bg
Brain-15 | bn-human-BNU_1_0025918_session_1
Brain-16 | bn-human-Jung2015_M87112427
Brain-17 | bn-human-Jung2015_M87118465
Brain-18 | bn-human-Jung2015_M87104201
Brain-19 | bn-human-Jung2015_M87101705
Brain-20 | bn-human-Jung2015_M87125286
Brain-21 | bn-human-Jung2015_M87113878