Graph Coloring Below Guarantees via Co-Triangle Packing

In the guarantee parameterization paradigm, we reformulate problems by first identifying classes of instances that are trivially solvable – typically because a solution is guaranteed to exist – and then parameterize general instances by their distance from these “easy” cases. See [13] for a survey of this area.

In the context of coloring graphs with $n$ nodes, observe that the $n$-Coloring problem is trivial, because we can obtain a proper coloring by assigning each vertex a distinct color. The framework of below-guarantee parameterization described above then motivates studying the $(n-k)$-Coloring problem, also referred to as Dual Coloring, where the parameter $k$ captures how many colors we are trying to “save” compared to the trivial coloring using different colors for all vertices. The Dual Coloring problem has been influential in parameterized complexity, with its study in [7] introducing the concept of crown reductions, by now a basic technique in the field of kernelization [10, Chapter 4]. Given an $n$-node instance $G$ of Dual Coloring and any constant $\epsilon >0$, [17] showed that in polynomial time one can kernelize the instance to a graph $G^{\prime }$ on $(2+\epsilon )k$ vertices such that the answer to the Dual Coloring problem is the same on $G$ and $G^{\prime }$, for sufficiently large $k$ in terms of $\epsilon >0$. Combining this kernelization with existing $2^n\mathrm{poly}(n)$ time algorithms for graph coloring [5], we immediately recover a $O^{\ast }(4^{(1+\epsilon )k})$ time algorithm for Dual Coloring for any constant $\epsilon >0$, where we write $O^{\ast }(f(k))$ to denote $f(k)\mathrm{poly}(n)$. Without going through this kernelization, one can also use the algorithms of [12] to solve Dual Coloring directly in $O^{\ast }(4^k)$ time. We improve upon this result:

Let us mention a closely related problem called $(n-k)$-Set Cover. In this problem, we are given a family $ℱ$ of subsets of $[n]$, and are tasked with determining if there exist $(n-k)$ sets from $ℱ$ whose union is $[n]$. Very recently, Alferov et al. [2] showed that $(n-k)$-Set Cover can be solved in $O^{\ast }(2^{3k/2}|ℱ|)$ time. Even though the $(n-k)$-Coloring problem can be cast as an instance of $(n-k)$-Set Cover, where $ℱ$ is the collection of all independent vertex sets of the graph, this result of [2] does not imply an $O^{\ast }(2^{3k/2})$ time algorithm for $(n-k)$-Coloring, because $ℱ$ can have exponentially many sets in $n$. The dynamic programming approach used in the algorithm of [2] appears to inherently require this runtime dependence on $|ℱ|$ even when the sets $ℱ$ can be implicitly described as in $(n-k)$-Coloring, so that Theorem 1 is not directly implied by this previous work. However, we note it seems plausible that one could combine the ideas of [2] with the subset convolution arguments of [4] to obtain fast algorithms for Dual Coloring as well, and recover Theorem 1.

Given a graph $G$, we let $\overline{G}$ denote its complement graph, which has the same vertex set as $G$, but an edge $\{u,v\}$ if and only if $u$ and $v$ are distinct, non-adjacent nodes in $G$. Let $\omega =\omega (G)$ denote the size of the maximum clique in $G$. Let $\overline{\mu }=\mu (\overline{G})$ denote the size of the maximum matching in the complement $\overline{G}$. Then we have the following structural parameter-based guarantee for coloring $G$.

Let $M$ be a maximal matching in $\overline{G}$. By definition, $|M|\le \overline{\mu }$. By maximality of $M$ in $\overline{G}$, the vertices that are not incident to any edge in $M$ form an independent set in $\overline{G}$. Thus the set $C$ of vertices outside $M$ form a clique in $G$, so $|C|\le \omega$. We color $G$ as follows. For each edge in $M$, we assign a unique color to both of its endpoints, and we assign distinct new colors to all vertices in $C$. In total, we use at most $(\omega +\overline{\mu })$ colors. By construction this coloring is proper, which proves the claim. $◀$

Note that in any graphs with $n$ vertices, we always have $\left(\omega +\overline{\mu }\right)\le n.$ This is because if we take a clique $C$ in $G$ of size $\omega$ and a matching $M$ in $\overline{G}$ of size $\overline{\mu }$, then by definition each edge of $M$ is incident to at least one distinct vertex outside of $C$, which forces $n\ge |C|+|M|=\left(\omega +\overline{\mu }\right)$. Thus the guarantee of Observation 2 is stronger than the trivial fact that any graph with $n$ vertices always has a proper coloring using $n$ colors.

In the same way this latter observation motivated the Dual Coloring problem, it is natural to ask if we can obtain efficient algorithms while parameterizing below the stronger guarantee provided by Observation 2. We prove that this is indeed possible.

The key ideas behind Theorems 1 and 3 are sketched below; see Section 1.1 for more details. We first greedily compute a maximal packing of co-triangles $\overline{K_3}$ (independent triplets). If the packing holds many co-triangles, saving two colors per co-triangle already yields the desired proper coloring. Otherwise, the packing’s vertices form a small co-triangle modulator $S$, whose deletion results in a $\overline{K_3}$-free graph. In the latter case, we extend the randomized procedure of Gutin et al. [12], to show that we can solve the desired coloring problem in $O^{\ast }(2^{|S|})$ time.

We also note that algorithms which are fixed-parameter tractable with respect to $k$ are unlikely to exist for $(\omega -k)$-Coloring and $(\overline{\mu }-k)$-Coloring, so that combining $\omega$ and $\overline{\mu }$ together in Theorem 3 appears to be necessary in order to achieve efficient parameterized algorithms with respect to these parameters. For the former, this is because 3-Coloring is NP-hard in planar graphs [11]. Since a planar graph does not have a clique of size five, this means that assuming $\text{P}\ne \text{NP}$ we cannot hope to solve $(\omega -k)$-Coloring in $f(k)\mathrm{poly}(n)$ time for any function $f(\cdot )$. To show hardness for the latter problem, we prove the following.

In view of Theorem 4, we cannot hope for an $O^{\ast }(f(k))$-time algorithm for $(\overline{\mu }-k)$-Coloring, for any function $f(\cdot )$.

Given a positive integer $a$, we let $[a]=\{1,\mathrm{\dots },a\}$ denote the set of the first $a$ consecutive positive integers.

We let $G$ denote the input graph on $n$ vertices and $m$ edges. We let $V$ denote the vertex set of $G$. Given a subset of nodes $S\subseteq V$, we let $G[S]$ denote the induced subgraph of $G$ on $S$. We let $\mu (G),\omega (G)$, and $\alpha (G)$ denote the size of a maximum matching, clique, and independent set in $G$ respectively. We let $K_3$ denote the complete graph on three nodes, which we refer to as a triangle.

Given a graph $G$, we say a clique cover of $G$ is a collection $𝒞$ of vertex-disjoint cliques in $G$ such that every vertex appears in some clique of $𝒞$. The size of this cover is simply $|𝒞|$, the number of cliques used in the clique cover.

In the $p$-Clique Cover problem, we are given a graph $G$ on $n$ vertices and are tasked with determining if $G$ has a clique cover of size at most $p$. For convenience, we refer to $(n-k)$-Clique Cover as the Dual Clique Cover problem. By complementing the graph it is easy to see that $p$-Coloring and $p$-Clique Cover are equivalent computational tasks.

Suppose we have a proper coloring of $G$. Then the set of vertices assigned any fixed color form an independent set in $G$, which means they form a clique in $\overline{G}$. Thus the coloring induces a clique cover of the same size. The reverse direction, that a solution to $p$-Clique Cover on $\overline{G}$ implies a solution to $p$-Coloring on $G$, follows by symmetric reasoning. $◀$

For convenience, in our proofs we will use Observation 7 to frame our algorithms as solving problems related to Clique Cover instead of Coloring.

Throughout we work over a finite field $𝔽$ of size $\mathrm{poly}(n)$. Arithmetic operations over $𝔽$ take $\mathrm{poly}(\log n)$ time.

Given a set $S$, let $\mathrm{\Pi }(S)$ denote the set of perfect matchings on $S$ (i.e., the collection of partitions of $S$ into sets of size exactly two). Given a skew-symmetric matrix $𝐀$ (i.e., a matrix that equals $𝐀=-{𝐀}^{\top }$ the negative of its transpose) with rows and columns indexed by a set $S$, its Pfaffian is defined to be

for a function $\mathrm{sgn}:\mathrm{\Pi }(S)\to \{-1,1\}$ whose definition is not relevant here [20, Section 7.3.2].

An arithmetic circuit is a way of constructing a polynomial by starting with its input variables, and iteratively building up more complicated expressions by using the standard operations of addition, multiplication, and division. The size of an arithmetic circuit is the total number of non-scalar operations used to construct its final output polynomial in this way. Our algorithms use the well known fact that Pfaffians admit polynomial-size arithmetic circuits that only use addition and multiplication operations [22].

We make use of the following classic result, proven for example in [19, Theorem 7.2].

Let $S$ be a set of size $p$. Let $\alpha$ and $\beta$ be functions from the collection of subsets of $S$ to $𝔽$.

The subset convolution $(\alpha \ast \beta )$ of $\alpha$ and $\beta$ is the function defined by setting

For each $v\in S$, introduce a variable $y_v$. Let $Y={\left\{y_v\right\}}_{v\in S}$ be this set of variables. Consider polynomials

over the quotient ring $R=𝔽[Y]/⟨{(y^2)}_{y\in Y}⟩$. That is, $R$ is the usual ring of polynomials over the variables in $Y$ with coefficients from $𝔽$, except that whenever we multiply the same variable with itself the resulting product vanishes.

We refer to $R$ as the squarefree ring over $Y$. By definition of polynomial multiplication and the fact that only squarefree monomials survive in $R$, we get that

over $R$. This shows that computing subset convolutions is equivalent to computing products of polynomials over $R$. The following result then follows from known $O^{\ast }(2^p)$ time algorithms for subset convolution [4].

Replace the input graph with its complement. Then by Observation 7, it suffices to show that given a $K_3$-free modulator $S$ of size $p$ for $G$ and a positive integer $k$, we can solve $k$-Clique Cover on $G$ in $O^{\ast }(2^p)$ time.

We write $\overline{S}=V\setminus S$. By definition, $G[\overline{S}]$ contains no triangle (i.e., a copy of $K_3$). This means that for every clique $C$ in $G$, we have $|C\cap \overline{S}|\in \{0,1,2\}$. Given a clique cover $𝒞$ of $G$, we say it has type $\overrightarrow{t}=(t_0,t_1)$ if for each $i\in \{0,1\}$ the cover $𝒞$ contains exactly $t_i$ cliques $C$ satisfying $|C\cap \overline{S}|=i$. Note that if a cover has type $\overrightarrow{t}$, then because every vertex appears in a unique clique in the cover, exactly $t_2=(|\overline{S}|-t_1)/2$ cliques in the cover intersect $\overline{S}$ at two nodes. Consequently, the size of a clique cover with type $\overrightarrow{t}$ is exactly

We say a type $\overrightarrow{t}=(t_0,t_1)$ is valid if and only if we have $t_0+(t_1+n-p)/2\le k$ so that a clique cover of type $\overrightarrow{t}$ has size at most $k$.

Our task is to determine if $G$ contains a clique cover of size at most $k$. Such a cover has at most $O(k^2)\le \mathrm{poly}(n)$ valid types $\overrightarrow{t}$, and we try out each possible such type and look for a clique cover with exactly that type.

To that end, fix a valid type $\overrightarrow{t}=(t_0,t_1)$. We now construct an auxiliary graph $H$, such that perfect matchings in $H$ encode how clique covers of $G$ with type $\overrightarrow{t}$ may restrict to clique covers of $G[\overline{S}]$. We include the vertex set $\overline{S}$ in $H$, and add all edges from $G[\overline{S}]$ to $H$. We then introduce a set $U$ of $t_1$ new vertices, and add edges from every node in $U$ to every vertex in $\overline{S}$. Intuitively, when we take a perfect matching $M$ of $H$, it will correspond to a clique cover $𝒞$ of $G$ such that

• $\mathrm{■}$

  for each edge $\{u,v\}$ with $u\in U$, there is a clique $C\in 𝒞$ with $C\cap \overline{S}=\left\{v\right\}$, and

• $\mathrm{■}$

  for each edge $\{v,w\}\in M$ with $v,w\in \overline{S}$, there is a clique $C\in 𝒞$ with $C\cap \overline{S}=\{v,w\}$.

With this correspondence in mind, we move to constructing a polynomial that will enumerate clique covers of $G$.

Let $E(H)$ denote the edge set of $H$. For each $e\in E(H)$, introduce an indeterminate variable $x_e$. Now consider the matrix $𝐀$ whose rows and columns are indexed by nodes of $H$, with entries defined by

where $(\prec )$ is some fixed ordering on the nodes of $H$.

By Equation 1 and the definition of $𝐀$ above, we have

where here $\mathrm{\Pi }(H)$ denotes the set of perfect matchings in $H$, and $\mathrm{sgn}(M)\in \{-1,1\}$ for each choice of $M$.

Next, we will introduce additional, larger polynomial expressions that we will substitute in for the $x_e$ variables, with the end goal of transforming the matching polynomial $\mathrm{Pf}𝐀$ into a polynomial that enumerates collections of cliques in $G$.

Go through all subsets $T\subseteq S$, and for each check if $T$ is a clique in $G$. This lets us determine the collection $ℱ$ of all cliques in $S$ in $O^{\ast }(2^p)$ time overall.

Then for each edge $e\in E(H)$ and clique $C\subseteq S$, we introduce a variable $z_{eC}$. For each $i\in [t_0]$ and clique $C\subseteq S$, also introduce a variable $z_{iC}$. Let $Z$ be the set of all these $z_{eC}$ and $z_{iC}$ variables.

Additionally, for each each node $v\in S$, we introduce a variable $y_v$. Let $Y={\left\{y_v\right\}}_{v\in S}$ denote this set of $k$ variables.

Now for each $e\in E(H)$ and subset $T\subseteq S$, define the polynomial

Intuitively this polynomial enumerates those cliques $C\subseteq T$ that can be extended using vertices in $e\cap \overline{S}$ to obtain larger cliques in $G$.

Also for each $i\in [t_0]$, define the polynomial

Intuitively these polynomials enumerate cliques $C\subseteq S$ that we do not plan on extending with nodes in $\overline{S}$.

For each vertex $v\in V$, let $N(v)$ denote the set of vertices in $S$ adjacent to $v$ in $G$. We construct a new matrix $𝐁$, by starting with the matrix $𝐀$ and

• $\mathrm{■}$

  for each $e=\{u,v\}\in E(H)$ with $u\in U$ and $v\in \overline{S}$, substituting $x_{uv}$ with ${\mathrm{\Phi }}_e[N(v)]$, and

• $\mathrm{■}$

  for each $e=\{v,w\}\in E(H)$ with $v,w\in \overline{S}$, substituting $x_{vw}$ with ${\mathrm{\Phi }}_e[N(v)\cap N(w)]$.

Now define the polynomial

over $R[Z]$, where $R=𝔽[Y]/⟨{(y^2)}_{y\in Y}⟩$ is the squarefree ring defined in Section 2.

Suppose first that $F$ has a monomial divisible by ${\prod }_{v\in S}{y}_v$. Since we work over the squarefree ring $R$, this monomial is of the form

for some polynomial $f\in 𝔽[Z]$. Moreover, from Equation 5 such a monomial in $F$ must have been generated by taking the product of monomials from $\mathrm{Pf}𝐁$ and each of the ${\mathrm{\Phi }}_i$ such that the appearance of variables from $Y$ in these monomials partition $Y$.

For each $i\in [t_0]$, let $C_i$ be the set of vertices $v\in S$ such that the $y_v$ variable was used by the monomial from ${\mathrm{\Phi }}_i$ selected to help generate the expression from Equation 6 in the expansion of the product from Equation 5. Then by the partition property, the $C_i$ are pairwise disjoint. From the definition of ${\mathrm{\Phi }}_i$ in Equation 4, we get that each $C_i$ is a clique.

Now, consider the monomial selected from $\mathrm{Pf}𝐁$ to help generate the expression from Equation 6 in the expansion of the product from Equation 5. By Equation 2 and the definition of $𝐁$ in terms of $𝐀$, this monomial corresponds to a matching $M\in \mathrm{\Pi }(H)$. Split $M=M_1\bigsqcup M_2$ by letting $M_b$ retain the edges in $M$ which have exactly $b$ endpoints in $\overline{S}$ for each $b\in [2]$. Since $H$ has vertex set $\overline{S}\bigsqcup U$ and $|U|=t_1$, we get that $M_1$ has exactly $t_1$ edges, and each of its edges has one endpoint in $U$ and one endpoint in $\overline{S}$. Let $v_1,\mathrm{\dots },v_{t_1}$ be the nodes in $\overline{S}$ appearing as endpoints of edges in $M_1$. For each $j\in [t_1]$, let $e_j$ be the edge containing $v_j$ in $M_1$.

Since in $𝐁$ we take $𝐀$ and replace each $x_{e_j}$ variable with ${\mathrm{\Phi }}_{e_j}[N(v_j)]$, the product over the edges of $M_1$ from Equation 2 contributes the variables $y_v$ precisely for those vertices $v$ appearing in the union of some choice of cliques $D_1,\mathrm{\dots },D_{t_1}\subseteq S$ with the property that the set $D_j\bigsqcup \left\{v_j\right\}$ is a clique in $G$ for each $j$. Since we work over $R$, the cliques $C_i$ and $D_j$ are mutually disjoint. Moreover, since $C_i\subseteq \overline{S}$ for all $i$, we actually have that the cliques $C_i$ and $D_j\bigsqcup \left\{v_j\right\}$ are collectively vertex-disjoint.

Set $t_2=(|\overline{S}|-t_1)/2$, and let ${\tilde{e}}_1,\mathrm{\dots },{\tilde{e}}_{t_2}$ be the edges of $M_2$. For each $\mathrm{\ell }\in [t_2]$, let ${\tilde{N}}_{\mathrm{\ell }}$ be the set of common neighbors in $S$ of the endpoints of the edge ${\tilde{e}}_{\mathrm{\ell }}$. Since in $𝐁$ we take $𝐀$ and replace each $x_{{\tilde{e}}_{\mathrm{\ell }}}$ variable with ${\mathrm{\Phi }}_{{\tilde{e}}_{\mathrm{\ell }}}[{\tilde{N}}_{\mathrm{\ell }}]$, the product over the edges of $M_2$ from Equation 2 contributes the variables $y_v$ precisely for those vertices $v$ appearing in the union of some choice of cliques ${\tilde{D}}_1,\mathrm{\dots },{\tilde{D}}_{t_2}\subseteq S$ with the property that the set ${\tilde{D}}_{\mathrm{\ell }}\bigsqcup e_{\mathrm{\ell }}$ is a clique in $G$ for each $\mathrm{\ell }$. Since we work over $R$, the $C_i$, $D_j$, and ${\tilde{D}}_{\mathrm{\ell }}$ are mutually disjoint. Moreover, since $M=M_1\bigsqcup M_2$ is a matching in $S$, we in fact know that the $C_i$, $D_j\bigsqcup \left\{v_j\right\}$, and ${\tilde{D}}_{\mathrm{\ell }}\bigsqcup {\tilde{e}}_{\mathrm{\ell }}$ are all vertex-disjoint cliques in $G$.

Combining this vertex-disjoint condition with the facts that $M$ is a perfect matching on $\overline{S}$ and that the monomial in Equation 6 generated by the products of the monomials of all the cliques we have listed so far is divisible by ${\prod }_{v\in S}{y}_v$, we get that the $C_i\text{, }{D}_j\bigsqcup \left\{v_j\right\}\text{, and }{\tilde{D}}_{\mathrm{\ell }}\bigsqcup {\tilde{e}}_{\mathrm{\ell }}$ cliques taken together form a clique cover of $G$ of type $\overrightarrow{t}=(t_0,t_1)$ as claimed.

Conversely, suppose $G$ has a clique cover of type $\overrightarrow{t}=(t_0,t_1)$. Set $t_2=(|\overline{S}|-t_1)/2$.

Let $C_1,\mathrm{\dots },C_{t_0}$ be the cliques in this cover intersecting $\overline{S}$ at zero nodes, $D_1,\mathrm{\dots },D_{t_1}$ be the cliques in this cover intersecting $\overline{S}$ at one node, and ${\tilde{D}}_1,\mathrm{\dots },{\tilde{D}}_{t_2}$ be the cliques in this cover intersecting $\overline{S}$ at two nodes. For each $i\in [t_0]$, select the monomial from ${\mathrm{\Phi }}_i$ in Equation 4 corresponding to the clique $C_i$.

For each $j\in [t_1]$, let $v_j$ be the unique vertex from $\overline{S}$ in $D_j$. For each $\mathrm{\ell }\in [t_2]$, let ${\tilde{e}}_{\mathrm{\ell }}$ be the subset of two vertices in $\overline{S}$ contained in ${\tilde{D}}_{\mathrm{\ell }}$. Since ${\tilde{D}}_{\mathrm{\ell }}$ is a clique, ${\tilde{e}}_{\mathrm{\ell }}$ is an edge. Let ${\tilde{N}}_{\mathrm{\ell }}$ be the set of common neighbors in $\overline{S}$ of the endpoints of ${\tilde{e}}_{\mathrm{\ell }}$. The $v_j$ and ${\tilde{e}}_{\mathrm{\ell }}$ are vertex-disjoint and account for all vertices in $\overline{S}$, because we are assuming we are starting with a clique cover. So we can take a perfect matching $M$ of $H$ which includes all the ${\tilde{e}}_{\mathrm{\ell }}$ edges, and pairs each $v_j$ with a different node in $U$ (here we use the fact that $U$ has exactly $t_1$ nodes). Let $e_j$ be the edge containing $v_j$ in $M$ for each $j\in [t_1]$.

Then we can select the monomial of $\mathrm{Pf}𝐁$ corresponding to choosing the summand for $M$ in Equation 2, choosing the summand for the cliques $D_j\setminus \left\{v_j\right\}$ in the sums for ${\mathrm{\Phi }}_{e_j}[N(v_j)]$ given by Equation 3, and choosing the summands for the cliques ${\tilde{D}}_{\mathrm{\ell }}\setminus {\tilde{e}}_{\mathrm{\ell }}$ in the sums for ${\mathrm{\Phi }}_{{\tilde{e}}_{\mathrm{\ell }}}[{\tilde{N}}_{\mathrm{\ell }}]$ given by Equation 3 again.

Then from the clique cover assumption, the product of all the monomials we selected from the ${\mathrm{\Phi }}_i$ and $\mathrm{Pf}𝐁$ will be divisible by ${\prod }_{v\in S}{y}_v$. Moreover, the product of the variables from $Z$ appearing in this monomial uniquely recover the cliques $C_i$, $D_j$, and ${\tilde{D}}_{\mathrm{\ell }}$, as well as the matching $M$, because the $z_{iC}$ variables record the ordering of the $C_i$ cliques, and the $z_{eC}$ variables annotate the edges $e$ of the matchings corresponding to the $D_j\cap \overline{S}$ and ${\tilde{D}}_{\mathrm{\ell }}\cap \overline{S}$ sets. Thus the monomial generated in this way cannot be cancelled out by any other term in the expansion of $F$ in Equation 5, which proves the desired result. $\mathrm{⊲}$

Having established Claim 11, it suffices to show that we can test that $F$ has a monomial divisible by ${\prod }_{v\in S}{y}_v$ in $O^{\ast }(2^p)$ time. To do this, we will take a random evaluation of the variables in $Z$, and then use fast subset convolution over the variables in $Y$.

For all $i\in [t_0]$ and cliques $C\subseteq S$, we pick independent, uniform random ${\xi }_{iC}\in 𝔽$. Independently from those values, for all $e\in E(H)$ and $C\subseteq S$ we also pick independent, uniform random ${\xi }_{eC}\in 𝔽$. For each $i\in [t_0]$, let

be the result of evaluating the $Z$ variables of ${\mathrm{\Phi }}_i$ on the ${\xi }_{iC}$ values. We can compute each ${\phi }_i$ in $O^{\ast }(2^p)$ time because we have already precomputed the collection $ℱ$ of cliques in $S$.

Similarly, for each $e\in E(H)$ and $T\subseteq S$, let

be the result of evaluating the $Z$ variables of ${\mathrm{\Phi }}_e[T]$ on the ${\xi }_{eC}$ values. Since we precomputed all the cliques contained in $S$, for any fixed $e\in E(H)$ and $T\subseteq S$ we can use Equation 8 to compute ${\phi }_e[T]$ in $O^{\ast }(2^p)$ time. In particular, we can compute ${\phi }_e[T]$ for all $e\in E(H)$ and $T\subseteq S$ of the form $T=N(v)$ for some $v\in \overline{S}$ or $T=N(v)\cap N(w)$ for some $v,w\in \overline{S}$ in $O^{\ast }(2^p)$ time, because there are $\mathrm{poly}(n)$ choices for $e$ and $T$ in this case.

Having computed all these values, we can substitute the $x_e$ for the relevant values ${\phi }_e[T]$ values needed to turn $𝐀$ into $𝐁$ (with respect to our random evaluation of the variables in $Z$). Now use Proposition 8 to obtain a polynomial-size, division-free arithmetic circuit for the Pfaffian, and feed the entries of $𝐁$ we have just computed into it. Each addition and multiplication operation for this arithmetic circuit is now over the squarefree ring $R$, which by Proposition 10 takes $O^{\ast }(2^p)$ time. Since there are only $\mathrm{poly}(n)$ such operations, we compute this random evaluation of $\mathrm{Pf}𝐁$ over $R$ in $O^{\ast }(2^p)$ time overall. We then compute the product of this with all the ${\phi }_i$ again in $O^{\ast }(2^p)$ time by Proposition 10, which by Equation 5 gives us the value of the polynomial $F$ under our random evaluation to its $Z$ variables.

Since $F$ has degree at most $\mathrm{poly}(n)$ in its $Z$ variables, applying Proposition 9 to the coefficient of ${\prod }_{v\in S}{y}_v$ in $F$ (viewed as a polynomial in $Z$), we see that by picking the size of the field $𝔽$ to be a sufficiently large polynomial in $n$, with high probability the random evaluation of $F$ we computed has the monomial ${\prod }_{v\in S}{y}_v$ if and only if the original polynomial $F$ has a monomial divisible by ${\prod }_{v\in S}{y}_v$. So by Claim 11 checking if this random evaluation of $F$ has the monomial ${\prod }_{v\in S}{y}_v$ solves the $k$-Coloring problem in $O^{\ast }(2^p)$ time with high probability. This proves the desired result. $◀$

We replace the graph $G$ with its complement. Then by Observation 7, it suffices to solve the Dual Clique Cover problem.

We first construct a maximal collection $𝒯$ of vertex-disjoint triangles in $G$. Since we can find a triangle in $G$ if one exists in polynomial time, we can construct $𝒯$ by repeatedly finding a triangle $T$ in $G$, including $T$ in $𝒯$, then deleting the vertices of $T$ from $G$ and repeating this process, until we determine that no triangles are left. We find at most $n/3$ triangles in this way, so this takes polynomial time overall.

Let $t=|𝒯|$. Suppose $t\ge k/2$. Then taking the triangles in $𝒯$ together with the single-node sets consisting of each vertex $v$ not used by a triangle in $𝒯$ yields a clique cover for $G$ of size $t+(n-3t)=n-2t\le n-k.$ Thus, we can solve Dual Clique Cover by returning the cover described above.

Otherwise, we have . In this case, maximality of $𝒯$ implies that the set $S={⨆}_{T\in 𝒯}T$ is a $K_3$-free modulator for $G$ of size $3t$. Then by Observation 7 and Lemma 6 we can solve Dual Coloring in this case in $O^{\ast }(2^{3t})\le O^{\ast }(2^{3k/2})$ time, as desired. $◀$

Next, we establish (randomized) fixed-parameter tractability for a smaller parameter.

We replace the graph $G$ with its complement. Let $\mu =\mu (G)$ and $\alpha =\alpha (G)$ be the size of a maximum matching and maximum independent set in the new graph respectively. Since complementing the graph turns cliques into independent sets, by Observation 7 it suffices to show that we can solve $(\alpha +\mu -k)$-Clique Cover in $O^{\ast }(2^{6k})$ time.

We first construct a maximal collection $𝒯$ of vertex-disjoint triangles in $G$. Since finding a triangle in $G$, if it exists, takes polynomial time, and $𝒯$ can have at most $n/3$ triangles, we can obtain $𝒯$ in polynomial time using a greedy algorithm that repeatedly finds triangles, includes them in $𝒯$, deletes the obtained triangles from $G$, and continues in this fashion until we are left with a triangle-free graph.

Let $t=|𝒯|$. Suppose that $t\le 2k$. In this case, define the set $S={⨆}_{T\in 𝒯}T$ of all vertices participating in the triangles of $𝒯$. Then by maximality of $𝒯$, the set $S$ is a $K_3$-free modulator of $G$ of size $3t$. In this case, by Observation 7 and Lemma 6 we can solve $(\alpha +\mu -k)$-Clique Cover in $O^{\ast }(2^{3t})\le O^{\ast }(2^{6k})$ time as claimed.

Otherwise, $t>2k$. In this case, take $\widetilde{𝒯}\subseteq 𝒯$ consisting of exactly $2k$ triangles, and define $S={⨆}_{T\in \widetilde{𝒯}}T$ to be a set of $6k$ vertices making up $2k$ of the triangles in $𝒯$. We show that in this case, a clique cover of size at most $(\alpha +\mu -k)$ always exists in $G$.

Write $\overline{S}=V\setminus S$. Let $M_{\text{out}}$ be a maximum matching in $G[\overline{S}]$. We can find $M_{\text{out}}$ in polynomial time. Let ${\mu }_{\text{out}}=|M_{\text{out}}|$ be the size of this matching. Let $I$ be the set of vertices in $\overline{S}$ that do not appear as an endpoint of an edge in $M_{\text{out}}$. By maximality of $M_{\text{out}}$, the set $I$ forms an independent set in $G$. Write ${\alpha }_{\text{out}}=|I|$.

We will prove the claim by establishing several inequalities concerning structural parameters in $G$.

First, construct a maximum matching $M_{\text{in}}$ in $G[S\bigsqcup I]$ in polynomial time. Let ${\mu }_{\text{in}}=|M_{\text{in}}|$ be the size of this matching. Since $M_{\text{out}}$ is in $G[\overline{S}\setminus I]$ by definition, we see that $M_{\text{in}}\bigsqcup M_{\text{out}}$ is a matching in $G$ of size $({\mu }_{\text{in}}+{\mu }_{\text{out}})$.

Since $\mu$ is the size of a maximum matching in $G$, we get that

Note that since $\alpha$ is the maximum size of independent sets in $G$, we have

Now, by maximality of $M_{\text{in}}$ in $G[S\bigsqcup I]$, we know that the set of vertices in $S\bigsqcup I$ not participating as an endpoint in $M_{\text{in}}$ forms an independent set in $G$. This set then has size $({\alpha }_{\text{out}}+6k-2{\mu }_{\text{in}})$. Since $\alpha$ is the maximum size of independent sets in $G$, we have

Now, we can write

By applying Equations 10, 9, and 11 to the first through third terms on the right-hand side of Equation 12 respectively, we can bound

which proves the desired result. $\mathrm{⊲}$

By definition, every vertex in $\overline{S}$ either appears as an endpoint of $M_{\text{out}}$, or belongs to $I$. Then using the triangles in $\widetilde{𝒯}$ to cover the vertices in $S$, and taking the edges from $M_{\text{out}}$ and the individual nodes from $I$ to cover the vertices in $\overline{S}$, we obtain a clique cover for $G$ of size

by Claim 12. So we can solve $(\alpha +\mu -k)$-Clique Cover just by returning this cover. $◀$

Curiously, previous work showed that Induced Matching (the problem of finding a 1-regular induced subgraph on $k$ vertices) is also fixed-parameter tractable in $k$ for the same below-guarantee parameter $\alpha +\mu -k$ as in the proof above [15].

We now present our lower bound, demonstrating that although Theorem 3 shows we can get an efficient parameterized algorithm for graph coloring below $(\omega +\overline{\mu })$, we do not expect an analogous algorithm to exist for coloring below the quantity $\overline{\mu }$ on its own.

By replacing the graph with its complement and applying Observation 7, it suffices to show that $(n/2-k)$-Clique Cover is W[1]-hard on graphs containing a perfect matching.

We prove this result by reducing from $k$-Colored Clique. In this problem, we are given a $k$-partite graph $G$ on $kn$ vertices, with vertex set $V=V_1\bigsqcup \mathrm{\cdots }\bigsqcup V_k$ partitioned into parts $V_i$ consisting of $n$ nodes each, and are tasked with determining if $G$ contains a clique on $k$ vertices. This problem is known to be W[1]-hard [9, Theorem 13.25].

Take an instance $G$ of $k$-Colored Clique.

For each $i\in [k]$, we order the vertices in $V_i=\{v_{i1},\mathrm{\dots },v_{in}\}$.

We construct a larger graph $\tilde{G}$ that contains $G$ as a subgraph, in addition to some auxiliary nodes and edges we describe next. For each $i\in [k+2]$, we introduce a new node $u_i$ in $\tilde{G}$. For each $i\in [k]$ and $j\in [n-1]$, we introduce a new node $w_{ij}$ in $\tilde{G}$. We add edges between all the $u_i$ nodes. For all $i\in [k]$, we add an edge from $u_i$ to $v_{i1}$. For all $i\in [k]$ and $j\in [n-1]$ we add edges from $w_{ij}$ to $v_{ij}$ and $v_{i(j+1)}$.

Conceptually, this construction of $\tilde{G}$ from $G$ involves adding a new clique of size $(k+2)$ to the graph on the $u_i$ vertices, and for each $i\in [k]$ introducing a path

beginning at $u_i$, and alternating between nodes in $V_i$ and $W_i$ according to the orders of the vertices in these sets. By design, for any $j\in [n]$, we can always split the path

into its first node, a path $A_{ij}$ on an even number of vertices, the node $v_{ij}$, and a suffix $B_{ij}$ on an even number of vertices. Moreover, $A_{ij}$ and $B_{ij}$ consist of $2n-2$ nodes altogether in this decomposition.

Note that the constructed graph $\tilde{G}$ has a perfect matching, by taking the edges $\{u_i,v_{i1}\}$ for all $i\in [k]$ and $\{w_{ij},v_{i(j+1)}\}$ for all $i\in [k]$ and $j\in [n-1]$.

From its definition, $\tilde{G}$ has $N=2kn+2$ nodes. Set the parameter $\mathrm{\ell }=k(n-1)+2$.

Suppose that $G$ has a clique of size $k$. Let $(v_{1j_1},\mathrm{\dots },v_{n{j}_n})\in V_1\times \mathrm{\cdots }\times V_k$ be the $k$-tuple of vertices participating in this clique.

For each $i\in [k]$, by Equation 14 we can split each path $P_i$ into

its first node, two paths $A_{i{j}_i}$ and $B_{i{j}_1}$ on even numbers of vertices with $2n-2$ nodes total, and the node $v_{i{j}_1}$. For each $i\in [k]$, we can cover the nodes in $A_{i{j}_i}$ and $B_{i{j}_i}$ using the endpoints of the edges from a matching of size $(n-1)$. This shows that with $k(n-1)$ cliques, we can cover all vertices in $\tilde{G}$ in a disjoint fashion, except the $u_i$ and $v_{i{j}_i}$ nodes. We include all the $u_i$ nodes in one clique and all the $v_{i{j}_i}$ nodes in another clique to then obtain a clique cover of size $\mathrm{\ell }=k(n-1)+2$ of $\tilde{G}$ as claimed.

Conversely, suppose $\tilde{G}$ has a clique cover of size $\mathrm{\ell }$. Note that the $w_{ij}$ vertices, with indices ranging over $i\in [k]$ and $j\in [n-1]$, form an independent set. Consequently, covering the $w_{ij}$ requires using $k(n-1)$ distinct cliques. Now, each $w_{ij}$ has degree two in $\tilde{G}$, and the neighbors of $w_{ij}$ are non-adjacent in $\tilde{G}$ by definition. Consequently, the cliques used to cover the $w_{ij}$ collectively cover at most $2k(n-1)$ vertices in $\tilde{G}$.

In the assumed clique cover of size $\mathrm{\ell }$ from $\tilde{G}$, this implies that a set of $\mathrm{\ell }-k(n-1)=2$ distinct cliques are used to cover the at least $N-2k(n-1)=2k+2$ remaining nodes in $\tilde{G}$ not covered by the cliques that contain the $w_{ij}$ vertices. Since node $u_{k+2}$ is adjacent to only other $u_i$ nodes, the clique that covers $u_{k+2}$ must solely consist of $u_i$ nodes. Without loss of generality, we may then assume the clique covering $u_{k+2}$ contains all $u_i$ nodes. After removing the nodes covered by this clique, we have one clique left, that must be used to cover the at least $(2k+2)-(k+2)=k$ remaining nodes in $\tilde{G}$. Moreover, this clique uses no $u_i$ nodes or $w_{ij}$ nodes. Consequently, the last clique must be a clique of size $k$ in the $v_{ij}$ nodes, which pulls back to the a clique of size $k$ in $G$. This proves the claim. $\mathrm{⊲}$

Observe that $N/2-\mathrm{\ell }=(k+1)$, so that $\mathrm{\ell }=N/2-(k+1)$.

By Claim 13, solving $k$-Colored Clique problem on graphs with $n$ vertices reduces to solving $(N/2-(k+1))$-Clique Cover on graphs with $N=2kn+2$ nodes and a perfect matching. Hence the reduction is efficient enough to imply that $(n/2-k)$-Clique Cover is W[1]-hard in graphs with perfect matchings, which proves the desired result. $◀$