# Computing Clique Cover with Structural Parameterization

Ahammed Ullah Purdue University

An abundance of real-world problems manifest as covering edges and/or vertices
of a graph with cliques that are optimized for some objectives. We consider
different structural parameters of graph, and design fixed-parameter tractable
algorithms for a number of clique cover problems. Using a set representation
of graph, we introduce a framework for computing clique cover with different
objectives. We demonstrate use of the framework for a variety of clique cover
problems. Our results include a number of new algorithms with exponential to
double exponential improvements in the running time.

##  1 Introduction

A set of cliques is an edge (resp. vertex) clique cover of a
graph111Throughout the paper we assume graphs are finite, undirected, and
simple, i.e., contains no self-loop and parallel edges. if every edge (resp.
vertex) is contained in at least one of the cliques in the set. In a clique
cover problem, we seek to compute a clique cover that is optimized for some
objectives such as minimizing number of cliques in the cover. The clique cover
problems we are pursuing in this study are _NP-hard_ , and inapproximable
within any constant factor unless $P=NP$. For applications of clique cover
problems, see [1, 2, 7, 14, 17, 23, 26, 30, 33, 37, 38, 39, 43].

One of the ways of tackling intractability of _NP-hard_ problems is to study
the problems through the lens of parameterized complexity [8, 13, 19]. In
parameterized complexity222See Section 2.3 for a brief introduction of
relevant terms., a problem is called fixed-parameter tractable (FPT) with
respect to a parameter $p$ if problem instance of size $n$ can be solved in
$f(p)n^{O(1)}$ time, where $f(p)$ is computable and independent of $n$, but
can grow arbitrarily with $p$. In terms of applicability, the hope is that for
small values of parameter an FPT problem would be solvable in a reasonable
amount of time.

###  1.1 Motivations

A number of clique cover problems have been shown to be FPT with respect to
the number of cliques in a solution [7, 17, 22]. These FPT running times have
super exponential dependence on the number of cliques, making them unlikely to
be useful for graphs which are not sufficiently dense. For example, deciding
whether edges of a graph can be covered with at most $k$ cliques is solvable
in $2^{2^{O(k)}}n^{O(1)}$ time [22]. The double exponential dependence on $k$
is necessary, assuming the exponential time hypothesis [10]. We ask to what
extent super exponential dependence on $k$ arises, and whether structural
parameters of graph can be used to tame dependence on $k$.

Known frameworks of computing clique covers are based on enumeration of binary
matrices of dimension $O(k)\times O(k)$ [7, 17] ($k$ is the number of cliques
in a solution), or enumeration of maximal cliques of different subgraphs [14,
22]. Clearly, enumeration of binary matrices of dimension $O(k)\times O(k)$
disregards any sparsity measures of graph. Also, time and space complexities
of algorithm designed using maximal clique enumeration may have prohibitively
large dependence on input size. For example, [14] have described an algorithm
for the problem of covering the edges of a graph with cliques such that the
number of individual assignments of vertices to the cliques is minimum. For a
graph with $n$ vertices, the algorithm of [14] takes $2^{2^{O(n)}}$ time and
$2^{O(n)}$ space. We investigate amenability of different frameworks for
designing better algorithms that also take sparsity of graph into account.

Many clique cover problems are unlikely to be FPT with respect to certain
choices of parameters. For example, covering vertices of a graph with at most
$k$ cliques is not FPT with respect to $k$ unless $P=NP$. We investigate
whether structural parameters of graph would be helpful for designing FPT
algorithms for these problems (and corresponding graph coloring problems).

###  1.2 Problems

We describe the clique cover problems we have studied in this paper.

Covering the edges of a graph with at most $k$ cliques is an _NP-complete_
problem [30, 36]. The problem has many applications [39], and appears in
different guises such as keyword conflict [30], intersection graph basis [21],
indeterminate string [26]. For ease of reference, the problem is outlined as
follows.

_Edge Clique Cover_ (_ECC_) Input: A graph $G=(V,E)$, and a nonnegative
integer $k$. Output: If one 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_.

Motivated by applications from applied statistics [23, 37], [14] have studied
the _assignment-minimum clique cover_ problem that seeks to cover edges of a
graph with cliques such that the number of individual assignments of vertices
to cliques is minimum. [14] have demonstrated that minimizing number of
cliques and number of individual assignments of vertices simultaneously is not
always possible. Therefore, number of cliques is not an appropriate choice for
_natural parameterization_ of the problem. We introduce the following
parameterized problem for _assignment-minimum clique cover_.

_Assignment Clique Cover_ (_ACC_) Input: A graph $G=(V,E)$, and a nonnegative
integer $t$. Output: If one exists, a clique cover $\mathcal{C}$ of $G$ such
that (1) every edge of $G$ is contained in at least one of the cliques in
$\mathcal{C}$, and (2) $\sum_{C_{l}\in\mathcal{C}}|C_{l}|\leq t$; otherwise
_NO_.

[17] have introduced the following parameterized clique cover problem.

_Weighted Edge Clique Partition_ (_WECP_) Input: A graph $G=(V,E)$, a weight
function $w:E\rightarrow\mathbb{Z}_{>0}$, and a nonnegative integer $k$.
Output: If one exists, a clique cover $\mathcal{C}$ of $G$ such that (1)
$|\mathcal{C}|\leq k$, and (2) each edge $e\in E$ appears in exactly $w(e)$
cliques of $\mathcal{C}$; otherwise _NO_.

Motivated by applications from identification of gene co-expression modules,
[7] have introduced a generalization of _WECP_ problem as follows.

_Exact Weighted Clique Decomposition_ (_EWCD_) Input: A graph $G=(V,E)$, a
weight function $w:E\rightarrow\mathbb{R}_{>0}$, and a nonnegative integer
$k$. Output: If one exists, a clique cover $\mathcal{C}$ of $G$ and
$\gamma_{i}\in\mathbb{R}_{>0}$ for all $C_{i}\in\mathcal{C}$ such that (1)
$|\mathcal{C}|\leq k$, (2) and for each edge $e=\\{u,v\\}\in E$,
$\sum_{\\{u,v\\}\in C_{i}}\gamma_{i}=w(e)$; otherwise _NO_.

The _vertex clique cover_ problem (abbreviated _VCC_) is the problem of
deciding whether vertices of a graph can be covered (or partitioned) using at
most $k$ cliques. _VCC_ is _NP-complete_ [28]. In parameterized complexity,
many variants of the _NP-complete_ problems from [28] had been extensively
studied such as _vertex cover_ [24], _graph coloring_ [18, 27]. _VCC_ in this
regard had been totally unexplored. We introduce following generalization of
_VCC_.

_Link Respected Clique Cover_ (_LRCC_) Input: A graph $G=(V,E)$, a nonnegative
integer $k$, and a set of edges $E^{*}\subseteq E$. Output: If one exists, a
set of cliques $\mathcal{C}$ of $G$ such that (1) $|\mathcal{C}|\leq k$, (2)
every vertex of $G$ is contained in at least one of the cliques in
$\mathcal{C}$, (3) and every edge $\\{x,y\\}\in E^{*}$ is contained in at
least one of the cliques in $\mathcal{C}$; otherwise _NO_.

_LRCC_ can be seen as the problem of covering vertices of a network with $k$
communities such that certain set of links (edges) are preserved in the cover.
Note that if $E^{*}=E$, then _LRCC_ is equivalent to _ECC_. On the other hand,
if $E^{*}=\varnothing$, then _LRCC_ reduces to _VCC_.

_Colorability_ is the problem of coloring vertices of a graph such that each
pair of adjacent vertices receive difference colors. _VCC_ is equivalent to
_Colorability_ in the complement graph. The following problem is equivalent to
_LRCC_ in the complement graph.

_Pairwise Mutual Colorability_ (_PMC_) Input: A graph $G=(V,E)$, a nonnegative
integer $k$, and a set of pairs of non-adjacent vertices $\mathcal{F}$.
Output: If exist, assignments of at most $k$ colors to the vertices of $G$
such that (1) each vertex receive at least one color, (2) no pair of adjacent
vertices share any color, and (3) each pair of vertices
$\\{x,y\\}\in\mathcal{F}$ share at least one color; otherwise _NO_.

_PMC_ captures formulation of a scheduling problem where each pair of adjacent
vertices are in conflict, and we want a conflict free assignments of vertices
into $k$ slots such that each pair of vertices in $\mathcal{F}$ has at least
one common slot. If $\mathcal{F}=\varnothing$, then _PMC_ reduces to
_Colorability_.

From the structural parameters333See Section 2.2 for a brief description of
different parameters and their relationships. that capture graph sparsity, we
focus on _degeneracy_ and _clique number_ of graph. Many structural parameters
(such as _arboricity_ , _thickness_ , _treewidth_ , _vertex cover number_) are
either within constant factors of or upper bounds on our chosen structural
parameters. Therefore, our algorithms are also FPT with respect to many
structural parameters that we do not explicitly focus on.

###  1.3 Our Results

For a graph $G=(V,E)$, let $n=|V|$ denote number of vertices, $m=|E|$ denote
number of edges, $d$ denote the _degeneracy_ , $\beta$ denote the _clique
number_ , and $\alpha$ denote the _independence number_.

Our results are obtained from two different algorithmic frameworks: one
described in Section 3 (denoted _Framework-1_), and the other described in
Section 4 and Section 5 (denoted _Framework-2_).

Using _Framework-1_ , we obtain the following result for _ECC_.

######  Theorem 1.1.

_ECC_ parameterized by $d$ and $k$ has an FPT algorithm running in
$1.4423^{dk}n^{O(1)}$ time.

With kernelization, we achieve a factor of $2^{\Omega(\alpha^{2})}$ times
faster algorithm than the algorithm of [22]. For $\alpha=\Omega(n)$, the
improvement in the running time amounts to a factor of $2^{2^{O(k)}}$. We
point out that the factor of $2^{\Omega(\alpha^{2})}$ improvement in the
running time is irrespective of graph density, i.e., the algorithm of Theorem
1.1 is faster than the algorithm of [22] regardless of whether the
_degeneracy_ of input graph is bounded or not.

Using _Framework-2_ , we obtain the following result for _ECC_.

######  Theorem 1.2.

_ECC_ parameterized by $\beta$ and $k$ has an FPT algorithm running in
$2^{\beta k\log k}n^{O(1)}$ time.444Unless otherwise specified, base of
logarithms in this paper is two.

For $\beta=o(d/\log d)$, the algorithm of Theorem 1.2 is asymptotically faster
than the algorithm of Theorem 1.1 by a factor $2^{O(dk)}$. For many instances
of _ECC_ , $\beta=o(d/\log d)$ is a very mild requirement: $d$ can grow
linearly with the input size, while $\beta$ remains constant.

[14] have claimed that the _assignment-minimum clique cover_ is NP-hard; but
we have not found any proof of this claim in the literature. We fill this gap
by proving the following claim.

######  Theorem 1.3.

_ACC_ is _NP-complete_.

We describe two FPT algorithms for _ACC_ , one is obtained using _Framework-1_
, and the other is obtained using _Framework-2_. The following is our best FPT
running time for _ACC_ that we obtain using _Framework-2_.

######  Theorem 1.4.

_ACC_ has an FPT algorithm running in $4^{t\log t}n^{O(1)}$ time.

In contrast to $2^{2^{O(n)}}$ running time and $2^{O(n)}$ space complexity of
the algorithm described by [14], we obtain the following result from Theorem
1.4.

######  Corollary 1.5.

An _assignment-minimum clique cover_ of a graph $G$ can be computed in
$2^{O(m\log n)}$ time, using $O(mn)$ space.

Rest of our results are obtained using _Framework-2_. For _WECP_ , we have the
following result.

######  Theorem 1.6.

_WECP_ parameterized by $\beta$ and $k$ has an FPT algorithm running in
$2^{\beta k\log k}n^{O(1)}$ time.

For _WECP_ , [17] have described an FPT algorithm with
$2^{O(k^{3/2}w^{1/2}\log(k/w))}n^{O(1)}$ running time, where $w$ is the
maximum edge weight. For $\beta=o((\sqrt{kw}\log(k/w))/\log k)$, the algorithm
of Theorem 1.6 improves the running time by a factor of
$2^{O(k^{3/2}w^{1/2}\log(k/w))}$. This is a significant improvement,
considering the fact that $\beta$ is bounded by the graph size, while $k$ and
$w$ could be arbitrarily large. For nontrivial instances of _WECP_ , $k$ could
be up to (but not including) $mw$. On the other hand, if the maximum edge
weight $w$ is bounded by some constant, then for $\beta=o(\sqrt{k})$, the
algorithm of Theorem 1.6 is $2^{O(k^{3/2}\log k)}$ times faster than the
algorithm of [17].

For _EWCD_ , we have the following result.

######  Theorem 1.7.

_EWCD_ parameterized by $\beta$ and $k$ has an FPT algorithm running in
$2^{O(\beta k\log k)}n^{O(1)}L$ time, where $L$ is the number of bits required
for input representation555More precisely, $L$ is the number of bits required
to encode the input in a linear program (see (A))..

For _EWCD_ , [7] have described an FPT algorithm with running time
$O(4^{k^{2}}k^{2}(32^{k}+k^{3}L))$, where $L$ is the number of bits required
for input representation. For $\beta=o(k/\log k)$, the algorithm of Theorem
1.7 improves the running time by a factor of $2^{O(k^{2})}$. For the cases
when all weights are restricted to integers, [7] have described an algorithm
with running time $O(4^{k^{2}}32^{k}w^{k}k)$, where $w$ is the maximum edge
weight. For these cases, if $\beta=o(k/\log k)$, then an adaptation of the
algorithm of Theorem 1.7 also improves the running time by a factor of
$2^{O(k^{2})}$.

For _LRCC_ , we have the following result.

######  Theorem 1.8.

_LRCC_ parameterized by $\beta$ and $k$ has an FPT algorithm running in
$2^{\beta k\log k}n^{O(1)}$ time.

Through a _parameterized reduction_ , we obtain the following result from
Theorem 1.8.

######  Corollary 1.9.

_PMC_ parameterized by $\alpha$ and $k$ has an FPT algorithm running in
$2^{\alpha k\log k}n^{O(1)}$ time.

###  1.4 Overview of Our Techniques

Our algorithms are based on combination of data reduction rules and bounded
search tree algorithm. We use two different frameworks for designing bounded
search tree algorithms. We make sure that all of our search tree algorithms
are compatible with the existing data reduction rules (and conceivably with
many rules yet to be found). For an instance of _WECP_ (or _EWCD_),
_kernelization_ produces an instance of a more general problem. For these
cases, to make use of the _kernelization_ , we describe search tree algorithms
for the general problems.

Our first framework (Section 3) for search tree algorithms is based on
enumeration of cliques of subgraphs, introduced by [22]. With an edge
selection rule, [22] have attempted to bound the branching factors of a search
tree. But the rule itself does not lead to any provable bound on the branching
factors. As a result, the branching factors of a search tree of [22] is only
bounded by a function of $k$ that is double exponential in $k$ (obtained
through kernelization). We enumerate cliques of subgraphs such that the size
of each subgraph is bounded by a polynomial function of _degeneracy_. This
allows us to bound the branching factors of a search tree with a single
exponential function of _degeneracy_ (or other parameters).

We introduce a general way of computing clique cover based on two concepts
that we call _locally minimal clique cover_ and _implicit set representation_.
The concepts may be of independent interest, and we devote a fair amount of
exposition highlighting their characterizations and relationships (Section 4).
We use the concepts to demonstrate a general framework for designing search
tree algorithms for clique cover problems (Section 5).

The concept of _locally minimal clique cover_ is based on a relaxation of a
global minimality of clique cover. With this relaxation, systematic
exploration of clique covers of a graph becomes straightforward. Every graph
corresponds to some family of sets called _set representation_ of the graph
[35]. The union of the sets in a _set representation_ of a graph corresponds
to an _edge clique cover_ of the graph; but this correspondence does not
immediately lead to efficient construction of _edge clique cover_. _Implicit
set representation_ of a graph is a relaxation of _set representation_ of the
graph that helps efficient construction of _edge clique cover_ of a graph. The
two concepts, _locally minimal clique cover_ and _implicit set representation_
, nicely fit together, and give us a general way of computing clique cover
with different objectives.

###  1.5 Related Work

[22] have described the first FPT algorithm for _ECC_. The algorithm of [22]
is based on a kernel with $2^{k}$ vertices and a search tree algorithm that
takes $2^{2^{O(k)}}$ time. Unless the polynomial hierarchy collapses, no
polynomial kernel exists for _ECC_ [9]. The FPT running time of [22] is
essentially optimal with respect to $k$ [10]. [2] have described an FPT
algorithm for _ECC_ parameterized by _treewidth_ , and for planar graphs an
FPT algorithm for _ECC_ parameterized by _branchwidth_.

The algorithm of [14] is based on the observation that an _edge clique cover_
of a graph consisting of all maximal cliques of the graph must contain an
_assignment-minimum clique cover_ of the graph. The algorithm starts with all
maximal cliques of a graph, and enumerates all possible individual assignments
of vertices that can be removed, maintaining an _edge clique cover_. The
requirement of having (simultaneously) all maximal cliques of a graph with $n$
vertices results in $O(n3^{n/3})=2^{O(n)}$ space requirement, and enumeration
of the choices of removing individual assignments of vertices results in
$2^{2^{O(n)}}$ running time.

[17] have described an FPT algorithm with
$2^{O(k^{3/2}w^{1/2}\log(k/w))}n^{O(1)}$ running time, where $w$ is the
maximum edge weight. The FPT algorithm of [17] is based on a _bi-kernel_ with
$4^{k}$ vertices, and a search tree algorithm that enumerates matrices of
$\\{0,1\\}^{k\times k}$ such that the dot product of any pair of rows in a
matrix is bounded by $w$.

Using the _bi-kernel_ of [17] and a search tree algorithm that enumerates
matrices of $\\{0,1\\}^{2k\times k}$, [7] have described two FPT algorithms
for _EWCD_. For arbitrary positive weights, [7] have described a linear
program based search tree algorithm with running time
$O(4^{k^{2}}k^{2}(32^{k}+k^{3}L))$, where $L$ is the number of bits required
for input representation. For the cases when all weights are restricted to
integers, [7] have described an integer partitioning based algorithm with
running time $O(4^{k^{2}}32^{k}w^{k}k)$, where $w$ is the maximum edge weight.

In the literature, we have not found any study on parameterizations of _VCC_.
On the other hand, _Colorability_ parameterized by _treewidth_ is known to be
FPT [8, 19]. Preceding result is not useful for obtaining FPT algorithm for
_VCC_ , since no _parameterized reduction_ is known from any parameterization
of _VCC_ to _Colorability_ parameterized by _treewidth_. Similarly, no
_parameterized reduction_ is known from any parameterization of _VCC_ to other
parameterizations of _Colorability_ that are known to be FPT [27].

###  1.6 Paper Organization

In Section 2, we provide a brief description of relevant structural parameters
and parameterized complexity terms. In Section 3, we describe FPT algorithms
for _ECC_ , _ACC_ , and a proof of _NP-completeness_ of _ACC_. The building
blocks of our new framework are described in Section 4. In Section 5, using
our new framework, we describe a new set of algorithms for the problems listed
in Section 1.2. We conclude with a discussion on implementations and open
problems in Section 6.

##  2 Preliminaries

In this section, we describe relevant structural parameters and their
relationships. We also provide a brief description of the relevant terms from
parameterized complexity.

###  2.1 Notations

We describe commonly used notations used in the paper. Additional notations
are introduced throughout the paper where they are appropriate for
introduction.

For a vertex $x\in V$, let $N(x)=\\{y|\\{x,y\\}\in E\\}$ denote the
neighbourhood of $x$ in $G$, and let $N[x]=N(x)\cup\\{x\\}$ denote the closed
neighbourhood of $x$ in $G$. A vertex $x$ is called an isolated vertex if
$N(x)=\varnothing$. Let $\Delta$ denote the maximum degree of $G$, i.e.,
$\Delta=\max_{x\in V}|N(x)|$. If the end points of an edge $e\in E$ are $x$
and $y$, then we denote the edge $e$ by $\\{x,y\\}$: it would be clear from
the context whether $\\{x,y\\}$ denote an edge or an arbitrary pair of
vertices.

We call $H=(V_{H},E_{H})$ a subgraph of $G$ if $V_{H}\subseteq V$ and $E_{H}$
is a subset of edges of $E$ that have both end points in $V_{H}$. We call $H$
an induced subgraph of $G$ if $E_{H}$ is the set all edges of $E$ that have
both end points in $V_{H}$. If $H$ is an induced subgraph of $G$, then we say
$V_{H}$ induces the subgraph $H$ in $G$ and denote the subgraph by $G[V_{H}]$.

###  2.2 Structural Parameters

######  Definition 2.1 (Degeneracy [31]).

The _degeneracy_ of a graph $G$ is the smallest value $d$ such that every
nonempty subgraph of $G$ contains a vertex that has at most $d$ adjacent
vertices in the subgraph.

Following Definition 2.1, we can find a vertex with at most $d$ neighbours and
delete the vertex and its incident edges. Repeating this process on the
resulting subgraphs would lead to the empty graph. Therefore, in linear time
[34], we can compute a permutation of vertices of $V$ defined as follows.

######  Definition 2.2 (Degeneracy Ordering).

The _degeneracy ordering_ of a graph $G=(V,E)$ is an ordering of vertices in
$V$ such that each vertex has at most $d$ neighbours that come later in the
ordering.

The following two propositions ensue from the preceding definitions.

######  Proposition 2.3.

$d+1\leq n$

######  Proposition 2.4.

$m<nd$

From Proposition 2.4 and the fact that $\sum_{x\in V}|N(x)|=2m$, we get the
following result.

######  Corollary 2.5.

Average degree of $G$ is at most $2d$.

_Degeneracy_ is within a constant factors of many sparsity measures of graph
such as _arboricity_ [4] and _thickness_ [11]. _Degeneracy_ is also known as
the _d-core number_ [41], _width_ [20], _linkage_ [29], and is equivalent to
the _coloring number_ [16].

######  Definition 2.6 (Vertex cover number).

A set of vertices $S\subset V$ is called a _vertex cover_ of $G$ if for every
edge $\\{x,y\\}\in E$, $S$ contains at least one end point of $\\{x,y\\}$. The
_vertex cover number_ $\tau$ is the size of a smallest _vertex cover_ of $G$.

######  Definition 2.7 (Independence number).

A set of vertices $S\subset V$ is called an _independent set_ of $G$ if for
every pair of distinct vertices $\\{x,y\\}\in S$, $\\{x,y\\}\not\in E$. The
_independence number_ $\alpha$ is the size of a largest _independent set_ of
$G$.

######  Definition 2.8 (Treewidth [40]).

A tree decomposition of a graph $G=(V,E)$ is a pair $(T,\\{X_{t}\\}_{t\in
V_{T}})$ where $T$ is a tree whose node set is $V_{T}$ and each
$X_{t}\subseteq V$ such that following conditions hold: (1) $\cup_{t\in
V_{T}}X_{t}=V$, (2) for every edge $\\{x,y\\}\in E$ there exist $t\in V_{T}$
such that $\\{x,y\\}\in X_{t}$, (3) for each $x\in V$ the set of nodes
$\\{t\in V_{T}|x\in X_{t}\\}$ induces a connected subtree of $T$.

The width of a tree decomposition $(T,\\{X_{t}\\}_{t\in V_{T}})$ is
$\max_{t\in V_{T}}|X_{t}|-1$. The treewidth of a graph $G$ is the smallest
width of a tree decomposition over all tree decompositions of $G$.

A graph $G$ with _treewidth_ $k$ is also a subgraph of a _$k$ -tree_ (see
Definition 10.2.1 of [13]). _$k$ -trees_ are the chordal graphs all of whose
maximal cliques are the same size $k+1$. Since any chordal graph admits an
ordering of vertices such that a vertex $x$ and neighbours of $x$ that come
later in the ordering form a clique (also known as the _perfect elimination
ordering_), _degeneracy_ of $G$ is at most the _treewidth_ of the graph. Also,
_treewidth_ of a graph is at most the _vertex cover number_ of the graph [18].
Therefore, $d\leq\tau$. From the fact that if $S$ is a _vertex cover_ of a
graph, then $V\backslash S$ is an _independent set_ of the graph, we have
$\tau+\alpha=n$. Thus we have the following.

######  Proposition 2.9.

$d+\alpha\leq n$

######  Remark 2.10.

Degeneracy is a better measure of graph sparsity than many other parameters.
To see this, consider the bipartite graph $K_{1,n-1}$ whose _degeneracy_ is
$1$, but maximum degree is $n-1$. A popular measure of graph sparsity is
_treewidth_. A graph may have bounded _degeneracy_ , but arbitrarily large
_treewidth_ : from any graph $G$ with _treewidth_ $tw$, we can subdivide the
edges (replace edge $\\{x,y\\}$ of $G$ with two edges $\\{x,z\\}$ and
$\\{z,y\\}$) and obtain a graph whose _degeneracy_ is at most two, but whose
_treewidth_ remains $tw$. Even extremely sparse graphs can have large
_treewidth_ : the _degeneracy_ of an $n\times n$ gird graph is at most three,
whereas its _treewidth_ is $\sqrt{n}$.

######  Definition 2.11 (Clique number).

We call a set of vertices $C$ a clique of $G$ if $C$ induces a complete
subgraph in $G$. The _clique number_ $\beta$ of $G$ is the size of a largest
clique of $G$.

If degree of every vertex in a subgraph of $G$ is more than $d$ then it would
contradict Definition 2.1. Thus we have the following.

######  Proposition 2.12.

$\beta\leq d+1$.

######  Remark 2.13.

Unlike _degeneracy_ , computing the _clique number_ of a graph is an _NP-hard_
problem. But, _clique number_ may be a better parameter for bounding running
time of algorithm, if possible. To see this, consider complete bipartite graph
$K_{p,q}$, where $p+q=n$. _Degeneracy_ of $K_{p,q}$ is $\min\\{p,q\\}\leq
n/2$, but _clique number_ is only $2$.

The following bound on _degeneracy_ is easy to show (for a proof see Appendix
A).

######  Lemma 2.14.

If $G$ contains no isolated vertices, then $d+1\leq 2\sqrt{m}$.

######  Corollary 2.15.

If $G$ contains no isolated vertices, then $\beta\leq 2\sqrt{m}$.

If the number of cliques in a vertex clique cover of a graph $G$ is $k$, then
the _independence number_ of $G$ is always a lower bound on $k$. Assume $G$
contains no isolated vertices. Then, any edge clique cover of $G$ is also a
vertex clique cover of $G$. Thus we have the following.

######  Proposition 2.16.

Let $G$ be a graph with no isolated vertices. If
$\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ is an _edge clique cover_ of $G$,
then $\alpha\leq k$.

Throughout the paper we use the following notations. Let $\langle
u_{1},u_{2},\ldots,u_{n}\rangle$ be a degeneracy ordering of $V$. For each
$u_{i}\in V$, let $N_{d}(u_{i})$ denote the neighbours of $u_{i}$ in $G$ that
comes later in the degeneracy ordering, i.e.,
$N_{d}(u_{i})=N(u_{i})\cap\\{u_{i+1},\ldots,u_{n}\\}$. Let
$N_{d}[u_{i}]=N_{d}(u_{i})\cup\\{u_{i}\\}$. We define an ordering of edges
(abbreviated _DEP_ for _degeneracy edge permutation_) as follows.

######  Definition 2.17 (DEP).

Let $E_{d}(x)=\\{\\{x,y\\}|y\in N_{d}(x)\\}$, i.e., the set of edges incident
on $x$ from vertices that come after $x$ in the degeneracy ordering. Let
$\pi^{E^{*}}=\langle e_{1},e_{2},\ldots,e_{q}\rangle$ be a permutation of a
set of edges $E^{*}$. We say $\pi^{E}$ a _degeneracy edge permutation_ of $G$
if $\pi^{E}$ is a concatenation of permutations $\pi^{E_{d}(u_{i})}$ in
increasing values of $i$, i.e.,
$\pi^{E}=\langle\pi^{E_{d}(u_{1})},\pi^{E_{d}(u_{2})},\ldots,\pi^{E_{d}(u_{n-1})}\rangle$.

###  2.3 Parameterized Complexity

We provide a brief overview of fixed-parameter tractability, kernelization,
bounded search tree, and other relevant terms. For a comprehensive
description, see [8, 13, 19].

######  Definition 2.18 (Parameterized problem).

A parameterized problem is a language $L\subseteq\Sigma^{*}\times\mathbb{N}$,
where $\Sigma$ is a fixed and finite alphabet. For an instance
$(x,p)\in\Sigma^{*}\times\mathbb{N}$, $p$ is called the parameter.

######  Definition 2.19 (Fixed-parameter tractability).

A parameterized problem $L\subseteq\sum^{*}\times\mathbb{N}$ is called _fixed-
parameter tractable_ (FPT), if for any $(x,p)\in\Sigma^{*}\times\mathbb{N}$,
we can decide whether $(x,p)\in L$ 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 a _fixed-parameter tractable_ algorithm, if it decides
whether $(x,p)\in L$ in time bounded by $f(p)|(x,p)|^{O(1)}$.

In a discrete optimization problem, we are interested in finding optimal value
of a function $f(x)$ given that $x$ is an instance of a language $X$. Each
such optimization problem corresponds to a decision problem $X_{D}$ that asks
for existence of $x\in X$ such that $f(x)\leq p$ or $f(x)\geq p$, for a
nonnegative integer $p$. A parameterized decision problem considers a decision
problem $X_{D}$ with respect to a parameter $p^{*}$ such that $\mathbb{N}$ is
the domain of $p^{*}$. If $p^{*}$ and $p$ are the same, i.e., the parameter is
the threshold of $f(x)$ in a decision problem $X_{D}$ that corresponds to an
optimization problem, then we call $p^{*}$ the _natural parameterization_ of
$X_{D}$.

For convenience, the definitions of parameterized problems and fixed-parameter
tractability are often described in terms of a parameter whose domain is the
set of natural numbers. Without loss of generality, the definitions allow much
more broader notions of parameters such as graphs, algebraic structures,
vectors in $\mathbb{N}^{c}$ for some fixed constant $c$. An equivalent notion
of _FPT_ is as follows (for a proof, see Appendix A).

######  Proposition 2.20.

An instance $(x,p)$ of a parameterized problem is decidable in
$f(p)|(x,p)|^{O(1)}$ time if and only if $(x,p)$ is decidable in
$f^{*}(p)+|(x,p)|^{O(1)}$ time.

######  Definition 2.21 (Equivalent instance).

Two instances $(x,p)$ and $(x^{*},p^{*})$ of a parameterized problem $L$ are
called _equivalent_ if $(x,p)\in L$ if and only if $(x^{*},p^{*})\in L$.

A natural consequence of Proposition 2.20 is the notion of _kernelization_
also known as _data reduction_ or _prepossessing_.

######  Definition 2.22 (Kernelization).

Given an instance $(x,p)$ of a parameterized problem $L$, _kernelization_ is
an algorithm that in $|(x,p)|^{O(1)}$ time reduces the instance $(x,p)$ to an
_equivalent instance_ $(x^{*},p^{*})$ of $L$ such that $|x^{*}|\leq f(p)$ and
$p^{*}\leq g(p)$.

We call the reduced instance $(x^{*},p^{*})$ a _kernel_. If $f(p)$ is a
polynomial (resp. exponential) function of $p$ then we say $L$ admits a
polynomial (resp. exponential) kernel. If the reduction is to an instance of a
different parameterized problem then we call the reduced instance a
_compression_ or _bi-kernel_. Kernelization often consists of a set of
reduction rules such that each rule produces an _equivalent instance_. We call
an instance $(x,p)$ _reduced_ with respect to a set of rules if the rules are
not applicable to $(x,p)$.

The following equivalence is straightforward to show (see Proposition 4.8.1 of
[13]), which is the basis of many FPT algorithms.

######  Proposition 2.23.

A _parameterized problem_ $L$ is _FPT_ if and only if $L$ admits a
_kernelization_.

Similar to polynomial time many-one reductions (also known as _Karp
reductions_), we have the following type of reductions for parameterized
problems.

######  Definition 2.24 (Parameterized reduction [8]).

Let $L,L^{*}\subseteq\Sigma^{*}\times\mathbb{N}$ be two parameterized
problems. A parameterized reduction from $L$ to $L^{*}$ is an algorithm that,
given an instance $(x,p)$ of $A$, returns an instance $(x^{*},p^{*})$ of
$L^{*}$ such that (1) $(x,p)$ is a _YES_ instance of $L$ if and only if
$(x^{*},p^{*})$ is a _YES_ instance of $L^{*}$, (2) $p^{*}\leq g(p)$ for some
computable function $g$, and (3) runs in $f(p)|x|^{O(1)}$ time for some
computable function $f$.

From Definition 2.24, if there exists a _parameterized reduction_ from $L$ to
$L^{*}$ and $L^{*}$ has an FPT algorithm with respect to $p^{*}$, then $L$
also has an FPT algorithm with respect to $p$.

Bounded search tree. _Bounded search tree_ is one of the most commonly used
techniques for designing FPT algorithm that often produces provably better FPT
algorithms than many other techniques. The idea is to treat the sequence of
decisions made by an algorithm as a tree $T$. Each node $u$ of $T$ corresponds
to a choice made by the algorithm such as deciding to include an element in a
partial solution. Children of a node $u$ correspond to subsequent choices that
arise as ramifications of the choice made at node $u$. Each node $u$
corresponds to a branch of the tree rooted at node $u$, and the number of
children of $u$ is called the _branching factor_ of node $u$. An algorithm
systematically explores the ramifications of choices made at node $u$ by
recursively visiting nodes of all branches rooted at children of $u$ until a
solution is found. While visiting a child node of $u$, the algorithm makes
substantial progress such as increasing the size of a partial solution. By a
recurrence relation, time required in a subtree $T_{u}$ rooted at node $u$ can
be bounded in terms of time required in the subtrees rooted at the children of
$u$ and time required at node $u$ alone. The recurrence relation can be solved
to provide an upper bound on the time requirement of the algorithm. A simple
strategy often suffices for bounding time requirement of a search tree
algorithm. Let the depth or the height of a tree $T$ be bounded by $h(p)$, and
let the _branching factor_ of any node of $T$ be bounded by $b(p)$. Then the
number of nodes in $T$ is bounded by $\\{b(p)\\}^{h(p)}$. If time spent at
each node is bounded by a polynomial in $|(x,p)|$, then total time required by
the algorithm is bounded by $\\{b(p)\\}^{h(p}|(x,p)|^{O(1)}$, which is an FPT
running time.

##  3 Enumerating Cliques of Restricted Subgraph

In this section, we describe FPT algorithms for _ECC_ and _ACC_ (which can be
extended to design algorithms for other clique cover problems such as the
problems described in Section 1.2). Our focus is on bounded search tree
algorithms for the problems, but we touch upon a number of relevant data
reduction rules. The general theme of these search tree algorithms is as
follows. In each node of a search tree, the corresponding algorithm branches
on a set of cliques constructed from a restricted subgraph. The restriction is
justified with a goal to bound the branching factors in terms of degeneracy or
other parameters. A proof of _NP-completeness_ of _ACC_ is included at the end
of this section.

###  3.1 Edge Clique Cover

The exponential kernel of [22] is based on a result of [25]. We use the result
of [25] and include an exposition of a proof of the result adapted from [22].

######  Definition 3.1 (Equivalent Vertices).

Let $\\{x,y\\}$ be an edge of $G$. $x$ and $y$ are equivalent vertices if the
vertices have the same closed neighbourhood, i.e., $N[x]=N[y]$.

######  Lemma 3.2 ([25]).

Let $G$ be a graph with $n$ vertices such that $G$ contains neither isolated
vertices nor equivalent vertices. If
$\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ is an edge clique cover of $G$,
then $n<2^{k}$.

###### Proof.

For the sake of contradiction suppose $n\geq 2^{k}$. Let
$\boldsymbol{B}\in{\\{0,1\\}}^{n\times k}$ be a matrix such that
$\boldsymbol{B}[x,l]=1$ if vertex $x$ is contained in clique $C_{l}$,
otherwise, $\boldsymbol{B}[x,l]=0$. The number of distinct rows in
$\boldsymbol{B}$ is at most $2^{k}$. If it is $2^{k}$, then included among
these rows is a row $x$ such that $\boldsymbol{B}[x,l]=0$ for all $l\in[k]$.
If the number of distinct rows is less than $2^{k}$, then, since $n\geq
2^{k}$, there exist two distinct rows $x$ and $y$ such that
$\boldsymbol{B}[x,l]=\boldsymbol{B}[y,l]$ for all $l\in k$. The first
condition leads to an isolated vertex, and the second condition leads to a
pair of equivalent vertices. Both conditions lead to contradiction, and the
claim follows. ∎

An immediate consequence of Proposition 2.9 and Lemma 3.2 is as follows.

######  Corollary 3.3.

Let $G$ be a graph with _degeneracy_ $d$ and _independence number_ $\alpha$
such that $G$ contains neither isolated vertices nor equivalent vertices. If
$\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ is an edge clique cover of $G$,
then $d+\alpha<2^{k}$.

Let $(G,k)$ be an instance of _ECC_. The following kernelization rules ensue
from Lemma 3.2.

######  Rule 3.4.

If $x\in V$ is an isolated vertex, then $(G-\\{x\\},k)$ and $(G,k)$ are
equivalent instances. For a solution $\mathcal{C}$ of $(G-\\{x\\},k)$, report
$\mathcal{C}$ as the solution of $(G,k)$.

######  Rule 3.5.

If $\\{x,y\\}\in E$ and $N[x]=N[y]$, then $(G-\\{x\\},k)$ and $(G,k)$ are
equivalent instances. For a solution $\mathcal{C}$ of $(G-\\{x\\},k)$, report
$(\mathcal{C}\backslash\\{C_{i}|y\in C_{i}\\})\cup\\{C_{i}\cup\\{x\\}|y\in
C_{i}\\}$ as the solution of $(G,k)$.

Let $(G,k)$ be a reduced instance with respect to Rules 3.4 and 3.5. We apply
the following rule on $(G,k)$.

######  Rule 3.6.

If $n>(d+1)k$, then report $(G,k)$ is a _NO_ instance of _ECC_.

The correctness of Rule 3.6 follows from the fact that with $k$ cliques and
_clique number_ bounded by $d+1$, we can cover at most $(d+1)k$ vertices.
Since $(G,k)$ is reduced with respect to Rule 3.4, an edge clique cover must
include all the vertices of $G$.

Let $(G,k)$ be a reduced instance with respect to Rules 3.4, 3.5, and 3.6. We
have a _kernel_ with $(d+1)k$ vertices. Note that only Rules 3.4 and 3.6 are
sufficient to get the _kernel_. We need Rule 3.5 to show a better search tree
algorithm.

The search tree algorithm of [22] (henceforth refereed as _ECCG_) works by
enumerating all maximal cliques that contain an uncovered edge selected at
every node of a search tree. For analysis of FPT algorithm, it is sufficient
to consider number of maximal cliques in a subgraph, since each such clique
can be listed spending polynomial time per clique [32].

######  Lemma 3.7 ([45]).

The number of maximal cliques in a graph with $n$ vertices is at most
$3^{n/3}$.

Using Lemma 3.7, we can obtain a bounded search tree algorithm with depth at
most $k$ and branching factor at most $3^{(d+1)k/3}$, i.e., an algorithm $A$
that takes $3^{(d+1)k^{2}/3}n^{O(1)}$ time. By Lemma 3.7, _ECCG_ takes
$3^{k2^{k}/3}n^{O(1)}$ time. The running time of $A$ would be better (or
competitive) than the running time of _ECCG_ if $d=O(2^{k}/k)$. Next, we
describe a search tree algorithm with (unconditionally) better running time
than _ECCG_.

Edge-Clique-Cover-Search$(G,k,\mathcal{C})$: // Abbreviated
ECCS$(G,k,\mathcal{C})$ 1. if $\mathcal{C}$ covers edges of $G$, then return
$\mathcal{C}$ 2. if $k<0$, then return $\varnothing$ 3. select the _first_
uncovered edge $\\{x,y\\}$ from the _DEP_ of $G$ where $y\in N_{d}(x)$ //
Definition 2.17 4. for each maximal clique $Z$ containing $\\{x,y\\}$ in the
subgraph $G[N_{d}[x]\cap N[y]]$ do (a)
$\mathcal{Q}\leftarrow\textbf{ECCS}(G,k-1,\mathcal{C}\cup\\{Z\\})$ (b) if
$\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ 5. return
$\varnothing$

Figure 1: A bounded search tree algorithm for _ECC_ , denoted _ECCS_.

Figure 1 shows a bounded search tree algorithm for _ECC_ , henceforth refereed
as _ECCS_. We assume _ECCS_ has access to a _degeneracy edge permutation_ of
$G$. At step 3, we select the first uncovered edge $\\{x,y\\}$ from the
_degeneracy edge permutation_ such that $y\in N_{d}(x)$. At step 4, we
restrict the search for maximal cliques in a subgraph induced by vertices of
$N_{d}[x]\cap N[y]$ in $G$. In each iteration of step 4, we select a maximal
clique from the restricted search space, and cover the edge $\\{x,y\\}$ with
the clique and recurse. This process is repeated until a solution is found in
a branch (step 4b), or all branches are exhausted without any solution (step
5).

We point out the crucial differences between _ECCG_ and _ECCS_. At step 3,
_ECCG_ uses a heuristic to select an edge, for which _ECCG_ has to enumerate
maximal cliques of the subgraph $G[N[x]\cap N[y]]$, in contrast to enumerating
maximal cliques of a restricted subgraph such as $G[N_{d}[x]\cap N[y]]$.
Consequently, _ECCG_ can only provide an upper bound of $3^{2^{k}/3}$ on the
number of maximal cliques enumerated at step 4: _kernelization_ , based on
Lemma 3.2, can only ensure that the number of vertices are bounded by $2^{k}$.

Next, we describe correctness and running time of _ECCS_. From the choices
made at step 3, we observe following invariant maintained by _ECCS_.

######  Proposition 3.8.

Let $\langle u_{1},u_{2},\ldots,u_{n}\rangle$ be a degeneracy ordering of $V$.
At any node of a search tree of _ECCS_ , if $x=u_{i}$, then all edges incident
on vertices of $\\{u_{1},u_{2},\ldots,u_{i-1}\\}$ are covered.

We also note a property that holds for induced subgraphs, but does not
necessarily hold for arbitrary subgraphs.

######  Proposition 3.9.

For a graph $G=(V,E)$, let $X\subseteq V$ be a set of vertices. If $(G,k)$ is
a _YES_ instance of _ECC_ , then $(G[X],k)$ is a _YES_ instance of _ECC_.

######  Lemma 3.10.

Algorithm _ECCS_ correctly solves the parameterized problem _ECC_.

###### Proof.

Let $\mathcal{A}$ be a family of algorithms that consider uncovered edges
$\\{x,y\\}$ in arbitrary order in step 3 of _ECCS_ , and in step 4 branch into
each of the choices of maximal cliques containing {x,y} in the subgraph
induced by $N[x]\cap N[y]$.

Consider any algorithm $A_{i}\in A$. For a search tree $T$ of $A_{i}$, let us
define a node $u^{T}$ to be a _YES_ node if $A_{i}$ returns at step 1 of
$u^{T}$. We claim that $(G,k)$ is a _YES_ instance of _ECC_ if and only if
$A_{i}$ returns from a _YES_ node. If $A_{i}$ returns from a _YES_ node, then
clearly $(G,k)$ is a _YES_ instance of _ECC_. It remains to show that if
$(G,k)$ is a _YES_ instance of _ECC_ , then $A_{i}$ would return from a _YES_
node. This can be seen as follows. $A_{i}$ 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]$.
$A_{i}$ considers all such possible maximal cliques, and allows a search tree
containing at most $k$ cliques in any leaves of the search tree.

_ECCS_ deviates from the family of algorithms $\mathcal{A}$. Next, we show
that the deviations are safe. Clearly, if _ECCS_ returns from a node at step
1, then $(G,k)$ is a _YES_ instance of _ECC_. Therefore, we only need to show
that if any algorithm $A_{i}\in\mathcal{A}$ returns from a _YES_ node, then
_ECCS_ would also return from a node at step 1.

At each node of the search tree of _ECCS_ , $y\in N_{d}[x]$, and
$N_{d}[x]\subseteq\\{u_{i},u_{i+1},\ldots,u_{n}\\}$. Therefore, $N_{d}[x]\cap
N[y]\subseteq\\{u_{i},u_{i+1},\ldots,u_{n}\\}$. In the enumeration of maximal
cliques, vertices that are not considered by _ECCS_ are $(N[x]\cap
N[y])\backslash(N_{d}[x]\cap N[y])=(N(x)\backslash N_{d}(x))\cap N(y)\subseteq
N(x)\backslash N_{d}(x)\subseteq\\{u_{1},u_{2},\ldots,u_{i-1}\\}$.

By Proposition 3.8, all edges incident on vertices of
$\\{u_{1},u_{2},\ldots,u_{i-1}\\}$ are covered when we are considering maximal
cliques for an edge $\\{x,y\\}$. By Proposition 3.9, if $(G[N[x]\cap
N[y]],k^{*})$ is a _YES_ instance of _ECC_ , then $(G[N_{d}[x]\cap
N[y]],k^{*})$ is a _YES_ instance of _ECC_. Therefore, it is safe to consider
maximal cliques for an edge $\\{x,y\\}$ only in the subgraph $G[N_{d}[x]\cap
N[y]]$. It follows that if any algorithm $A_{i}\in\mathcal{A}$ returns from a
_YES_ node, then _ECCS_ would also return from a node at step 1. ∎

######  Lemma 3.11.

The number of nodes in a search tree of _ECCS_ is at most $1.4423^{dk}$.

###### Proof.

The number of vertices in a subgraph induced by vertices of $N_{d}[x]\cap
N[y]$ is at most $d+1$ i.e., $|N_{d}[x]\cap N[y]|\leq d+1$. Since the vertices
$x$ and $y$ are fixed, we only need to enumerate maximal cliques of the
subgraph $G[N_{d}(x)\cap N(y)]$, containing at most $d-1$ vertices.

By Lemma 3.7, at each node of the search tree, the number of maximal cliques
containing $x$ and $y$ in the subgraph induced by vertices of $N_{d}[x]\cap
N[y]$ is at most $3^{(d-1)/3}<3^{d/3}$. Therefore, the total number of nodes
in the search tree is at most $3^{dk/3}\leq 1.4423^{dk}$ ∎

From Figure 1, it is evident that the time spent at every node of a search
tree of _ECCS_ is bounded by a polynomial of input size. Considering the time
needed for data reduction, we obtain Theorem 1.1 from Lemma 3.11 and
Proposition 2.20.

Next, we discuss a number of consequences of _ECCS_.

Using Lemma 3.7, the number of nodes is a search tree of _ECCG_ is bounded by
$3^{k2^{k}/3}$. By Corollary 3.3, $2^{k}>d+\alpha$. Therefore, we have a
factor of
$\frac{3^{k2^{k}/3}}{3^{dk/3}}>\frac{3^{k(d+\alpha)/3}}{3^{dk/3}}=3^{k\alpha/3}=2^{\Omega(k\alpha)}=2^{\Omega(\alpha^{2})}$
improvement over the bound on search tree size. The last equality follows from
Lemma 2.16. The improvement becomes significant for sparse graphs, such as
when $d=o(2^{k})$ or $\alpha=\Omega(n)$, and we may obtain a factor of
$2^{2^{O(k)}}$ reduction on the number of nodes in the search tree of _ECCS_
compared to _ECCG_. Note that with kernelization we have $n<2^{k}$. Therefore,
preceding improvement carry over to the overall running time.

We point out that single exponential dependence on $k$, with low degree
polynomial of $k$ in the exponent, suffices for sparse graphs.

######  Corollary 3.12.

For $d=O(k)$, _ECC_ has an FPT algorithm running in $2^{O(k^{2})}n^{O(1)}$
time.

######  Corollary 3.13.

For $k=\Omega(\sqrt{m})$, _ECC_ has an FPT algorithm running in
$2^{O(k^{2})}n^{O(1)}$ time.

Corollary 3.13 follows from Lemma 2.14.

From the preceding two observations, it is obvious that the inherent
difficulty of solving _ECC_ on sparse graphs is poorly captured by parameter
$k$ alone. Next, we demonstrate that this difficulty is indeed better captured
by degeneracy.

######  Corollary 3.14.

If $m\geq\lfloor\frac{n^{2}}{4}\rfloor$, then running time of _ECCS_ is
$2^{O(d^{3})}n^{O(1)}$.

###### Proof.

For _ECC_ , we can assume $k\leq\lfloor\frac{n^{2}}{4}\rfloor$ [15]. Also, by
Proposition 2.4, we can assume $k\leq m<nd$. Since
$\lfloor\frac{n^{2}}{4}\rfloor\leq m$, combining preceding inequalities, we
have $k<4d^{2}$. Therefore, _ECCS_ takes $2^{O(d^{3})}n^{O(1)}$ time. ∎

By algebraic manipulation similar to the preceding proof, we can show the
following.

######  Corollary 3.15.

For $c>0,\epsilon>0$, if $m\geq cn^{1+\epsilon}$, then running time of _ECCS_
is $2^{O(d^{2}(d/c)^{1/\epsilon})}n^{O(1)}$.

######  Corollary 3.16.

For $c>0,\epsilon>0$, if $m\geq cn(\log n)^{\epsilon}$, then running time of
_ECCS_ is $2^{O(d^{2}2^{(d/c)^{1/\epsilon}})}n^{O(1)}$.

The preceding observations show that the dependence of the running time of
_ECCS_ on _degeneracy_ shifts from single exponential to double exponential as
graph becomes sparser. Unlike double exponential dependence on $k$, this shift
captures what we expect for sparse graphs.

_ECC_ is _NP-complete_ on planar graphs [3]. Degeneracy of planar graph is at
most 5. Thus we have the following.

######  Corollary 3.17.

For planar graphs, _ECC_ has an FPT algorithm running in $2^{O(k)}n^{O(1)}$
time.

Note that for planar graphs we can easily obtain a _kernel_ with $4k$
vertices, since _clique number_ of planar graph is at most $4$. Then, instead
of running time with exponent linear in $k$ (as in Corollary 3.14), we would
get running time with exponent quadratic in $k$.

###  3.2 Assignment Clique Cover

We describe an FPT algorithm for _ACC_. First, we describe a set of simple
data reduction rules that reduce a given instance $(G,t)$ of _ACC_. We note
that many data reduction rules for _ECC_ may not be directly applicable for
_ACC_ , for example Rule 3.5 (we expand on this later).

######  Rule 3.18.

If $x\in V$ is an isolated vertex or a vertex with no uncovered incident
edges, then $(G-\\{x\\},t)$ and $(G,t)$ are equivalent instances. For a
solution $\mathcal{C}$ of $(G-\\{x\\},t)$, report $\mathcal{C}$ as the
solution of $(G,t)$.

######  Rule 3.19.

Let $x$ be vertex with all its incident edges uncovered, and $N[x]$ induces a
clique $C$ in $G$. Mark all edges of $C$ as covered. Then
$(G-\\{x\\},t-|N[x]|)$ and $(G,t)$ are equivalent instances. For a solution
$\mathcal{C}^{*}$ of $(G-\\{x\\},t-|N[x]|)$, report
$\mathcal{C}^{*}\cup\\{C\\}$ as the solution of $(G,t)$.

Rule 3.19 is correct. Every edge $\\{x,y\\}\in E$ has to be covered by a
clique. Therefore, covering the edge $\\{x,y\\}$ with a clique other than the
clique induced by $N[x]$ would increase number of assignments of $x$.

######  Rule 3.20.

Let $e=\\{x,y\\}$ be an uncovered edge, and $N(x)\cap N(y)=\varnothing$. Mark
the edge $e$ as covered. Then $(G-\\{e\\},t-2)$ and $(G,t)$ are equivalent
instances. For a solution $\mathcal{C}^{*}$ of $(G-\\{e\\},t-2)$, report
$\mathcal{C}^{*}\cup\\{\\{x,y\\}\\}$ as the solution of $(G,t)$.

Rule 3.20 is correct: edge $\\{x,y\\}$ can only be covered by a clique
$C=\\{x,y\\}$. Let $(G,t)$ be a reduced instance with respect to Rules 3.18,
3.19, and 3.20. We apply following rule on $(G,t)$.

######  Rule 3.21.

If $n>t$, then report $(G,t)$ is a _NO_ instance of _ACC_.

Since $(G,t)$ is reduced with respect to Rule 3.18, an _assignment clique
cover_ must include all the vertices of $G$. Therefore, Rule 3.20 is correct.
Next, we describe a bounded search tree algorithm for _ACC_.

Assignment-Clique-Cover-Search$(G,t,\mathcal{C})$: // Abbreviated
ACCS$(G,t,\mathcal{C})$ 1. if $\mathcal{C}$ covers edges of $G$, then return
$\mathcal{C}$ 2. if $t<2$, then return $\varnothing$ 3. select the _first_
uncovered edge $\\{x,y\\}$ from the _DEP_ of $G$ where $y\in N_{d}(x)$ //
Definition 2.17 4. for each _clique_ $Z$ containing $\\{x,y\\}$ in the
subgraph $G[N_{d}[x]\cap N[y]]$ do (a) $\mathcal{Q}\leftarrow\varnothing$ (b)
if $t-|Z|\geq 0$, then
$\mathcal{Q}\leftarrow\textbf{ACCS}(G,t-|Z|,\mathcal{C}\cup\\{Z\\})$ (c) if
$\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ 5. return
$\varnothing$

Figure 2: A bounded search tree algorithm for _ACC_ , denoted _ACCS_.

Figure 2 shows a bounded search tree algorithm for _ACC_ , henceforth referred
as _ACCS_. _ACCS_ uses the same strategy as _ECCS_ to select uncovered edge at
step 3. Unlike _ECCS_ , _ACCS_ searches for _cliques_ rather than _maximal
cliques_ at step 4. But, the restriction of search space for cliques is same
as _ECCS_ : subgraph induced by vertices of $N_{d}[x]\cap N[y]$ in $G$.

The need for enumerating all cliques in step 4, instead of only maximal
cliques, follows from the fact that a maximal clique may include additional
vertices not required for an _edge clique cover_ , and the corresponding
branch of a search tree may miss a solution due to excess decrement of the
value of parameter $t$. The correctness of subgraph restriction is similar to
what has been described in the proof of Lemma 3.10. Therefore, we conclude the
following.

######  Lemma 3.22.

Algorithm _ACCS_ correctly solves the parameterized problem _ACC_.

######  Theorem 3.23.

_ACC_ has an FPT algorithm running in $1.4143^{t^{2}}n^{O(1)}$ time.

###### Proof.

As we have shown in the proof of Lemma 3.11, at each node of a search tree of
_ACCS_ , we only need to enumerate cliques of the subgraph $G[N_{d}(x)\cap
N(y)]$ with at most $d-1$ vertices. At each node of a search tree, the number
of cliques containing the edge $\\{x,y\\}$ in the subgraph $G[N_{d}[x]\cap
N[y]]$ is at most $\sum_{s=1}^{d-1}\binom{d-1}{s}=2^{d-1}$. The depth of a
search tree is bounded by $t/2$. Therefore, the total number of nodes in a
search tree is bounded by $2^{dt/2}\leq 1.4143^{t^{2}}$, since by Rule 3.21,
$d<n\leq t$. The claim follows from Proposition 2.20, considering time needed
for data reduction. ∎

######  Remark 3.24.

For a reduced instance of _ACC_ with respect to Rule 3.18, $n\leq t$.
Therefore, to achieve a running time with respect to parameter $t$, it would
suffice to select edges arbitrarily at step 3 of _ACCS_ , and enumerate
cliques of subgraph $G[N[x]\cap N[y]]$ at step 4. The restriction of search
for cliques in a subgraph $G[N_{d}[x]\cap N[y]]$ is what makes the algorithm
attuned to sparse graphs.

######  Corollary 3.25.

An _assignment-minimum clique cover_ of a graph $G$ can be found in
$2^{O(mn)}$ time using $O(m^{3/2})$ space.

###### Proof.

We can invoke the FPT algorithm for _ACC_ that we just have described with
values of $t$ in the range $[1,2m]$ (by linearly increasing values of $t$ or
doing a binary search in the range) until a solution is found. Total running
time would be $\sum_{t\in[2m]}2^{O(dt)}n^{O(1)}=2^{O(dm)}=2^{O(mn)}$.

The depth a search tree of ACCS is at most $m$, and each such clique would
take $O(d)$ space. Also, enumeration of cliques in step 4 can be done using a
binary vector of size $O(d)$. Therefore, the total space usage of _ACCS_ is
$O(dm)=O(m^{3/2})$. The last equality follows from Lemma 2.14. ∎

We have noted that Rule 3.5 is not directly applicable for _ACC_ , but we can
use rules like that in a broader context. The following two data reduction
rules are applicable for computing an _assignment-minimum clique cover_ of a
graph $G$.

######  Rule 3.26.

Let $\\{x,y\\}$ be an edge of $G$ and $N[x]=N[y]$. If $\mathcal{C}$ is an
_assignment-minimum clique cover_ of $G\backslash\\{x\\}$, then
$(\mathcal{C}\backslash\\{C_{l}|y\in C_{l}\\})\cup\\{C_{l}\cup\\{x\\}|y\in
C_{l}\\}$ is an _assignment-minimum clique cover_ of $G$.

######  Rule 3.27.

Let $x$ and $y$ be distinct vertices of $G$ such that $\\{x,y\\}\not\in E$ and
$N(x)=N(y)$. If $\mathcal{C}$ is an _assignment-minimum clique cover_ of
$G\backslash\\{x\\}$, then
$\mathcal{C}\cup\\{C_{l}\backslash\\{y\\}\cup\\{x\\}|y\in
C_{l},C_{l}\in\mathcal{C}\\}$ is an _assignment-minimum clique cover_ of $G$.

Since a corresponding correct parameter $t$ for $G\backslash\\{x\\}$ cannot be
known beforehand, there is no equivalent of Rule 3.26 or Rule 3.27 for _ACC_.
It is straightforward to see that the preceding two rules are correct.

###  3.3 Other Clique Covers

What we have shown in the preceding discussion for _ECC_ and _ACC_ can be
extended to design algorithms for other clique cover problems, namely _WECP_ ,
_EWCD_ , and _LRVCC_. We refrain from going into the details of these
extensions. Instead, we describe algorithms for these problems using a
different framework in Section 5: one may utilize the descriptions in Section
5 to design full-fledged algorithms based on enumeration of cliques of
restricted subgraph.

###  3.4 _NP-completeness_ of _ACC_

We conclude this section with a proof of Theorem 1.3. We use a construction
used by [30] (Proposition 2).

###### Proof of Theorem 1.3.

_ACC_ is in _NP_ : given an instance $(G,t)$ and a certificate $\mathcal{C}$,
in polynomial time we can verify that $\mathcal{C}$ covers edges of $G=(V,E)$,
and $\sum_{C_{l}\in\mathcal{C}}|C_{l}|\leq t$.

Let $(G^{*},k)$ be an instance of _VCC_. We construct an instance $(G,t)$ of
$ACC$ from $(G^{*},k)$, and show that $(G^{*},k)$ is a _YES_ instance of _VCC_
if and only if $(G,t)$ is a _YES_ instance of _ACC_.

Let $G^{*}=(V^{*},E^{*})$ has $n$ vertices and $m$ edges. To construct $G$, we
start with an empty graph and include all the vertices and edges of $G^{*}$.
Then, we include a set of additional vertices
$X=\\{x_{1},x_{2},\ldots,x_{q}\\}$ with $q\geq 2m+1$. Then, we connect each
pair of vertices $x_{i}\in X$ and $v\in V^{*}$ with an edge. Resulting graph
$G=(V,E)$ has vertices $V=V^{*}\cup X$ and edges
$E=E^{*}\cup\\{\\{x_{i},v\\}|x_{i}\in X,v\in V^{*}\\}$. We complete the
construction by setting $t=(n+k)q+2m$.

Only if. Let $(G^{*},k)$ be a _YES_ instance of _VCC_ , and
$\mathcal{C}^{*}=\\{C_{1}^{*},C_{2}^{*},\ldots,C_{k}^{*}\\}$ be a
corresponding _vertex clique cover_ of $G^{*}$. Since each vertex $x_{i}$ is
connected to all the vertices of $V^{*}$ and no pair of vertices in $X$ are
connected by edge, we can cover all the edges incident on $x_{i}$ with a set
of cliques $\mathcal{C}({x_{i}})=\\{C_{l}^{*}\cup\\{x_{i}\\}|l\in[k]\\}$.
Since the number of individual assignments of vertices to cliques in
$\mathcal{C}^{*}$ is $n$, the number of individual assignments of vertices to
cliques in $\mathcal{C}(x_{i})$ is $n+k$. Therefore, to cover the edges
incident on a vertex $x_{i}$, we would need at most
$\sum_{C_{l}\in\mathcal{C}({x_{i}})}|C_{l}|\leq n+k$ individual assignments of
vertices to cliques. To cover all the edges incident on the vertices of $X$,
we would need at most $\sum_{x_{i}\in
X}\sum_{C_{l}\in\mathcal{C}({x_{i}})}|C_{l}|\leq(n+k)q$ individual assignments
of vertices to cliques. Finally, to cover $m$ edges of $G^{*}$, we would need
at most $2m$ individual assignments of vertices to cliques. Therefore, in
polynomial time, we can construct an _edge clique cover_ $\mathcal{C}$ of $G$
such that $\sum_{C_{l}\in\mathcal{C}}|C_{l}|\leq(n+k)q+2m=t$. It follows that
$(G,t)$ is a _YES_ instance of _ACC_.

If. Let $(G,t)$ be a _YES_ instance of _ACC_ , and $\mathcal{C}$ be a
corresponding _assignment clique cover_ of $G$. Let
$\mathcal{C}(x_{i})=\\{C_{l}|x_{i}\in C_{l},C_{l}\in\mathcal{C}\\}$. For any
$i\in[q]$, the set of cliques $\mathcal{C}(x_{i})$ with $x_{i}$ removed is a
_vertex clique cover_ of $G^{*}$. We need to choose $i\in[q]$ such that
$|\mathcal{C}(x_{i})|\leq k$. Note that for any pair of distinct vertices
$x_{i}$ and $x_{j}$ of $X$, $\mathcal{C}(x_{i})$ and $\mathcal{C}(x_{j})$ are
disjoint, since $\\{x_{i}$, $x_{j}\\}\not\in E$. To show
$(G^{*},|\mathcal{C}(x_{i})|)$ is a _YES_ instance of _VCC_ , choosing
$\mathcal{C}(x_{i})$ such that $\sum_{C_{l}\in\mathcal{C}(x_{i})}|C_{l}|$ is
minimum suffices. We have

$\sum_{C_{l}\in\mathcal{C}(x_{i})}|C_{l}|=\min_{j\in[q]}\sum_{C_{l}\in\mathcal{C}(x_{j})}|C_{l}|\leq\frac{\sum_{j\in[q]}\sum_{C_{l}\in\mathcal{C}(x_{j})}|C_{l}|}{q}\leq\frac{\sum_{C_{l}\in\mathcal{C}}|C_{l}|}{q}\leq\frac{t}{q}$
$=\frac{(n+k)q+2m}{q}=n+k+\frac{2m}{q}\leq n+k.$

The last inequality follows from the choice of $q\geq 2m+1$. For the sake of
contradiction, assume $|\mathcal{C}(x_{i})|=k^{*}>k$. Then, by the definition
of $\mathcal{C}(x_{i})$, $x_{i}$ appears in $k^{*}$ times in
$\mathcal{C}(x_{i})$. Since $x_{i}$ is connected to all $n$ vertices of
$V^{*}$, $\sum_{C_{l}\in\mathcal{C}(x_{i})}|C_{l}|\geq n+k^{*}>n+k$, which
contradicts the fact that $\sum_{C_{l}\in\mathcal{C}(x_{i})}|C_{l}|\leq n+k$.
Therefore, $|\mathcal{C}(x_{i})|\leq k$, i.e., $(G^{*},|\mathcal{C}(x_{i})|)$
is a _YES_ instance of _VCC_. ∎

##  4 New Framework: Building Blocks

We describe underlying concepts of a new framework that we use in Section 5
for algorithm design. Our framework is based on a relaxation of a global
minimality of clique cover and a set representation of graph. We include a
number of characterizations which may be of independent interest (could be
used in other contexts such as designing polynomial time algorithm for
specific class of graphs). We start with a discussion of a number of pitfalls
that we want to deal with the new framework.

###  4.1 Pitfalls Addressed

In terms of exact algorithm design, we have found two major ways that have
been adopted to systematically explore search space of clique covers of a
graph. One way is to explore matrices $\mathbf{B}\in\\{0,1\\}^{n\times m}$
such that $\mathbf{B}\mathbf{B^{T}}=\mathbf{A}$ where $\mathbf{A}$ is the
adjacency matrix of graph. The matrix multiplication is defined with addition
rule $1+1=1$, and diagonal entries of $\mathbf{A}$ are all assumed to be $1$.
Several FPT algorithms [17, 7] are based on exploration of this type of search
space, where binary matrices of dimension $O(k)\times O(k)$ are enumerated
from a search space of size $2^{O(k^{2}\log k)}$. Consequently, this type of
algorithms does not have any regard for sparsity of graph, making them
unsuitable even for moderately small values of parameters.

The other major way is to explore search space consisting of maximal cliques
of (sub)graph. Depending on objective of clique cover, exploring search space
of maximal cliques could become infeasible, even for moderately small input
size. An example is the search tree algorithm of [14] for computing
_assignment-minimum clique cover_ of a graph. Search tree size of [14] is
double exponential in input size in the worst case, and the algorithm also
requires space exponential in input size in the worst case.

Algorithms described in Section 3 explore search spaces that are structurally
dependent on the _degeneracy_ of graph. We ask whether a more robust parameter
than _degeneracy_ can be used to restrict search space further. More
specifically, we ask whether it is possible to restrict search space
structurally with respect to the _clique number_ of graph. Recall _clique
number_ is always bounded by _degeneracy_ (Proposition 2.12). Moreover,
_degeneracy_ can grow linearly with the input size, while _clique number_
remains constant (Remark 2.13).

In this section, our discussion would be focused on _edge clique cover_ and
number of cliques in the cover. We use following definitions in the subsequent
discussion.

######  Definition 4.1 (Minimum Clique Cover).

A _minimum clique cover_ of a graph $G$ is an _edge clique cover_ of $G$ with
smallest number of cliques.

######  Definition 4.2 (Minimal Clique Cover).

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

It is evident from the preceding two definitions that a _minimum clique cover_
is also a _minimal clique cover_. Therefore, it is natural to ask whether we
can find a _minimum clique cover_ by systematically exploring a search space
of _minimal clique covers_. We face with a number of difficulties.

First, note that the complete graph $K_{n}$ has a _minimal clique cover_ of
size $\binom{n}{2}$, clearly indicating a difficult search space to explore.
Second, it is not clear how to systematically explore the search space of
_minimal clique covers_. Third, any conceivable way to systematically explore
the set of _minimal clique covers_ of a graph would require a massive amount
of tests for minimality and provision for removing and restoring cliques,
i.e., enumerating _minimal clique covers_ of a graph would be prohibitive in
terms of time and space. Next, we introduce a relaxation on global minimality
to avoid these pitfalls.

###  4.2 Locally Minimal Clique Cover

######  Definition 4.3 (Locally Minimal Clique Cover).

Let $H=(V_{H},E_{H})$ be a proper subgraph of a graph $G=(V,E)$, and
$\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of $H$.
Let $\\{x,y\\}$ be an uncovered edge of $G$, and $H^{*}$ be the subgraph
induced by vertices of $V_{H}\cup\\{x,y\\}$ in $G$. Let $\mathcal{C}^{*}$ be
an _edge clique cover_ of a subgraph of $H^{*}$ constructed as follows.

(i) If the edge $\\{x,y\\}$ can be covered in a clique $C_{l}\in\mathcal{C}$,
then we cover $\\{x,y\\}$ with exactly one such clique of $\mathcal{C}$ by
letting $C_{l}^{*}=C_{l}\cup\\{x,y\\}$, and we set $\mathcal{C}^{*}$ to be
$(\mathcal{C}\backslash\\{C_{l}\\})\cup\\{C_{l}^{*}\\}$.

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

We call an _edge 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.

The bottom-up constructive clique cover in Definition 4.3 is simple but has
far-reaching consequences. First, search space of _locally minimal clique
cover_ is easy to explore systematically. Second, the search space is much
more compact as it does not try to construct maximal cliques, let alone all
maximal cliques of graph. Third, we will be able to make the search space
exploration efficient, with the help of a set representation introduced later.
Forth, it admits a number of desirable characterizations. We elaborate on
these in subsequent discussion.

######  Definition 4.4 ($E_{\pi(i)}$).

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$. Let $\pi$ be a permutation of $[k]$.
$E_{\pi(i)}=\\{\\{x,y\\}\in C_{\pi(i)}|\\{x,y\\}\not\in C_{\pi(j)},j<i\\}$,
i.e., the set of edges exclusive to $C_{\pi(i)}$ with respect to the cliques
$\\{C_{\pi(1)},C_{\pi(2)},\ldots,C_{\pi(i-1)}\\}$.

An immediate observation for _locally minimal clique cover_ is as follows.

######  Proposition 4.5.

If $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ is a _locally minimal clique
cover_ of $G$, then there exists a permutation $\pi$ such that
$E_{\pi(i)}\neq\varnothing$, for all $i\in[k]$.

The following is a characterization that _minimal clique cover_ does not
admit, but _locally minimal clique cover_ does. Recall the _minimal clique
cover_ of $K_{n}$ with $\binom{n}{2}$ cliques, which arises precisely due to
the fact that _minimal clique cover_ lacks the following characterization.

######  Proposition 4.6.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
$G=(V,E)$. If $\mathcal{C}$ is _locally minimal_ , then for each pair of
distinct cliques $\\{C_{a},C_{b}\\}$ in $\mathcal{C}$, there exist $x\in
C_{a}$, $y\in C_{b}$ such that $x\neq y$ and $\\{x,y\\}\not\in E$.

###### Proof.

We prove the contrapositive, i.e., if for some pairs of distinct cliques
$\\{C_{a},C_{b}\\}$ in $\mathcal{C}$ it holds that for all $x\in C_{a}$ and
for all $y\in C_{b}$, $x\neq y$, $\\{x,y\\}\in E$, then $\mathcal{C}$ is not a
_locally minimal clique cover_ of $G$.

Let $\pi$ be a permutation of $[k]$ and let $\pi(i)=a$ and $\pi(j)=b$. WLOG
assume $i<j$, and consider an edge $\\{y,z\\}\in E_{\pi(j)}$. If no such edge
$\\{y,z\\}$ exists for all $\pi$, then, by Proposition 4.5, $\mathcal{C}$ is
not _locally minimal_. By our assumption, for all $x\in
C_{a}\backslash\\{y,z\\}$, $\\{x,z\\}\in E$ and $\\{x,y\\}\in E$. Clearly,
rule (i) of the construction of _locally minimal clique cover_ is applicable
to the edge $\\{y,z\\}$, but rule (ii) of the construction is being applied.
Since preceding argument holds every permutation $\pi$, it follows that
$\mathcal{C}$ is not _locally minimal_. ∎

The converse of Proposition 4.6 does not hold. But, we can establish a close
equivalent of the converse. This will be crucial for showing sufficiency of
search for different clique covers in a search space of _locally minimal
clique covers_.

######  Proposition 4.7.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
$G=(V,E)$. If for each pair of distinct cliques $\\{C_{a},C_{b}\\}$ in
$\mathcal{C}$, there exist $x\in C_{a}$, $y\in C_{b}$ such that $x\neq y$ and
$\\{x,y\\}\not\in E$, then there exists a permutation $\pi$ of
$\\{1,\ldots,k\\}$ such that $E_{\pi(i)}\neq\varnothing$, for all $i\in[k]$.

###### Proof.

Let $P_{1}$ denote the property that for each pair of distinct cliques
$\\{C_{a},C_{b}\\}$ in $\mathcal{C}$, there exist $x\in C_{a}$, $y\in C_{b}$
such that $x\neq y$ and $\\{x,y\\}\not\in E$. Let $P_{2}$ denote the property
that for all permutation $\pi$ of $\\{1,2,\ldots,k\\}$ there exists $i\in[k]$
such that $E_{\pi(i)}=\varnothing$. We want to show $P_{1}\implies\neg P_{2}$,
equivalently $P_{2}\implies\neg P_{1}$.

Consider any $C_{j}$ such that $\pi(k)=j$ and $E_{\pi(k)}\neq\varnothing$. We
remove $C_{j}$ from further consideration by considering a permutation $\pi$
such that $\pi(k)=j$. We restrict our permutation space to
$\\{1,\ldots,k-1\\}$ from $\\{1,\ldots,k\\}$ as depicted below.

1 | 2 | … | $k-1$ | $k$
---|---|---|---|---
$C_{\pi(1)}$ | $C_{\pi(2)}$ | … | $C_{\pi(k-1)}$ | $C_{j}$

Repeatedly removing all such $C_{j}$ depicted above from further
consideration, we would be able to restrict our permutation space to the
permutations of $\\{1,\ldots,l\\}$ such that $E_{\pi(l)}=\varnothing$, for any
permutation $\pi$ of $\\{1,\ldots,l\\}$. Note that $l>1$ since
$E_{\pi(1)}\neq\varnothing$ for all $\pi$. Following two cases completely
characterize the restricted permutation space.

  1. 1.

For $i,j\in[l]$ there exists a pair of distinct cliques $\\{C_{i},C_{j}\\}$
such that $C_{i}=C_{j}$.

  2. 2.

A least one non-trivial covering of some clique $C_{g}$ of $G$ exists in
$\\{C_{1},\ldots,C_{l}\\}$ (a covering of a clique is trivial if it consists
of a single clique).

It is straightforward to see that if (1) holds, then $P_{1}$ is false. If (2)
holds, then any pairs of cliques in the non-trivial covering makes $P_{1}$
false. ∎

Next characterization shows a close equivalent of the converse of Proposition
4.6.

######  Proposition 4.8.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
$G=(V,E)$. If for each pair of distinct cliques $\\{C_{a},C_{b}\\}$ in
$\mathcal{C}$, there exist $x\in C_{a}$, $y\in C_{b}$ such that $x\neq y$ and
$\\{x,y\\}\not\in E$, then there exists a _locally minimal clique cover_
$\mathcal{C}^{*}$ of $G$ such that $|\mathcal{C}|=|\mathcal{C}^{*}|$ and
$C^{*}_{l}\subseteq C_{l}$, for all $l\in[k]$.

###### Proof.

From Proposition 4.7, we have a permutation $\pi$ of $\\{1,\ldots,k\\}$ such
that $E_{\pi(i)}\neq\varnothing$ for all $i\in[k]$. Consider any such $\pi$,
and let $C^{*}_{\pi(i)}=\\{x|\\{x,y\\}\in E_{\pi(i)}\\}$. Clearly,
$C^{*}_{\pi(i)}\subseteq C_{\pi(i)}$ for all $i\in[k]$, and by definition of
$E_{\pi(i)}$, $\mathcal{C}^{*}$ is an _edge clique cover_ of $G$ with size
$|\mathcal{C}|$. ∎

Following characterization shows that it is sufficient to search for _minimum
clique cover_ in a search space of _locally minimal clique cover_.

######  Proposition 4.9.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$. If $\mathcal{C}$ is a _minimum clique cover_ of $G$, then
there exists a _locally minimal clique cover_ $\mathcal{C}^{*}$ of $G$ such
that $|\mathcal{C}^{*}|=|\mathcal{C}|$ and $C^{*}_{l}\subseteq C_{l}$ for all
$l\in[k]$.

###### Proof.

Any _minimum clique cover_ satisfies the property that for each pair of
distinct cliques $\\{C_{i},C_{j}\\}\in\mathcal{C}$, there exits $x\in C_{i}$,
$y\in C_{j}$ such that $x\neq y$ and $\\{x,y\\}\not\in E$. Therefore, the
claim follows from Proposition 4.8. ∎

In fact, a much stronger characterization exists for _assignment-minimum
clique cover_.

######  Proposition 4.10.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$. If $\mathcal{C}$ is an _assignment-minimum clique cover_ of
$G$, then there exists a _locally minimal clique cover_ $\mathcal{C}^{*}$ of
$G$ such that $|\mathcal{C}^{*}|=|\mathcal{C}|$ and $C^{*}_{l}=C_{l}$ for all
$l\in[k]$.

###### Proof.

Any _assignment-minimum clique cover_ satisfies the property that for each
pair of distinct cliques $\\{C_{i},C_{j}\\}\in\mathcal{C}$, there exits $x\in
C_{i}$, $y\in C_{j}$ such that $x\neq y$ and $\\{x,y\\}\not\in E$. Therefore,
we can use the construction described in Proposition 4.8 to get a clique cover
$\mathcal{C}^{*}$ such that $|\mathcal{C}^{*}|=|\mathcal{C}|$. For
_assignment-minimum clique cover_ , it must be the case that $C^{*}_{l}=C_{l}$
for all $l\in[k]$; otherwise that would contradict the minimality of number of
individual assignments of vertices to cliques in $\mathcal{C}$. ∎

A characterization that holds for both _minimal clique cover_ and _locally
minimal clique cover_ is as follows.

######  Proposition 4.11.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$. If $\mathcal{C}$ is _locally minimal_ , then for each pair
of distinct cliques $\\{C_{i},C_{j}\\}\in\mathcal{C}$, $C_{i}\not\subseteq
C_{j}$.

###### Proof.

For the sake of contradiction assume $\mathcal{C}$ is _locally minimal_ and
there exists a pair of distinct cliques $\\{C_{i},C_{j}\\}\in\mathcal{C}$ such
that $C_{i}\subseteq C_{j}$. This implies there exists a pair of distinct
cliques $\\{C_{i},C_{j}\\}\in\mathcal{C}$ such that for all $x\in C_{i}$, and
for all $y\in C_{j}$, $x\neq y$, $\\{x,y\\}\in E$. By Proposition 4.6, we have
a contradiction to the assumption that $\mathcal{C}$ is _locally minimal_. ∎

Note that Proposition 4.6 implies Proposition 4.11, but the converse does not
hold. Our next characterization shows that a tight upper bound on the size of
_minimum clique cover_ (Theorem 2 [15]) also holds for _locally minimal clique
cover_.

######  Proposition 4.12.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$ with $n$ vertices. If $\mathcal{C}$ is locally minimal, then
$k\leq\lfloor\frac{n^{2}}{4}\rfloor$.

###### Proof.

We induct on $n$. It is straightforward to see that the claim holds for $n=2$
and $n=3$. Assume that the claim holds for all $n_{0}\leq n$.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be a _locally minimal clique
cover_ of a graph $G=(V,E)$ with $n+2$ vertices. Let $\\{x,y\\}$ be an edge of
$G$, and $E_{xy}$ be the set of edges incident to $x$ or $y$, including the
edge $\\{x,y\\}$, i.e., $E_{xy}=\\{\\{w,z\\}\in E|z\in\\{x,y\\}\\}$. Let
$H=(V_{H},E_{H})$ be the subgraph induces by vertices of
$V\backslash\\{x,y\\}$ in $G$. Note that $E_{H}=E\backslash E_{xy}$.

Let $\mathcal{C}^{*}=\\{C_{1},C_{2},\ldots,C_{k^{*}}\\}$ be a _locally minimal
clique cover_ of $H$. Since $|V_{H}|=n$, by inductive hypothesis,
$k^{*}\leq\lfloor\frac{n^{2}}{4}\rfloor$.

Number of edges in $E_{xy}$ is at most $2n+1$. By the construction of _locally
minimal clique cover_ , number of additional cliques needed to cover edges of
$E_{xy}$ is at most $n+1$. This can be seen as follows.

Let $z$ be any vertex of $V_{H}$. Assume $\\{x,z\\}$ and $\\{y,z\\}$ exist in
$G$. WLOG, assume we cover the edge $\\{x,z\\}$ first, either with a clique of
$\mathcal{C}^{*}$ or a new clique $C_{k^{*}+1}=\\{x,z\\}$. Next, we may be
able to cover the edge $\\{y,z\\}$ with a clique of $\mathcal{C}^{*}$; if not,
then the clique $C_{k^{*}+1}=\\{x,z\\}$, we just have created, is sufficient
to cover the edge $\\{y,z\\}$, since the edge $\\{x,y\\}$ exists in $G$. In
any of the cases, to cover edges incident from $x$ and $y$ to $z$, at most one
additional clique would be needed (this also holds if any of the edges
$\\{x,z\\}$ and $\\{y,z\\}$ does not exist in $G$). Therefore, at most $n+1$
additional cliques would be needed, considering all $n$ vertices of $V_{H}$
and the edge $\\{x,y\\}$.

Note that the ordering of covering edges of $E_{xy}$ does not affect the
preceding argument. To see this, let $z_{1}$ and $z_{2}$ be two distinct
vertices of $V_{H}$. If the edges $\\{x,z_{1}\\}$, $\\{x,z_{2}\\}$, and
$\\{z_{1},z_{2}\\}$ exist in $G$, then we may cover these edges with a clique
$\\{x,z_{1},z_{2}\\}$. If the edge $\\{y,z_{1}\\}$ and $\\{y,z_{2}\\}$ both
exist in $G$, then we would not need any additional cliques, since the clique
$\\{x,y,z_{1},z_{2}\\}$ would cover all the edges. Now, if only one of
$\\{y,z_{1}\\}$ and $\\{y,z_{2}\\}$ exits in $G$, then we may need one
additional clique. Therefore, to cover edges incident on $z_{1}$ and $z_{2}$
from $x$ and $y$, at most two additional cliques would be needed. Generalizing
this argument, we see that any $\\{z_{1},z_{2},\ldots,z_{q}\\}\subseteq
V_{H}$, we would need at most $q$ additional cliques to cover all edges
incident from $x$ and $y$ to vertices of $\\{z_{1},z_{2},\ldots,z_{q}\\}$.

We conclude that $k\leq
k^{*}+n+1\leq\lfloor\frac{n^{2}}{4}\rfloor+n+1=\lfloor\frac{(n+2)^{2}}{4}\rfloor$.
∎

Proposition 4.12 gives us a characterization of compactness of _locally
minimal clique cover_ in terms of number of cliques. In subsequent
characterizations, we show compactness of _locally minimal clique cover_ in
terms of vertex assignments and edge assignments.

######  Proposition 4.13.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$, and $N(x)$ denote the neighbours of a vertex $x$. If
$\mathcal{C}$ is _locally minimal_ , then each vertex $x$ appears in at most
$|N(x)|$ distinct cliques of $\mathcal{C}$.

###### Proof.

Let $\mathcal{C}^{*}$ be a _locally minimal clique cover_ of a subgraph of
$G$, and let $\\{x,y\\}$ be an edge not included in the cliques of
$\mathcal{C}^{*}$. Now, consider the expansion of $\mathcal{C}^{*}$ for
$\\{x,y\\}$. Before the expansion, none of the cliques in $\mathcal{C}^{*}$
contained both $x$ and $y$. After the expansion, $\\{x,y\\}$ would not get
selected for expansion in subsequent choices. The number of uncovered edges
$\\{x,y\\}$ incident on a vertex $x$ is at most $|N(x)|$. Therefore, the
number of such expansions of clique covers for a vertex $x$ is at most
$|N(x)|$, i.e., $x$ appears at most $|N(x)|$ times in $\mathcal{C}$. ∎

######  Proposition 4.14.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$ with $m$ edges. If $\mathcal{C}$ is _locally minimal_ , then
the number of individual assignments of vertices to cliques of $\mathcal{C}$
is at most $2m$.

###### Proof.

Since $\mathcal{C}$ is _locally minimal_ , by Proposition 4.13, each vertex
$x$ appears in at most $|N(x)|$ distinct cliques of $\mathcal{C}$. Therefore,
$\sum_{l\in[k]}|C_{l}|\leq\sum_{x\in V}|N(x)|=2m$. ∎

Next characterization follows from Proposition 4.14 and Proposition 2.4.

######  Proposition 4.15.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$ with _degeneracy_ $d$. If $\mathcal{C}$ is _locally minimal_
, then on average a vertex is included in at most $2d$ cliques of
$\mathcal{C}$, i.e., $\frac{\sum_{C_{l}\in\mathcal{C}}|C_{l}|}{n}<2d$.

######  Proposition 4.16.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$ with $m$ edges and $\Delta$ maximum degree. If $\mathcal{C}$
is _locally minimal_ , then the number of individual assignments of edges to
cliques of $\mathcal{C}$ is at most $m\Delta$.

###### Proof.

Consider any edge $\\{x,y\\}\in E$. Since $\mathcal{C}$ is _locally minimal_ ,
by Proposition 4.13, any vertex $x\in V$ appears in at most $|N(x)|$ distinct
cliques of $\mathcal{C}$. Both $x$ and $y$ can appear in at most
$\min\\{|N(x)|,|N(y)|\\}\leq\Delta$ distinct cliques of $\mathcal{C}$.
Therefore, $\sum_{\\{x,y\\}\in E}|\\{C_{l}|\\{x,y\\}\in
C_{l},C_{l}\in\mathcal{C}\\}|\leq m\Delta$. ∎

###  4.3 Implicit Set Representation

From the definition of _locally minimal clique cover_ , a natural question
emerges: from an _edge clique cover_ of a subgraph how would one quickly find
a clique that can cover an edge $\\{x,y\\}$ or report that none exists.
Obviously, scanning the entire set of cliques of the clique cover is an
inefficient method. We address this problem by introducing a set
representation of graph connected to intersection graph theory [35].

######  Definition 4.17 (Intersection Graph).

Let $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{n}\\}$ be a family of sets. The
_intersection graph_ of $\mathcal{F}$ is a graph that has $\mathcal{F}$ as the
vertex set, and an edge for each pair of distinct sets $F_{x}$ and $F_{y}$ if
and only if $F_{x}\cap F_{y}\neq\varnothing$.

On the other hand, every graph is an intersection graph of some family of sets
[15], which leads us to the following definition.

######  Definition 4.18 (Set Representation).

Let $G=(V,E)$ be a graph with $n$ vertices. A family of sets
$\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{n}\\}$ is called a _set representation_
of $G$ if $\\{x,y\\}\in E$ if and only if $F_{x}\cap F_{y}\neq\varnothing$.

Note that _intersection graph_ of a family of sets is unique, but a graph can
have many set representations.

Let $U_{\mathcal{F}}=\cup_{x\in[n]}F_{x}$. Every element $l\in
U_{\mathcal{F}}$ corresponds to a clique of $G$ such that the set
$\\{F_{x}|l\in F_{x}\\}$ corresponds to the vertex set of the clique. Each set
$F_{x}$ corresponds to a set of cliques of $G$ that contain the vertex $x$. By
definition of _set representation_ , for every edge $\\{x,y\\}\in E$, there
exists $l\in U_{\mathcal{F}}$ such that $l\in F_{x}\cap F_{y}$. Therefore, the
set $U_{\mathcal{F}}$ corresponds to an _edge clique cover_ of $G$.

######  Definition 4.19 (Intersection Graph Basis [21]).

Let $G=(V,E)$ be a graph with $n$ vertices and
$\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{n}\\}$ be a _set representation_ of $G$.
Let $U_{\mathcal{F}}=\cup_{x\in[n]}F_{x}$. If $|U_{\mathcal{F}}|$ is minimum
over all _set representations_ of $G$, then $U_{\mathcal{F}}$ is called an
_intersection graph basis_ of $G$.

As a consequence, computing a _minimum clique cover_ of $G$ is equivalent to
computing an _intersection graph basis_ of $G$ (see Theorem 1.6 of [35] for a
proof). Although every _set representation_ of a graph is in one-to-one
correspondence with an _edge clique cover_ of the graph, that does not give us
an efficient way to construct either of them from scratch. Next, we introduce
a constructive way of representing graph that implicitly contains a _set
representation_.

######  Definition 4.20 (Representative Set).

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a subgraph of $G=(V,E)$. We call a clique $C_{l}\in\mathcal{C}$ a
_representative_ of a vertex $x\in V$ if either (1) $x\in C_{l}$ or (2)
$x\not\in C_{l}$ and $C_{l}\subseteq N(x)$. A _representative set_ $R_{x}$ of
a vertex $x$ is the set of (indices of) representatives of $x$ in
$\mathcal{C}$, i.e., $R_{x}=\\{l\in[k]|x\in C_{l}\text{ or }(x\not\in
C_{l}\text{ and }C_{l}\subseteq N(x))\\}$.

######  Definition 4.21 (Implicit Set Representation).

Let $\mathcal{C}$ be an _edge clique cover_ of graph $G=(V,E)$ and $R_{x}$ be
the corresponding _representative set_ for a vertex $x$. We call the family of
sets $\mathcal{R}=\\{R_{1},R_{2},\ldots,R_{n}\\}$ an _implicit set
representation_ of $G$.

$x$$w$$z$$y$$a$$b$$c$$d$

Figure 3: An example graph $G$ showing $R_{x}\cap R_{y}\neq\varnothing$ does
not imply $\\{x,y\\}\in E$. A _minimum clique cover_ $\mathcal{C}$ of $G$
consists of following cliques: $C_{1}=\\{x,a,z\\}$, $C_{2}=\\{x,b,w\\}$,
$C_{3}=\\{y,c,w\\}$, $C_{4}=\\{y,d,z\\}$, $C_{5}=\\{w,z\\}$. For all
$v\in\\{a,b,c,d,z,w\\}$, _set representation_ and _implicit set
representation_ of $G$ have the same sets for $F_{v}$ and $R_{v}$
respectively. But, _set representation_ has $F_{x}=\\{1,2\\}$,
$F_{y}=\\{3,4\\}$, whereas _implicit set representation_ has
$R_{x}=\\{1,2,5\\}$, $R_{y}=\\{3,4,5\\}$.

Note that _set representation_ requires biconditional for every edge:
$\\{x,y\\}\in E\Longleftrightarrow F_{x}\cap F_{y}\neq\varnothing$. _Implicit
set representation_ can only ensure one way implication: $\\{x,y\\}\in
E\implies R_{x}\cap R_{y}\neq\varnothing$. Figure 3 shows an example where
$R_{x}\cap R_{y}\neq\varnothing$ does not imply $\\{x,y\\}\in E$. It would be
evident from following characterization that an _implicit set representation_
of a graph always contains a _set representation_ of the graph.

######  Proposition 4.22.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G$ with $n$ vertices, and $\mathcal{R}$ be the corresponding
_implicit set representation_ of $G$. Let $U_{\mathcal{R}}=\cup_{x\in
V}R_{x}$. If $|U_{\mathcal{R}}|$ is minimum over all _implicit set
representations_ of $G$, then $\mathcal{C}$ is a _minimum clique cover_ of
$G$.

###### Proof.

Let $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{n}\\}$ be a family of sets where
$F_{x}=R_{x}\backslash\\{l\in[k]|x\not\in C_{l}\\}$. Let
$U_{\mathcal{F}}=\cup_{x\in V}F_{x}$. Note that $\mathcal{F}$ is a _set
representation_ of $G$, since $F_{x}=\\{l|x\in C_{l}\\}$. Moreover,
$U_{\mathcal{F}}=U_{\mathcal{R}}$. $|U_{\mathcal{F}}|$ is minimum over all
_set representation_ of $G$. To see this, suppose $|U_{\mathcal{F}}|$ is not
minimum, i.e., there exists $l\in U_{\mathcal{F}}$ such that $C_{l}$ can be
removed from $\mathcal{C}$, which contradicts the assumption that
$|U_{\mathcal{R}}|$ is minimum. Therefore, $U_{\mathcal{F}}$ is an
_intersection graph basis_ of $G$. Since $U_{\mathcal{F}}$ is an _intersection
graph basis_ of $G$, $\mathcal{C}$ is a _minimum clique cover_ of $G$. ∎

As in Proposition 4.22, we can obtain similar characterizations for
_assignment-minimum clique cover_.

######  Proposition 4.23.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G$ with $n$ vertices, and $\mathcal{R}$ be the corresponding
_implicit set representation_ of $G$. If $\sum_{x\in
V}|R_{x}\backslash\\{l\in[k]|x\not\in C_{l}\\}|$ is minimum over all _implicit
set representations_ of $G$, then $\mathcal{C}$ is an _assignment-minimum
clique cover_ of $G$.

Definition 4.20 captures the idea that a _representative_ of a vertex $x$
corresponds to a clique that may be used to cover an edge incident on $x$,
regardless of whether $x$ is contained in the clique. So far it may not be
evident how Definition 4.20 resolves the problem of efficiently constructing a
_set representation_ from scratch. In following characterization we provide a
clarification.

######  Proposition 4.24.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a subgraph of $G=(V,E)$, and $R_{x}$ be the corresponding _representative set_
of a vertex $x$. Let $\\{x,y\\}\in E$ be an uncovered edge. There exists
representative set $l\in R_{x}\cap R_{y}$ if and only if $\\{x,y\\}$ can be
covered by a clique $C_{l}\in\mathcal{C}$.

###### Proof.

Only if. Since $\\{x,y\\}$ is an uncovered edge, both $x$ and $y$ are not
contained in any of the cliques of $\mathcal{C}$. By the definition of
_representative 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)$. Each of the three cases, both
$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\\}$ is uncovered, 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 R_{x}$ and $l\in
R_{y}$. Similarly, $l\in R_{x}$ and $l\in R_{y}$ if $y$ is contained in
$C_{l}$ or both $x$ and $y$ are not contained in $C_{l}$. Therefore, $l\in
R_{x}\cap R_{y}$. ∎

Proposition 4.24 immediately connects us to the construction of _locally
minimal clique cover_. To cover an edge $\\{x,y\\}$, we can simply select a
clique $C_{l}\in\mathcal{C}$ if $l$ is contained in $R_{x}\cap R_{y}$. Each
such choice to cover an edge may require update of some sets in $\mathcal{R}$
to conform to Definition 4.20. We describe the updates in the context of
algorithm design (Section 5). Our next characterization provides a bound on
the space requirement of _implicit set representation_ for constructing a
_locally minimal clique cover_.

######  Proposition 4.25.

Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{k}\\}$ be an _edge clique cover_ of
a graph $G=(V,E)$ with $m$ edges, and $\mathcal{R}$ be the corresponding
_implicit set representation_ of $G$. If $\mathcal{C}$ is _locally minimal_ ,
then $\sum_{x\in V}|R_{x}|<2m+k\Delta$.

###### Proof.

From the definition of _representative set_ , we have

$\sum_{x\in V}|R_{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)\\}|.$

For the first sum on the right hand side, by Proposition 4.14, we have

$\sum_{x\in V}|\\{l|x\in C_{l}\\}|=\sum_{C_{l}\in\mathcal{C}}|C_{l}|\leq 2m.$

It remains to show a bound for the second sum of the right hand side.

Since $\mathcal{C}$ is _locally minimal_ , there exists a permutation $\pi$ of
$\\{1,\ldots,k\\}$ such that $C_{\pi(i)}$ contains an edge $\\{x,y\\}$ not
contained in any $C_{\pi(j)},j<i$. For the permutation $\pi$, existence of
$C_{\pi(i)}$ is necessary for covering $\\{x,y\\}$. WLOG we can assume that in
the _locally minimal_ construction of $\mathcal{C}$, the edge $\\{x,y\\}$
triggered the creation of $i^{th}$ clique in $\mathcal{C}$. Immediately after
including $\\{x,y\\}$ in the $i^{th}$ clique of $\mathcal{C}$, we would have
$\pi(i)\in R_{z}$ for all $z\in N[x]\cap N[y]$ (from the definition of
_representative set_).

For any subsequent edge $\\{x,y\\}$ added to the $i^{th}$ clique of
$\mathcal{C}$ (for locally minimal construction), $\pi(i)\in R_{x}\cap R_{y}$
holds by Proposition 4.24. Therefore, all _representative sets_ that include
$\pi(i)$ have already been accounted for, when we created (by _locally
minimal_ construction) the $i^{th}$ clique of $\mathcal{C}$.

Any vertex $z$ such that $z\not\in C_{\pi(i)}$, but $C_{\pi(i)}\subseteq
N(z)$, must be a common neighbour of $x$ and $y$ such that the edge
$\\{x,y\\}$ required the creation of $C_{\pi(i)}$. And $|\\{z|z\not\in
C_{\pi(i)},C_{\pi(i)}\subseteq N(z)\\}|\leq|N(x)\cap N(y)|<\Delta$. Summing
over all cliques we get,

$\sum_{C_{l}\in\mathcal{C}}|\\{x|x\not\in C_{l},C_{l}\subseteq
N(x)\\}|<k\Delta.$

Consider a bipartite graph $B=(V,\mathcal{C},E_{B})$ where $E_{B}$ is the
relation of vertices and cliques from the second condition of _representative_
: $E_{B}=\\{\\{x,C_{l}\\}|x\in V,C_{l}\in\mathcal{C},x\not\in
C_{l},C_{l}\subseteq N(x)\\}$. Sum of the degrees of the vertices on the $V$
side of $B$ is equal to the sum of the degrees of the vertices on the
$\mathcal{C}$ side of $B$. Therefore,

$\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)\\}|<k\Delta.$

∎

######  Remark 4.26.

A tighter bound than Proposition 4.25 is possible if we construct _locally
minimal clique cover_ by choosing the edges in the order of _DEP_ of $G$, and
keep maintaining only necessary _representative sets_. At any stage of the
construction of _locally minimal clique cover_ , let $\\{x,y\\}$ be the first
uncovered edge of _DEP_ where $y\in N_{d}(x)$. Note that if $x=u_{i}$, then
all edges incident on $u_{j}$ such that $j<i$ are covered. Therefore, if we
choose to add a new clique for $\\{x,y\\}$, then we only need to keep this
information for the _representative sets_ of $N_{d}[x]\cap N[y]$. As a
consequence, the $k\Delta$ bound in the proof of Proposition 4.25 can be
replaced with $dk$, since $|N_{d}(x)\cap N(y)|<d$. Overall, we would have
$O(m+dk)$ space bound. Furthermore, since we can assume $d=O(\sqrt{m})$, for
$k=O(\sqrt{m})$ this bound becomes $O(m)$.

##  5 New Framework: Algorithms

In this section, we describe a new set of bounded search tree algorithms for
the problems listed in Section 1.2. The algorithms are based on the concepts
introduced in Section 4. The general theme of these search tree algorithms is
as follows. At each node of a search tree, the corresponding algorithm
branches on a set of cliques already constructed for a partial solution
(clique cover of a subgraph). Consequently, branching factors of a search tree
can be bounded in terms of number of cliques in a clique cover or other
parameters. Most notably, we would be able to show that the size of a search
tree is structurally dependent on the _clique number_ of graph, a feature
lacking in the algorithms we have presented in Section 3.

###  5.1 Edge Clique Cover

We will continue to assume that data reduction rules are applied on an
instance $(G,k)$ of _ECC_ , including the rules described in Section 3.1.
Figure 4 shows our new bounded search tree algorithm for _ECC_ , henceforth
referred as _ECCS2_. For better readability, we describe the details of steps
3a, 3d, 4a, and 4d separately as subroutines in Figure 5.

_ECCS2_ works as follows. At every node of the search tree, it selects the
_last_ uncovered edge $\\{x,y\\}$ from the _DEP_ of $G$ such that $y\in
N_{d}(x)$. Then, it branches on each of the choices of _representatives_ $l\in
R_{x}\cap R_{y}$, by covering the edge $\\{x,y\\}$ with the clique $C_{l}$
(steps 3a-3d). If all of these branches fail and the parameter $k$ permits,
then it creates an additional branch (steps 4a-4d), by covering the edge
$\\{x,y\\}$ with a new clique.

Algorithm _ECCS2_ works by modifying a single _edge clique cover_
$\mathcal{C}$ and a single _implicit set representation_ $\mathcal{R}$ at
every node of a search tree. This makes the algorithm space efficient. Now, to
conform to the definition of _representative set_ , we need to update
$\mathcal{R}$ in response to changes in the cliques of $\mathcal{C}$ (steps
3a, 3d), or inclusion/exclusion of clique in $\mathcal{C}$ (steps 4a, 4d).
Next, we expand on these updates, included in the subroutines of _ECCS2_ in
Figure 5.

We use a data structure $\mathcal{D}$ to help the updates of sets in
$\mathcal{R}$. A set $D_{l}\in\mathcal{D}$ contains a set of vertices that
have clique $C_{l}$ in their _representative sets_ , i.e., $D_{l}=\\{x\in
V|l\in R_{x},C_{l}\in\mathcal{C}\\}$. The sets in $\mathcal{R}$ contain a
mapping of vertices to the representatives (cliques), whereas the sets in
$\mathcal{D}$ contain the corresponding inverse mapping of the representatives
(cliques) to the vertices.

In the subroutine for step 4a, a new clique, with index $q$, is included in
the solution. By the definition of _representative set_ , this prompts $q$ to
be included in the _representative sets_ of all vertices in $N[x]\cap N[y]$.
Similarly, in the subroutine for step 4d, the clique $q$ is excluded from the
clique cover, which prompts $q$ to be excluded from the representative sets of
all vertices in $N[x]\cap N[y]$.

In the subroutine for step 3a, since the edge $\\{x,y\\}$ to be included in
$C_{l}$, any vertex $z$ such that $l\in R_{z}$ must have both $x$ and $y$ in
the neighbourhood of $z$. The set of vertices that violates this requirement
is collected in a set $U$ (a local data structure allocated for every node in
a search tree), and corresponding _representative sets_ of these vertices are
updated. Indicator variable $x_{l}$ (resp. $y_{l}$) is set that would denote
whether the vertex $x$ (resp. $y$) is already contained in $C_{l}$. The
subroutine for step 3d simply undoes the updates of $\mathcal{R}$ and
$\mathcal{D}$ using the set $U$. The indicator variables are used to restore
the clique $C_{l}$ to the state prior to including the edge $\\{x,y\\}$ in
$C_{l}$. Each of the subroutines of Figure 5 takes $O(\Delta)$ time.

Edge-Clique-Cover-Search2$(G,k,\mathcal{C},\mathcal{R})$: // Abbreviated
ECCS2$(G,k,\mathcal{C},\mathcal{R})$ 1. if $\mathcal{C}$ covers edges of $G$,
then return $\mathcal{C}$ 2. select the _last_ uncovered edge $\\{x,y\\}$ from
the _DEP_ of $G$ where $y\in N_{d}(x)$ // cf. step 3 of _ECCS_ in Figure 1 3.
for each $l\in R_{x}\cap R_{y}$ do (a) cover the edge $\\{x,y\\}$ with the
clique $C_{l}$ and update $\mathcal{R}$ // Figure 5 (a) (b)
$\mathcal{Q}\leftarrow\textbf{ECCS2}(G,k,\mathcal{C},\mathcal{R})$ (c) if
$\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ (d) undo changes done
to $\mathcal{C}$ and $\mathcal{R}$ at step 3a // Figure 5 (b) 4. if $k>0$,
then (a) set $\mathcal{C}$ to $\mathcal{C}\cup\\{\\{x,y\\}\\}$ and update
$\mathcal{R}$ // Figure 5 (c) (b)
$\mathcal{Q}\leftarrow\textbf{ECCS2}(G,k-1,\mathcal{C},\mathcal{R})$ (c) if
$\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ (d) undo changes done
to $\mathcal{C}$ and $\mathcal{R}$ at step 4a // Figure 5 (d) 5. return
$\varnothing$

Figure 4: A bounded search tree algorithm for _ECC_ , denoted _ECCS2_.

Step 3a: 1. $U\leftarrow\varnothing$ 2. for each $z\in
D_{l}\backslash\\{x,y\\}$ such that $\\{x,z\\}\not\in E$ or $\\{y,z\\}\not\in
E$ do (a) $U\leftarrow U\cup\\{z\\}$ (b) $R_{z}\leftarrow
R_{z}\backslash\\{l\\}$ 3. $D_{l}\leftarrow D_{l}\backslash U$ 4.
$x_{l}\leftarrow\mathbbm{1}_{[x\in C_{l}]}$ 5.
$y_{l}\leftarrow\mathbbm{1}_{[y\in C_{l}]}$ 6. $C_{l}\leftarrow
C_{l}\cup\\{x,y\\}$

(a)

Step 3d: 1. for each $z\in U$ do (a) $R_{z}\leftarrow R_{z}\cup\\{l\\}$ (b)
$D_{l}\leftarrow D_{l}\cup\\{z\\}$ 2. if $x_{l}=0$, then set $C_{l}$ to
$C_{l}\backslash\\{x\\}$ 3. if $y_{l}=0$, then set $C_{l}$ to
$C_{l}\backslash\\{y\\}$

(b)

Step 4a: 1. $q\leftarrow|\mathcal{C}|+1$ 2. $C_{q}\leftarrow\\{x,y\\}$ 3.
$D_{q}\leftarrow N[x]\cap N[y]$ 4. for each $z\in D_{q}$ do (a)
$R_{z}\leftarrow R_{z}\cup\\{q\\}$

(c)

Step 4d: 1. $q\leftarrow|\mathcal{C}|$ 2.
$\mathcal{C}\leftarrow\mathcal{C}\backslash\\{C_{q}\\}$ 3. for each $z\in
D_{q}$ do (a) $R_{z}\leftarrow R_{z}\backslash\\{q\\}$

(d)

Figure 5: Subroutines of _ECCS2_ shown in Figure 4.

The definition of _locally minimal_ construction is oblivious of edge
permutation. An exact algorithm that strictly adheres to the definition of
_locally minimal_ construction would potentially need to try all permutations
of edges (for _ECCS_ , this would be equivalent to trying all possible choices
of uncovered edge at step 2). Consequently, we would have algorithms with
large dependency on parameters (for example, we would need $2^{O(\beta
k^{2})}n^{O(1)}$ or $2^{\beta k\log(\beta^{2}k^{3})}n^{O(1)}$ running time for
_ECC_). Furthermore, we want to impose permutations of edges (such as step 2
of _ECCS2_) so that we can bound the branching factors of a search tree with
certain choices of parameters (such as degeneracy). We address these issues by
judicious relaxation of _locally minimal_ construction.

If the edge $\\{x,y\\}$ (selected at step 2) can be covered by a clique
$C_{l}\in\mathcal{C}$, then _ECCS2_ selects exactly one such clique from the
set $R_{x}\cap R_{y}$. Therefore, every branch of step 3 conforms to the
_locally minimal_ construction. If all branches of step 3 fail, only then the
edge $\\{x,y\\}$ may need to be covered with a new clique in step 4a. If
$R_{x}\cap R_{y}=\varnothing$, then step 4 still conforms to the _locally
minimal_ construction. If $R_{x}\cap R_{y}\neq\varnothing$ and all branches of
step 3 fail, then _ECCS2_ relaxes the requirement of _locally minimal_
construction. In this case, _ECCS2_ considers the possibility of a branch with
at most $k$ cliques where the edge $\\{x,y\\}$ is covered with a clique, not
contained in the current partial solution $\mathcal{C}$. Therefore, if $k$
permits, then _ECCS2_ includes a new clique in the solution. Incidentally,
this type of adaptation would be required for other objective of clique
covers, where we would need to include an edge to a specified number of
cliques.

Preceding adaptation may seem puzzling, considering the fact that with a
simple relaxation of _locally minimal_ construction we are able to avoid
enumerating all possible choices of an uncovered edge at step 2 of _ECCS2_. We
shed some light on this.

Let $(G,k)$ be a _YES_ instance of ECC, and $\mathcal{C}^{*}$ be a
corresponding clique cover. Let us call a clique cover $\mathcal{C}$ of a
subgraph of $G$ a _subcovering_ of $\mathcal{C}^{*}$ if every clique
$C_{i}\in\mathcal{C}$ is contained in a clique $C^{*}_{l}\in\mathcal{C}^{*}$,
and no pair of distinct cliques $C_{i},C_{j}\in\mathcal{C}$ are contained in
the same clique $C^{*}_{l}\in\mathcal{C}^{*}$. In the search tree $T$ of
ECCS2, for $(G,k)$, consider a clique cover $\mathcal{C}$ of a subgraph of
$G$, constructed at a node $u^{T}$. Observe that if the clique cover
$\mathcal{C}$ at node $u^{T}$ is a _subcovering_ of $\mathcal{C}^{*}$, then
_ECCS2_ would not backtrack from node $u^{T}$, i.e., a clique cover of $G$
would be returned from node $u^{T}$. To get a _subcovering_ $\mathcal{C}$ of
$\mathcal{C}^{*}$ at node $u^{T}$, it is irrelevant in what order we
constructed the cliques in $\mathcal{C}$, and in what order edges of
individual clique $C_{l}\in\mathcal{C}$ are included in $C_{l}$. All that
matters is being able to construct _subcoverings_ of $\mathcal{C}^{*}$ with
more and more cliques. The relaxation at step 4 of _ECCS2_ is precisely for
this purpose: even if $R_{x}\cap R_{y}$ is nonempty, we allow the edge
$\\{x,y\\}$ to be included in a new clique, as a potential extension for a
larger subcovering of some $\mathcal{C}^{*}$.

A correctness proof for _ECCS2_ can be obtained using induction (see Appendix
B). Thus we conclude the following.

######  Lemma 5.1.

Algorithm _ECCS2_ correctly solves the parameterized problem _ECC_.

The space use of _ECCS2_ can be bounded as follows (see Appendix B for a
proof).

######  Lemma 5.2.

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

Next, we describe bounds on the depth and the branching factors of a search
tree of _ECCS2_.

######  Lemma 5.3.

The depth of a search tree of _ECCS2_ is at most $\beta k$.

###### Proof.

Every new clique starts with two vertices (step 4a), and each expansion of a
clique (step 3a) with an uncovered edge $\\{x,y\\}$ will include at least one
new vertex to the clique. Therefore, number of total possible expansions of
any clique is at most $\beta-2$. With at most $k$ cliques allowed in any
branches, the depth of a search tree is at most $\beta k$. ∎

Recall by $\langle u_{1},u_{2},\ldots,u_{n}\rangle$ we denote degeneracy
ordering of $V$. Since for any $x=u_{i}$, we only consider $y\in N_{d}(x)$,
any vertex $z\in N(x)\backslash N_{d}(x)$ would not be included in any clique
$C_{l}\in\mathcal{C}$ until we process a node such that $x=z$. Therefore, by
our choice of uncovered edge $\\{x,y\\}$ for each node of the search tree of
_ECCS2_ , the following invariant holds.

######  Proposition 5.4.

At any node of a search tree of _ECCS_ , if $x=u_{i}$, then for all
$C_{l}\in\mathcal{C},C_{l}\subseteq\\{u_{i},u_{i+1},\ldots,u_{n}\\}$.

######  Lemma 5.5.

The number of branches at any node of a search tree of _ECCS2_ is at most
$\min\\{k,\binom{d+1}{2}\\}$.

###### Proof.

Consider an uncovered edge $\\{x,y\\}$ at step 2 of _ECCS2_. For the branches
of step 3, by Proposition 5.4, we only need to consider cliques created for
the subgraph induced by vertices of $\\{u_{i},u_{i+1},\ldots,u_{n}\\}$ in $G$.

Since $|N_{d}[x]|\leq d+1$, maximum number edges in the subgraph induced by
the vertices of $N_{d}[x]$ is at most $\binom{d+1}{2}$. Since $y\in N_{d}(x)$
and the edge $\\{x,y\\}$ is uncovered, number of cliques in $\mathcal{C}$ that
are also included in the representative sets of $x$ and $y$ is less than
$\binom{d+1}{2}$, i.e., $|R_{x}\cap R_{y}|<\binom{d+1}{2}$. Considering the
branch for a new clique at step 4, number of branches at any node of a search
tree of _ECCS2_ is at most $\binom{d+1}{2}$.

At any node of the search tree at most $k$ cliques are allowed in
$\mathcal{C}$, i.e., $|R_{x}\cap R_{y}|\leq k$. If at any node of the search
tree $|R_{x}\cap R_{y}|=k$, then there is no branch at step 4 for the
corresponding node. The claim follows. ∎

######  Lemma 5.6.

The number of nodes in a search tree of _ECCS2_ is at most $2^{\beta k\log
k}$.

###### Proof.

From Lemma 5.3, the depth of a search tree of _ECCS2_ is at most $\beta k$.
From Lemma 5.5, the branching factors of a search tree of _ECCS2_ are bounded
by $\min\\{k,\binom{d+1}{2}\\}\leq k$. Therefore, the number of nodes in a
search tree of _ECCS_ is at most $k^{\beta k}=2^{\beta k\log k}$. ∎

Considering time needed for data reduction, Theorem 1.2 follows from Lemma 5.6
and Proposition 2.20.

We have shown in Section 3 that the algorithm _ECCS_ has consistently better
running time than _ECCG_ [22]. For a large class of graphs, _ECCS2_ further
beats _ECCS_ in the running time. This can be seen as follows. From Lemma 5.5,
we have $\min\\{k,\binom{d+1}{2}\\}\leq\binom{d+1}{2}<(d+1)^{2}$. Therefore,
the number of nodes in a search tree of _ECCS2_ is at most $2^{O(\beta k\log
d)}$. For $\beta=o(d/\log d)$, _ECCS2_ improves the bound on search tree size
by a factor of $\frac{2^{O(dk)}}{2^{O(\beta k\log d)}}=2^{O(k(d-\beta\log
d))}=2^{O(dk)}$, an exponential improvement over the bound on search tree
size. For many instances of _ECC_ , $\beta=o(d/\log d)$ is a very mild
requirement, considering that $d$ can grow linearly with the input size, while
$\beta$ remains constant (Remark 2.13).

###  5.2 Assignment Clique Cover

We will continue to assume that data reduction rules are applied on an
instance $(G,t)$ of _ACC_ , including the rules described in Section 3.2.
Figure 6 shows our new bounded search tree algorithm for _ACC_. henceforth
referred as _ACCS2_. Steps 4c, 4f, 5a, 5d of _ACCS2_ are identical to the
steps 3a, 3d, 4a, 4d of _ECCS2_ described in Figure 5.

Assignment-Clique-Cover-Search2$(G,t,\mathcal{C},\mathcal{R})$: // Abbreviated
ACCS2$(G,t,\mathcal{C},\mathcal{R})$ 1. if $\mathcal{C}$ covers edges of $G$,
then return $\mathcal{C}$ 2. if $t\leq 0$ return $\varnothing$ 3. select the
_last_ uncovered edge $\\{x,y\\}$ from the _DEP_ of $G$ where $y\in N_{d}(x)$
// cf. step 3 of _ACCS_ in Figure 2 4. for each $l\in R_{x}\cap R_{y}$ do (a)
$s\leftarrow|\\{x,y\\}\backslash(C_{l}\cap\\{x,y\\})|$ (b) if $t<s$, then go
to the next iteration of step 4 (c) cover the edge $\\{x,y\\}$ with the clique
$C_{l}$ and update $\mathcal{R}$ // Figure 5 (a) (d)
$\mathcal{Q}\leftarrow\textbf{ACCS2}(G,t-s,\mathcal{C},\mathcal{R})$ (e) if
$\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ (f) undo changes done
to $\mathcal{C}$ and $\mathcal{R}$ at step 4c // Figure 5 (b) 5. if $t\geq 2$,
then (a) set $\mathcal{C}$ to $\mathcal{C}\cup\\{\\{x,y\\}\\}$ and update
$\mathcal{R}$ // Figure 5 (c) (b)
$\mathcal{Q}\leftarrow\textbf{ACCS2}(G,t-2,\mathcal{C},\mathcal{R})$ (c) if
$\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ (d) undo changes done
to $\mathcal{C}$ and $\mathcal{R}$ at step 5a // Figure 5 (d) 6. return
$\varnothing$

Figure 6: A bounded search tree algorithm for _ACC_ , denoted _ACCS2_.

In a search tree of _ACCS2_ , there is no depth bound for the number of
cliques. _ACCS_ will create as many cliques as permitted by the parameter $t$,
until it finds a clique cover of $G$ at step 1. At step 4a of _ACCS2_ , we
count out of two vertices $x$ and $y$ how many are missing in $C_{l}$: it
could only be one or two. Only scenario for which we cannot execute steps
4c-4f would be when $s=2$ but $t=1$. We are reusing the subroutines of _ECCS2_
for _ACCS2_ , and rest of the steps of _ACCS2_ are fairly straightforward
adaptation of _ECCS2_. We can adapt the proof of Lemma 5.1 to show correctness
of _ACCS2_ (see Appendix B). Thus we conclude the following.

######  Lemma 5.7.

Algorithm _ACCS2_ correctly solves the parameterized problem _ACC_.

######  Lemma 5.8.

The number of nodes in a search tree of _ACCS2_ is at most $4^{t\log t}$.

###### Proof.

The branching factors of _ACCS2_ are bounded by $\binom{d+1}{2}$: this follows
from the first part of the proof of Lemma 5.5. By Rule 3.21, $d+1\leq n\leq
t$. The depth of a search tree of _ACCS2_ is at most $t$. Therefore, the
number of nodes in a search tree of _ACCS2_ is at most
$\binom{t}{2}^{t}<t^{2t}=4^{t\log t}$. ∎

Theorem 1.4 follows from Lemma 5.8 and Proposition 2.20, considering time
needed for data reduction. The running time of Corollary 1.5 follows from
similar arguments presented for Corollary 3.25. The space bound of Corollary
1.5 follows from Lemma 5.2, since for an _assignment-minimum clique cover_
$k=m$ suffices.

###  5.3 Weighted Edge Clique Partition

We describe a bounded search tree algorithm for the _WECP_ problem,
considering that a given instance of _WECP_ would be reduced with respect to
the data reduction rules described by [17]. For _WECP_ , [17] have developed a
_bi-kernel_ of size at most $4^{k}$. The _bi-kernel_ is based on a general
problem that considers a subset of vertices annotated with integer weights as
input, in addition to the input of _WECP_. The general problem is as follows.

_Annotated weighted edge clique partition_ (_AWECP_) Input: A graph $G=(V,E)$,
a weight function on edges $w^{E}:E\rightarrow\mathbb{Z}_{>0}$, a nonnegative
integer $k$, a set of vertices $S\subseteq V$, and a weight function
$w^{S}:S\rightarrow\mathbb{Z}_{>0}$. Output: If one exists, a clique cover
$\mathcal{C}$ of $G$ such that (1) $|\mathcal{C}|\leq k$, (2) each edge $e\in
E$ appears in exactly $w^{E}(e)$ cliques of $\mathcal{C}$, and (3) each vertex
$x\in S$ appears in exactly $w^{S}(x)$ cliques of $\mathcal{C}$; otherwise
report _NO_.

When $S=\varnothing$, _AWECP_ reduces to the special case _WECP_. For the data
reduction rules that give rise to an instance of _AWECP_ from an instance of
_WECP_ , see Section 2 of [17]. We point out that a reduced instance of
_AWECP_ with respect to the data reduction rules of [17] does not contain any
isolated vertices.

Note that for any vertex $x\in S$, if the weight on the vertex $x$ is smaller
than the weight of all the edges incident on $x$, i.e., $w^{S}(x)<w^{E}(e)$
for all $e=\\{x,y\\}\in E$, then we immediately know that a given instance of
_AWECP_ is a _NO_ instance. Also, for any vertex $x\in S$, if the weight on
the vertex $x$ is larger than the sum of the weights of all the edges incident
on $x$, i.e., $w^{S}(x)>\sum_{e=\\{x,y\\}\in E}w^{E}(e)$, then we immediately
know that a given instance of _AWECP_ is a _NO_ instance.

Annotated-Weighted-Edge-Clique-Partition-
Search$(G,k,w^{E},S,w^{S},\mathcal{C},\mathcal{R})$: // Abbreviated
AWECPS$(G,k,w^{E},S,w^{S},\mathcal{C},\mathcal{R})$ 1. if $w^{E}(e)=0$ for all
$e\in E$ and $w^{S}(z)=0$ for all $z\in S$, then return $\mathcal{C}$ // cf.
step 1 _ECCS2_ Figure 4 2. select the _last_ edge $e=\\{x,y\\}$ from the _DEP_
of $G$ where $y\in N_{d}(x)$ and $w^{E}(e)>0$ // cf. step 2 _ECCS2_ Figure 4
3. for each $l\in R_{x}\cap R_{y}$ such that $\\{x,y\\}\not\subseteq C_{l}$ do
(a) if ’$e$ cannot be included’ in $C_{l}$, then go to the next iteration of
step 3 // Figure 8 (a) (b) include the edge $\\{x,y\\}$ in the clique $C_{l}$,
and update $\mathcal{R}$, $w^{E}$, $w^{S}$ // Figure 8 (b) (c)
$\mathcal{Q}\leftarrow\textbf{AWECPS}(G,k,w^{E},S,w^{S},\mathcal{C},\mathcal{R})$
(d) if $\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ (e) undo
changes done to $\mathcal{C}$, $\mathcal{R}$, $w^{E}$, and $w^{S}$ at step 3b
// Figure 8 (c) 4. if $k>0$, then (a) if ($x\in S$ and $w^{S}(x)=0$) or ($y\in
S$ and $w^{S}(y)=0$), then return $\varnothing$ (b) set $\mathcal{C}$ to
$\mathcal{C}\cup\\{\\{x,y\\}\\}$, and update $\mathcal{R}$, $w^{E}$, $w^{S}$
// Figure 8 (d) (c)
$\mathcal{Q}\leftarrow\textbf{AWECPS}(G,k-1,w^{E},S,w^{S},\mathcal{C},\mathcal{R})$
(d) if $\mathcal{Q}\neq\varnothing$, then return $\mathcal{Q}$ (e) undo
changes done to $\mathcal{C}$, $\mathcal{R}$, $w^{E}$, and $w^{S}$ at step 4b
// Figure 8 (e) 5. return $\varnothing$

Figure 7: A bounded search tree algorithm for _AWECP_ , denoted _AWECPS_.

Step 3a: 1. if $x\in S$ and $x\not\in C_{l}$ and $w^{S}(x)=0$, then report _’
$e$ cannot be included’_ 2. if $y\in S$ and $y\not\in C_{l}$ and $w^{S}(y)=0$,
then report _’ $e$ cannot be included’_ 3. for each $z\in
C_{l}\backslash\\{x,y\\}$ do • Let $e_{1}=\\{x,z\\}$ and $e_{2}=\\{y,z\\}$ (a)
if ($x\not\in C_{l}$ and $w^{E}(e_{1})=0$) or ($y\not\in C_{l}$ and
$w^{E}(e_{2})=0$), then report _’ $e$ cannot be included’_ 4. report _’ $e$
can be included’_

(a)

Step 3b: 1. execute the subroutine for step 3a of _ECCS2_ from Figure 5 2. for
each $z\in C_{l}\backslash\\{x,y\\}$ do (a) if $x_{l}=0$, then decrement
$w^{E}(e_{1})$ by $1$, where $e_{1}=\\{x,z\\}$ (b) if $y_{l}=0$, then
decrement $w^{E}(e_{2})$ by $1$, where $e_{2}=\\{y,z\\}$ 3. decrement
$w^{E}(e)$ by $1$ 4. if $x_{l}=0$ and $x\in S$, then decrement $w^{S}(x)$ by
$1$ 5. if $y_{l}=0$ and $y\in S$, then decrement $w^{S}(y)$ by $1$

(b)

Step 3e: 1. execute the subroutine for step 3b of _ECCS2_ from Figure 5 2. for
each $z\in C_{l}\backslash\\{x,y\\}$ do (a) if $x_{l}=0$, then increment
$w^{E}(e_{1})$ by $1$, where $e_{1}=\\{x,z\\}$ (b) if $y_{l}=0$, then
increment $w^{E}(e_{2})$ by $1$, where $e_{2}=\\{y,z\\}$ 3. increment
$w^{E}(e)$ by $1$ 4. if $x_{l}=0$ and $x\in S$, then increment $w^{S}(x)$ by
$1$ 5. if $y_{l}=0$ and $y\in S$, then increment $w^{S}(y)$ by $1$

(c)

Step 4b: 1. execute the subroutine for step 4a of _ECCS2_ from Figure 5 2.
decrement $w^{E}(e)$ by $1$ 3. if $x\in S$, then decrement $w^{S}(x)$ by $1$
4. if $y\in S$, then decrement $w^{S}(y)$ by $1$

(d)

Step 4e: 1. execute the subroutine for step 4d of _ECCS2_ from Figure 5 2.
increment $w^{E}(e)$ by $1$ 3. if $x\in S$, then increment $w^{S}(x)$ by $1$
4. if $y\in S$, then increment $w^{S}(y)$ by $1$

(e)

Figure 8: Subroutines of _AWECPS_ shown in Figure 7.

Figure 7 shows a bounded search tree algorithm for _AWECP_ , henceforth
referred as _AWECPS_. The subroutines for steps 3a, 3b, 3e, 4a, 4d of _AWECPS_
are described in Figure 8. _AWECPS_ extends the mechanism of building clique
cover employed by _ECCS2_. At every node of a search tree, _AWECPS_ extends a
clique cover if and only if the extension is (locally) consistent with the
weight functions $w^{E}$ and $w^{S}$.

_AWECPS_ treats the weight functions $w^{E}$ and $w^{S}$ as budgets for the
edges of $E$ and vertices of $S$ respectively. At every node of a search tree,
every edge $e$ has a budget $w^{E}(e)$, denoting how many more cliques the
edge $e$ can be included. Similarly, at every node of a search tree, every
vertex $z\in S$ also has a budget $w^{S}(z)$, denoting how many more cliques
the vertex $z$ can be included. For _AWECPS_ , we maintain the notions of
including an edge (or a vertex) in a clique (in this context covering an edge
$e$ by cliques could be used to denote including the edge $e$ in exactly
$w^{E}(e)$ distinct cliques).

Since both $w^{E}$ and $w^{S}$ are positive integer weight functions, if
budgets of all edges of $E$ and budgets of all vertices of $S$ can be spent
exactly at a node of a search tree of _AWECPS_ with at most $k$ cliques, then
the given instance of _AWECP_ is a _YES_ instance, and step 1 would return a
corresponding clique cover. Step 2 of _AWECPS_ essentially select the same
edge $e=\\{x,y\\}$ as would be selected by step 2 of _ECCS2_ , except _AWECPS_
selects the same edge $e$ repeatedly until its budget is entirely exhausted,
i.e., $w^{E}(e)=0$. Steps 3a and 4a enforce that including an edge
$e=\\{x,y\\}$ to a clique must be within the budgets of the corresponding
edges of $E$ and within the budgets of corresponding vertices of $S$. Rest of
the steps of _AWECPS_ are self-explanatory.

Turning to the subroutines of _AWECPS_ in Figure 8, we see that the subroutine
for step 3a simply makes sure that every new vertex or new edge that would be
included in the clique $C_{l}$ (as a result of including the edge
$e=\\{x,y\\}$ in the clique $C_{l}$) has the budget to do so. Rest of the
subroutines make sure that the budgets of the edges of $E$ and the vertices of
$S$ are updated accordingly when we include (resp. exclude) an edge $e$ in
(resp. from) a clique. Note that (for brevity) the subroutines of _ECCS2_ are
invoked from the subroutines of _AWECPS_.

The proof correctness of _ECCS2_ (Lemma 5.1) can be adapted to obtain a proof
of correctness for _AWECPS_ (see Appendix B). Thus we conclude the following.

######  Lemma 5.9.

Algorithm _AWECPS_ correctly solves the parameterized problem _AWECP_.

######  Lemma 5.10.

The number of nodes in a search tree of _AWECPS_ is at most $2^{\beta k\log
k}$.

###### Proof.

It is straightforward to see that the depth of a search tree of _AWECPS_ is
bounded by $\beta k$. Let $w$ be the maximum edge weight in an instance of
_AWECP_ , i.e., $w=\max_{e\in E}\\{w^{E}(e)\\}$. Then, number of branches at
any node of a search tree of _AWECPS_ is bounded by
$\min\\{k,\binom{d+1}{2}w\\}\leq k$: this follows from similar arguments
presented for _ECCS2_ in Lemma 5.5. Therefore, the number of nodes in a search
tree of _AWECPS_ is at most $k^{\beta k}=2^{\beta k\log k}$. ∎

Considering time needed for data reduction, Theorem 1.6 follows from Lemma
5.10 and Proposition 2.20.

For an instance of _WECP_ , the algorithm of [17] takes
$2^{O(k^{3/2}w^{1/2}\log(k/w))}n^{O(1)}$ time, where $w$ is the maximum edge
weight of the instance. For $\beta=o((\sqrt{kw}\log(k/w))/\log k)$, _AWECPS_
improves the running time by a factor of
$\frac{2^{O(k^{3/2}w^{1/2}\log(k/w))}}{2^{\beta k\log
k}}=2^{O(k(\sqrt{kw}\log(k/w)-\beta\log k))}=2^{O(k^{3/2}w^{1/2}\log(k/w))}$.
This is a significant improvement, considering the fact that $\beta$ is
bounded by the graph size, while $k$ and $w$ could be arbitrarily large. For
nontrivial instances of _WECP_ , $k$ could be up to (but not including) $mw$.

On the other hand, if the maximum edge weight $w$ is bounded by some constant,
then for $\beta=o(\sqrt{k})$, _AWECPS_ is $\frac{2^{O(k^{3/2}\log
k)}}{2^{\beta k\log k}}=2^{O(k\log k(\sqrt{k}-\beta))}=2^{O(k^{3/2}\log k)}$
times faster than the algorithm of [17].

###  5.4 Exact Weighted Clique Decomposition

The data reduction rules of _WECP_ described by [17] are also applicable to
any instance of _EWCD_. Consequently, we have a _bi-kernel_ for _EWCD_ with
$4^{k}$ vertices. The _bi-kernel_ is based on a general problem that considers
a subset of vertices annotated with positive weights as input, in addition to
the input of _EWCD_. The general problem is as follows.

_Annotated exact weighted clique decomposition_ (_AEWCD_) Input: A graph
$G=(V,E)$, a weight function on edges $w^{E}:E\rightarrow\mathbb{R}_{>0}$, a
nonnegative integer $k$, a set of vertices $S\subseteq V$, and a weight
function $w^{S}:S\rightarrow\mathbb{R}_{>0}$. Output: If one exists, a clique
cover $\mathcal{C}$ of $G$ and positive weight $\gamma_{i}$ for every clique
$C_{i}\in\mathcal{C}$ such that (1) $|\mathcal{C}|\leq k$, (2) for each edge
$e=\\{x,y\\}\in E$, $\sum_{\\{x,y\\}\in
C_{i},C_{i}\in\mathcal{C}}\gamma_{i}=w^{E}(e)$, and (3) for each vertex $x\in
S$, $\sum_{x\in C_{i},C_{i}\in\mathcal{C}}\gamma_{i}=w^{S}(x)$; otherwise
report _NO_.

Note that when $S=\varnothing$, _AEWCD_ reduces to the special case _EWCD_. If
the weight functions are integer valued and weight on each of the cliques are
forced to be $1$, then _AEWCD_ is equivalent to _AWECP_.

Let $\mathcal{C}$ be a clique cover of $G$. If $\mathcal{C}$ contains at most
$k$ cliques, then, for an instance $(G,k,w^{E},S,w^{S})$ of _AEWCD_ , the
following linear program (LP) would compute weights of the cliques
$\gamma=\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{|\mathcal{C}|}\\}$ in
$\mathcal{C}$ (if the LP is feasible). Note that the objective function of the
LP is a constant, i.e., an LP solver would only need to find a feasible
solution $\gamma=\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{|\mathcal{C}|}\\}$,
if one exists.

$\begin{array}[]{lll}\text{minimize}&\displaystyle\sum\limits_{i:C_{i}\in\mathcal{C}}0\times\gamma_{i}\\\
\text{subject to}&\displaystyle\sum\limits_{i:\\{x,y\\}\in
C_{i},C_{i}\in\mathcal{C}}\gamma_{i}=w^{E}(e),&\text{for all }e=\\{x,y\\}\in
E\\\ &\displaystyle\sum\limits_{i:x\in
C_{i},C_{i}\in\mathcal{C}}\gamma_{i}=w^{S}(x),&\text{for all }x\in S\\\
&\gamma_{i}\geq 0,&\text{for all }i:C_{i}\in\mathcal{C}\end{array}$ (A)

Annotated-Exact-Weighted-Clique-Decomposition-
Search$(G,k,\mathcal{C},\mathcal{R})$: // Abbreviated
AEWCDS$(G,k,\mathcal{C},\mathcal{R})$ 1. if $\mathcal{C}$ covers edges of $G$,
then (a) for $\mathcal{C}$ solve the LP (A) (b) if (A) is feasible, then
return $(\mathcal{C},\gamma)$ (c) else return $(\varnothing,\varnothing)$ 2.
select the _last_ uncovered edge $\\{x,y\\}$ from the _DEP_ of $G$ where $y\in
N_{d}(x)$ 3. for each $l\in R_{x}\cap R_{y}$ such that $\\{x,y\\}\not\subseteq
C_{l}$ do (a) include the edge $\\{x,y\\}$ in the clique $C_{l}$ and update
$\mathcal{R}$ // Figure 5 (a) (b) mark the edge $\\{x,y\\}$ as covered (c)
$(\mathcal{Q},\gamma)\leftarrow\textbf{AEWCDS}(G,k,\mathcal{C},\mathcal{R})$
(d) if $\mathcal{Q}\neq\varnothing$, then return $(\mathcal{Q},\gamma)$ (e)
mark the edge $\\{x,y\\}$ as uncovered (f)
$(\mathcal{Q},\gamma)\leftarrow\textbf{AEWCDS}(G,k,\mathcal{C},\mathcal{R})$
(g) if $\mathcal{Q}\neq\varnothing$, then return $(\mathcal{Q},\gamma)$ (h)
undo changes done to $\mathcal{C}$ and $\mathcal{R}$ at step 3a // Figure 5
(b) 4. if $k>0$, then (a) set $\mathcal{C}$ to
$\mathcal{C}\cup\\{\\{x,y\\}\\}$ and update $\mathcal{R}$ // Figure 5 (c) (b)
mark the edge $\\{x,y\\}$ as covered (c)
$(\mathcal{Q},\gamma)\leftarrow\textbf{AEWCDS}(G,k-1,\mathcal{C},\mathcal{R})$
(d) if $\mathcal{Q}\neq\varnothing$, then return $(\mathcal{Q},\gamma)$ (e)
mark the edge $\\{x,y\\}$ as uncovered (f)
$(\mathcal{Q},\gamma)\leftarrow\textbf{AEWCDS}(G,k-1,\mathcal{C},\mathcal{R})$
(g) if $\mathcal{Q}\neq\varnothing$, then return $(\mathcal{Q},\gamma)$ (h)
undo changes done to $\mathcal{C}$ and $\mathcal{R}$ at step 4a // Figure 5
(d) 5. return $(\varnothing,\varnothing)$

Figure 9: A bounded search tree algorithm for _AEWCD_ , denoted _AEWCDS_.

Figure 9 shows a bounded search tree algorithm for _AEWCD_ , henceforth
referred to as _AEWCDS_. We reuse the subroutines of _ECCS2_ for _AEWCDS_ :
steps 3a, 3h, 4a, 4h of _AEWCDS_ are identical to the steps 3a, 3d, 4a, 4d of
_ECCS2_ described in Figure 5. We assume _AEWCDS_ has access to the weight
functions at step 1 of any node of a search tree. Whenever a clique cover
$\mathcal{C}$ of $G$ is found at a node, we check the feasibility of
$\mathcal{C}$ for the instance $(G,k,w^{E},S,w^{S})$, by solving the LP (A).
If (A) is feasible, then the clique cover $\mathcal{C}$ and a corresponding
solution $\gamma=\\{\gamma_{1},\gamma_{2},\ldots\\}$ of (A) is returned at
step 1.

For _AEWCD_ , we explicitly distinguish between covering an edge by a clique
and including an edge in a clique. An edge can be included in many cliques,
without being identified as covered. If an edge $\\{x,y\\}$ is marked as
covered (steps 3b, 4b) at a node $u^{T}$ of a search tree $T$, then the
corresponding descendent nodes (steps 3c, 4c) of $u^{T}$ in $T$ would not
select the edge $\\{x,y\\}$ as uncovered at step 2. On the other hand, if an
edge $\\{x,y\\}$ is marked as uncovered (steps 3e, 4e) at a node $u^{T}$ of a
search tree $T$, then the corresponding descendent nodes (steps 3f, 4f) of
$u^{T}$ in $T$ may select the edge $\\{x,y\\}$ as uncovered at step 2.

$a$$b$$c$$d$$101$$2$$1$$2$$1$$1$

Figure 10: An example graph $G$ with positive weights on edges. For $k=3$, $G$
with the weights on the edges (and $S=\varnothing$) is a _YES_ instance of
_AEWCD_. Cliques of a corresponding clique cover $\mathcal{C}$ of $G$, and
feasible weights on the cliques are as follows: $C_{1}=\\{a,b,c,d\\}$,
$C_{2}=\\{a,b,c\\}$, $C_{3}=\\{a,b\\}$, $\gamma_{1}=1$, $\gamma_{2}=1$,
$\gamma_{3}=99$.

For _AEWCDS_ , the branches at steps 3e-3g and 4e-4g are crucial: an edge
$e=\\{x,y\\}$ may need to be included in many cliques so that the weight
$w(e)$ can be matched with the weights of the neighbouring edges of $e$. To
see this, consider the complete graph $K_{4}$ and weights on the edges as
shown in Figure 10. For $k=3$, the instance of _AEWCD_ is a _YES_ instance. A
corresponding clique cover $\mathcal{C}$ of $G$ consists of following cliques:
$C_{1}=\\{a,b,c,d\\}$, $C_{2}=\\{a,b,c\\}$, $C_{3}=\\{a,b\\}$. Corresponding
feasible weights on the cliques are $\gamma_{1}=1$, $\gamma_{2}=1$, and
$\gamma_{3}=99$. WLOG, we can assume that the edge $e=\\{a,b\\}$ is the last
edge in the _DEP_ of $G$. The edge $e$ needs to appear in all three cliques of
$\mathcal{C}$. Therefore, we need to make sure that an edge is included in a
sufficient number of cliques (at most $k$), so that we have correct
combination of cliques for the edges that are chosen later from the edge
permutation.

The way we have described _AEWCDS_ (in Figure 9) is merely for ease of
reading. An equivalent (in terms of correctness) description would have a
subroutine consisting of step 3 and step 4, excluding steps 3b, 3e-3g, 4b,
4e-4g. Now, instead of step 3 and 4, we can simply call the subroutine once,
after marking the edge $\\{x,y\\}$ as covered, and if the call fails, then we
can call the subroutine once, after marking the edge $\\{x,y\\}$ as uncovered.
The search trees corresponding to the equivalent description are likely to be
smaller for many instances of _AEWCD_.

[7] have described an LP based algorithm for _AEWCD_ , called _CliqueDecomp-
LP_. The LP used by _CliqueDecomp-LP_ has $k$ variables and at most $4k^{2}$
constraints. In contrast, the LP (A) has at most $k$ variables and at most
$m+|S|\leq m+n$ constraints. At every iteration, _CliqueDecomp-LP_ selects a
permutation matrix $P\in\\{0,1\\}^{2k\times k}$. For every such permutation
matrix $P$, _CliqueDecomp-LP_ needs to solve the corresponding LP, regardless
of whether $P$ correspond to a clique cover of the graph or not. For a single
permutation matrix $P$, _CliqueDecomp-LP_ may need to solve the LP up to $2k$
times. Therefore, _CliqueDecomp-LP_ may need to solve the LP up to
$2^{2k^{2}}\times 2k$ times, in the worst case. In contrast, _AEWCDS_ solves
the LP (A) (at step 1) only when $\mathcal{C}$ is a clique cover of the graph.
In most cases, for _YES_ instances of _AEWCD_ , the number of clique covers of
a graph with at most $k$ cliques is significantly smaller than
$2^{2k^{2}}\times 2k$.

A correctness proof for _AEWCDS_ can be obtained similarly as the correctness
proof for _AWECPS_ (Lemma 5.9). A minor modification would be required for the
base case of induction. In the base case, i.e., $k=1$, for some constant $q$,
we would have $w^{E}(e)=q$ for all $e\in E$ and $w^{S}(x)=q$ for all $x\in S$.
Rest of the proof would be analogous. Thus we have the following.

######  Lemma 5.11.

Algorithm _AEWCDS_ correctly solves the parameterized problem _AEWCD_.

######  Lemma 5.12.

The number of nodes in a search tree of _AEWCDS_ is at most $2^{\beta k(1+\log
k)}$.

###### Proof.

The depth of a seach tree of _AEWCDS_ is bounded by $\beta k$. At step 3 of
any node of the search tree $R_{x}\cap R_{y}\leq k$. If $R_{x}\cap R_{y}=k$,
then there is no branch at step 4 of the node. Therefore, number of branches
at any node of a search tree of _AEWCDS_ is at most $2k$. It follows that the
number of nodes in a search tree of _AEWCDS_ is at most $(2k)^{\beta
k}=2^{\beta k(1+\log k)}$. ∎

For _AEWCDS_ , the LP (A) would have at most $k$ variables, and at most $m+n$
constraints. For nontrivial instances of _AEWCD_ , we can assume $k<m$.
Therefore, (A) is solvable in $O(k^{3}L)$ time, where $L$ is the number of
bits needed to encode the LP [6, 44]. Since $n\leq 4^{k}$, running time of
_AEWCDS_ is $2^{O(\beta k\log k)}L$. Now, considering time needed for data
reduction, Theorem 1.7 follows from Proposition 2.20.

For the cases when all the weights are restricted to integers (including the
weights on the cliques), [7] have described an integer partitioning based
algorithm called _CliqueDecomp-IP_. _CliqueDecomp-IP_ requires maintaining
$(w+1)^{k}$ weight matrices in the worst case, where $w$ is the maximum edge
weight. Consequently, space requirement of _CliqueDecomp-IP_ could be
prohibitive for many _AEWCD_ instances even if the instances are solvable in a
reasonable amount of time. For these cases, we point out that instead of
solving the LP (A), at step 1 of _AEWCDS_ , one can search for feasible set of
weights $\gamma$, by enumerating at most $w^{k}=2^{k\log w}$ choices.
Therefore, _AEWCD_ instances restricted to integer weights are solvable in
$2^{O(k(\beta\log k+\log w))}n^{O(1)}$ time, using $O(m+k\Delta)$ space (Lemma
5.2).

_CliqueDecomp-LP_ and _CliqueDecomp-IP_ both require enumerating $2^{2k^{2}}$