Edge Clique Partition and Cover Beyond Independence

In this paper, we consider simple undirected graphs and refer to the textbook by Diestel [15] for notions that are not defined here. We use $V(G)$ and $E(G)$ to denote the set of vertices and the set of edges of $G$, respectively. We use $n$ and $m$ to denote the number of vertices and edges in $G$, respectively, unless this creates confusion. For a vertex subset $X\subseteq V(G)$, we use $G[X]$ to denote the subgraph of $G$ induced by the vertices of $X$ and $G-X$ to denote $G[V(G)\setminus X]$. For a vertex $v\in V(G)$, we write $N_G(v)=\{u\in V(G)\mid uv\in E(G)\}$ to denote the open neighborhood of $v$, and we use $N_G[v]=N_G(v)\cup \{v\}$ for the closed neighborhood. For $X\subseteq V(G)$, $N_G(X)=\left({\bigcup }_{v\in X}{N}_G(v)\right)\setminus X$ and $N_G[X]={\bigcup }_{v\in X}{N}_G[v]$. We denote by $d_G(v)=|N_G(v)|$ the degree of a vertex $v$; a vertex of degree zero is isolated. The minimum degree is denoted by $\delta (G)$. A graph $G$ is $d$-degenerate for an integer $d\ge 0$ if $\delta (H)\le d$ for any subgraph $H$ of $G$. By $\mathrm{dg}(G)$ we denote the degeneracy of $G$, i.e. minimum $d$ for which $G$ is $d$-degenerate. A graph $H$ is a minor of $G$ if the graph isomorphic to $H$ can be obtained from $G$ by vertex/edge deletions and edge contractions. A graph $G$ is $H$-minor-free if $H$ is not a minor of $G$. A set of pairwise adjacent vertices is called a clique, and a set of pairwise non-adjacent vertices is independent. The maximum size of an independent set in $G$ is denoted by $\alpha (G)$, and the maximum size of a clique in $G$ is denoted by $\omega (G)$. A vertex $v\in V(G)$ is said to be simplicial if $N_G[v]$ is a clique, and we say that a clique $K$ is simplicial if $K$ equals $N_G[v]$ for a simplicial vertex $v$. An edge $uv\in E(G)$ is covered by a clique $K$ if $u,v\in K$. A set $𝒦$ of cliques is a vertex clique cover if for every $v\in V(G)$, there is $K\in 𝒦$ such that $v\in K$. We say that $𝒦$ is an edge clique cover if for every $uv\in E(G)$, there is $K\in 𝒦$ with $u,v\in K$, and $𝒦$ is an edge clique partition if $𝒦$ is an edge clique cover such that any two cliques in $𝒦$ has at most one common vertex. We use $\mathrm{ecc}(G)$ and $\mathrm{ecp}(G)$ to denote the minimum size of an edge clique cover and partition of $G$, respectively.

We refer to the textbook by Cygan et al. [12] for an introduction to the area. We remind that a parameterized problem is a language $L\subseteq {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$ where ${\mathrm{\Sigma }}^{\ast }$ is a set of strings over a finite alphabet $\mathrm{\Sigma }$. An input of a parameterized problem is a pair $(x,k)$ where $x$ is a string over $\mathrm{\Sigma }$ and $k\in \mathbb{N}$ is a parameter. A parameterized problem is fixed-parameter tractable (or $\mathrm{𝖥𝖯𝖳}$) if it can be solved in $f(k)\cdot {|x|}^{𝒪(1)}$ time for some computable function $f$. The complexity class $\mathrm{𝖥𝖯𝖳}$ contains all fixed-parameter tractable parameterized problems. We use the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi, and Zane [33] to obtain conditional computational lower bounds. Under ETH, there is a positive real $\delta$ such that $3$-Satisfiability ($3$-SAT) with $n$ variables and $m$ clauses cannot be solved in $2^{\delta n}\cdot {(n+m)}^{𝒪(1)}$ time; in particular, $3$-SAT cannon be solved in time subexponential in $n$.

We need the following auxiliary results about edge clique covers and independent sets. First, we observe that $\alpha (G)$ gives a lower bound for $\mathrm{ecc}(G)$ and $\mathrm{ecp}(G)$.

Notice that the absence of isolated vertices is crucial for the lower bound of $\mathrm{ecc}(G)$ and $\mathrm{ecp}(G)$. We also remark that that excluding isolated vertices is essential for our algorithmic results for ECP/$\alpha$ and ECP/$\alpha$.

The following lemma plays the most fundamental role for ECC/$\alpha$ and ECP/$\alpha$.

As an edge clique partition is an edge clique cover, it is sufficient to show the claim when $𝒞$ is an edge clique cover of size at most $\alpha (G)+k$. Let $X$ be a maximum independent set of $G$. Clearly, any clique of $G$ contains at most one vertex of $X$ by independence. Because $G$ has no isolated vertices, each vertex $v\in X$ is included in at least one clique of $𝒞$. Furthermore, $v$ is simplicial if $v$ is included in a single clique of $𝒞$. Since $|𝒞|\le \alpha (G)+k$, we obtain that at least $\alpha (G)-k$ vertices of $X$ are contained in exactly one clique of $𝒞$. Therefore, at least $\alpha (G)-k$ vertices of $X$ are simplicial, and at least $\alpha (G)-k$ cliques of $𝒞$ are simplicial. This means that at most $k$ vertices of $X$ are non-simplicial and proves (i). To show (ii), note that because at least $\alpha (G)-k$ cliques of $𝒞$ are simplicial, at most $2k$ cliques could be non-simplicial. This concludes the proof. $◀$

In particular, this lemma implies that ECC/$\alpha$ and ECP/$\alpha$ are trivial for $k=0$.

We use Lemma 7 to argue that for graphs admitting an edge clique cover of bounded size, we can compute $\alpha (G)$.

We remark that our algorithm from Lemma 9 can be easily modified to output an independent set of maximum size.

Let $G$ be a graph without isolated vertices. We compute the set $𝒮$ of all simplicial cliques and select a simplicial vertex in each simplicial clique. Denote by $X$ the obtained set of simplicial vertices. It is well-known that $G$ has a maximum independent set $U$ such that $X\subseteq U$. This implies that $\alpha (G)=\alpha (H)+|𝒮|$ where $H=G[W]$ for $W=V(G)\setminus {\bigcup }_{S\in 𝒮}S$. If $G$ admits an edge clique partition of size at most $\alpha (G)+k$ then, by Lemma 7, at most $2k$ cliques of the partition are non-simplicial. Notice that the edges of $H$ can be covered only by non-simplicial cliques. Therefore, $H$ should have an edge clique partition of size at most $2k$. We apply the algorithm from Proposition 11 to $H$ and check in $2^{𝒪(k^{3/2}\log k)}\cdot n^{𝒪(1)}$ time whether $H$ has an edge clique partition of size at most $k^{\prime }=2k$. If the algorithm reports that such a partition does not exist then we conclude that $(G,k)$ is a no-instance of ECP/$\alpha$. Otherwise, the algorithm outputs an edge clique partition $𝒞$ of size at most $2k$. Given this partition, we use the algorithm from Lemma 9 to compute $\alpha (H)$ in $2^{𝒪(k)}\cdot n^{𝒪(1)}$ time. Then we output $\alpha (G)=\alpha (H)+|𝒮|$. Because simplicial cliques can be found in polynomial time, for example, by the algorithm of Kloks, Kratsch, and Müller [35], the overall running time is $2^{𝒪(k^{3/2}\log k)}\cdot n^{𝒪(1)}$. This concludes the proof. $◀$

By the following claim, which is proved by making use of Proposition 10, we show that all cliques of size at least $6k+1$ that belong to any solution to an instance of ECP/$\alpha$ can be found in polynomial time.

Now we are ready to show Theorem 1 which we restate.

Let $(G,k)$ be an instance of ECP/$\alpha$. As pointed out in Observation 8, the problem is trivial if $k=0$. Hence, we assume that $k\ge 1$. First, we call the algorithm from Lemma 12 for $(G,k)$. The algorithm either computes $\alpha (G)$ or correctly reposts that $(G,k)$ is a no-instance of ECP/$\alpha$. If we obtain a no-instance, we report it and stop. We assume from now on that this is not the case, and the value $\alpha (G)$ is known to us.

In the following step, we construct a partial solution $𝒦$ using the algorithm from Lemma 13. This algorithm works in polynomial time and either outputs a set $𝒦$ of cliques of $G$ such that

1. (i)

   each clique $C\in 𝒦$ is included in any edge clique partition of $G$ of size at most $\alpha (G)+k$,

2. (ii)

   for every edge clique partition $𝒞$ of $G$ of size at most $\alpha (G)+k$ and any clique $C\in 𝒞$ of size at least $6k+1$, $C\in 𝒦$,

3. (iii)

   for any two distinct cliques $C_1,C_2\in 𝒦$, $|C_1\cap C_2|\le 1$,

or correctly concludes that $(G,k)$ is a no-instance. If the algorithm returns that $(G,k)$ is a no-instance then we return the answer and stop. We also conclude that $(G,k)$ is a no-instance if $|𝒦|>\alpha (G)+k$. From now on, we assume that $𝒦$ is a set of cliques that are included in any edge clique partition of size at most $\alpha (G)+k$ such that any two distinct cliques of $𝒦$ do not cover the same edge.

Next, we list all distinct simplicial cliques of $G$ and denote by $𝒮$ the set of simplicial cliques. We say that a clique $S\in 𝒮$ is broken in a (potential) solution to $(G,k)$, if $S$ is not included in the edge clique partition. Notice that if $S$ is a broken simplicial clique, then at least two distinct non-simplicial cliques should be used to cover the edges incident to the corresponding simplicial vertex. By Lemma 7, any edge clique partition of size at most $\alpha (G)+k$ can include at most $2k$ non-simplicial cliques. Thus, for any solution, the number of broken simplicial cliques should not exceed $k$. Our algorithm identifies the set $ℬ$ of broken cliques in a solution.

We initialize $ℬ$ using the following branching algorithm. Consider the auxiliary graph $H$ whose nodes are simplicial cliques. Two distinct nodes $S_1,S_2\in 𝒮$ are adjacent in $H$ if and only if $|S_1\cap S_2|\ge 2$. Observe that if $|S_1\cap S_2|\ge 2$ then either $S_1$ or $S_2$ should be broken in a solution. Thus, the set of broken cliques in any solution should be a vertex cover of $H$ of size at most $k$. We can decide in $𝒪(2^k\cdot n)$ time whether $H$ has a vertex cover of size at most $k$ and, moreover, we can list all inclusion minimal vertex covers using the standard recursive branching algorithm for Vertex Cover (see [12]). If $H$ has no vertex cover of size at most $k$, we report that $(G,k)$ is a no-instance of ECP/$\alpha$ and stop. Assume that this is not the case. Then we obtain the list $ℒ$ of all inclusion minimal vertex covers of $H$ of size at most $k$. Notice that $|ℒ|\le 2^k$. Then if $(G,k)$ admits an edge clique partition of size at most $\alpha (G)+k$, there is $L\in ℒ$ such that $L\subseteq ℬ$ – the set of broken cliques in $𝒞$. To initialize $ℬ$, we branch on all possible choices of $L\in ℒ$ and set $ℬ:=L$. If we find a solution for some choice of $L$, we output it and stop. Otherwise, if we fail to find an edge clique partition of size at most $\alpha (G)+k$ for any initial selection of $ℬ$, we report that $(G,k)$ is a no-instance of ECP/$\alpha$.

From now on, we assume that the initial choice of $ℬ$ is fixed from one of at most $2^k$ choices given by $ℒ$. We update $ℬ$ by adding cliques that get broken because of the cliques in the partial solution. Notice that if $S\notin 𝒦$ is a simplicial clique covering the same edge as one of the cliques in the partial solution, then $S$ has to be broken. This implies the correctness of the following step:

• $\mathrm{■}$

  For every simplicial clique $S\notin ℬ\cup 𝒦$ such that $|S\cap K|\ge 2$ for some $K\in 𝒦$, set $ℬ:=ℬ\cup \{S\}$.

• $\mathrm{■}$

  If $|ℬ|>k+1$ then stop and discard the current choice of $L$.

Assume that the algorithm does not stop in this step. We call the set $ℬ$ obtained in this step a base set of broken cliques.

We say that a simplicial clique $S$ is free if $S\notin ℬ\cup 𝒦$, and we use $ℱ$ to denote the set of free cliques. Lemma 13 and the construction of $ℬ$ imply the following property.

This means that no edge of $G$ is covered by two cliques of $ℱ\cup 𝒦$. In the final step of our algorithm, we try to extend $ℱ\cup 𝒦$ to an edge clique partition of $G$ of size at most $\alpha (G)+k$. If we fail, then we recurse by including one of the free cliques to the set of broken cliques. Formally, we use the subroutine Extend$(ℱ,ℬ)$ in Algorithm 1 which either finds a solution extending $𝒦$, such that all cliques in $ℬ$ are broken, or discards the current choice of $ℱ$ and $ℬ$.

The description of the algorithm is finished. To argue correctness, observe that in each recursive call of the algorithm, we increase the size of $ℬ$ and stop if $|ℬ|>k$ in line 2. This means that Extend$(ℱ,ℬ)$ is finite. If this subroutine outputs a set of cliques ${𝒞}^{\ast }$ then it is a valid edge partition of $G$. First, because of Claim 14, no two cliques intersect. Second, the cover $𝒞$, constructed by the algorithm from Proposition 11 in line 5, outputs an edge clique partition for the edges which are not covered by the cliques of $ℱ\cup 𝒦$. Since we verify that $|{𝒞}^{\ast }|\le \alpha (G)+k$ in line 7, if the algorithm outputs some ${𝒞}^{\ast }$ then it is a valid solution to $(G,k)$. Thus, we have to show that if $(G,k)$ is a yes-instance of ECP/$\alpha$, then the algorithm necessarily finds a solution. For this, we show the following claim.

To complete the correctness proof, observe that if $(G,k)$ is a yes-instance of ECP/$\alpha$ then there is $L\in ℒ$ such that every clique of $L$ is broken in a solution. Then for the base set of broken cliques $ℬ$ constructed for $L$, each clique of $ℬ$ should be broken. By Claim 15, Extend$(ℱ,ℬ)$ called for this $ℬ$ and the corresponding set of free cliques $ℱ$ should output an edge clique partition of size at most $\alpha (G)+k$. This completes the correctness proof.

We conclude the proof with a claim explaining the running time bound.

The proof is complete. $◀$

In the conclusion of this section, we remark that the algorithm of Proposition 11 is a bottleneck for the running time of our algorithm for ECP/$\alpha$. More precisely, given an algorithm solving ECP in time $f(k)\cdot n^{𝒪(1)}$, the running time of our algorithm is $k^{𝒪(k)}f(2k)\cdot n^{𝒪(1)}$. Furthermore, consider the graph $G^{\prime }$ obtained from a graph $G$ by adding a pendent neighbor to each vertex of $G$. Since $\mathrm{ecp}(G^{\prime })=\alpha (G^{\prime })+\mathrm{ecp}(G)$, a faster algorithm for ECP/$\alpha$ would improve the algorithm of Proposition 11.