Parameterized Reunion with Achromatic Number

Bounds on Achromatic Number in terms of other graph variants like vertex cover number and independence number have been studied [5, 12]. The Pseudo-achromatic Number problem, a related problem, was introduced in 1969 [13] and has been studied extensively [3, 4, 21]. The Pseudo-achromatic Number problem or Graph Complete Partition problem checks whether an undirected graph can be partitioned into $k$ classes such that every pair of classes is connected by an edge. Unlike the achromatic number problem, we do not require these classes to be independent sets. The pseudo-achromatic number may strictly exceed the achromatic Number even for a family of trees [9]. Halldórsson et al studied the problem from the approximation viewpoint, giving tight lower and upper bounds on its approximability. The problem has a $𝒪(k^2)$ kernel that also establishes that it is FPT parameterized by the solution size [7]. Another related problem is the Harmonious Coloring where the objective is to find a proper coloring of the graph such that each pair of colors appears together on at most one edge [15]. It is known to be NP-hard on trees, interval and permutation graphs [8, 2, 20]. Georges investigated the problem on paths, cycles, complete graphs and complete bipartite graphs [11]. Kolay et al [17] studied it from an FPT perspective and showed that it is FPT parameterized by the solution size as well as the vertex cover number of the graph. They also gave an exact exponential time algorithm in split graphs.

Let $G$ be an irreducible graph. We show that if $G$ has more than $k^{k+1}{2}^{k^3+k+2}{e}^{k^2}$ vertices then $\psi (G)\ge k$. Moreover, we design an algorithm for such a graph, i.e., we give a complete coloring with at least $k$ colors. We first describe the algorithm briefly.

We start with finding a greedy independent partition $\mathrm{\Pi }$. If the size of $\mathrm{\Pi }$ is at least $k$, we have that $\psi (G)\ge k$ (by Lemma 17). Moreover $\mathrm{\Pi }$ gives a complete coloring with at least $k$ colors by assigning a distinct color to each set. Next, we focus on the first independent set $S_0$ in $\mathrm{\Pi }$. At each recursive step $i$, we construct $S_{i+1}\subset S_i$ as follows:

• $\mathrm{■}$

  We fix an arbitrary vertex ordering.

• $\mathrm{■}$

  Let $x_{2i}$ and $x_{2i+1}$ be the two minimal vertices with respect to the ordering.

• $\mathrm{■}$

  We identify a distinguishing vertex $d_{xy}$ that is adjacent to exactly one of $x_{2i}$ and $x_{2i+1}$.

• $\mathrm{■}$

  Then we partition $S_i$ into $S_i^0$ ($\subseteq N(d_{xy})$) and $S_i^1$ (not intersect $N(d_{xy})$).

• $\mathrm{■}$

  We set $S_{i+1}=S_i^0$ if $|S_i^0|\ge |S_i|/k$; otherwise, set $S_{i+1}=S_i^1$.

This process yields nested independent sets $S_0\supset S_1\supset \mathrm{\cdots }\supset S_l$, forming either a partial complete coloring or a semi-independent matching, both can be extendable to a complete coloring. We also store a pair of sets $U^0$ and $U^1$ of witness vertices. Simultaneously we keep two index set $Q^0$ and $Q^1$. Next we show that for $|V(G)|\ge k^{k+1}{2}^{k^3+k+2}{e}^{k^2}$ the Algorithm 1 always terminates. In addition we show that either of the cases $Q^0\ge k$ or $Q^1\ge k^3$ leads to a complete coloring with at least $k$ colors (Claims 11 and 12). A complete description of this above mentioned procedure is given in Algorithm 1. Now we show that Algorithm 1 always terminates. Assume that inside Algorithm 1 as otherwise it returns $\psi (G)\ge k$ so terminates. Note that if the Algorithm 1 does not terminate at Step 3 then the while loop (Step 11) runs at most $(k+k^3)$ steps as per our construction of the set $Q_0$ and $Q_1$. Now we show that either $|Q^0|\ge k$ or $|Q^1|\ge k^3$ in the output of Algorithm 1.

We prove this by contradiction. Assume $G$ is an irreducible graph with $n>k^{k+1}{2}^{k^3+k+2}{e}^{k^2}$ vertices and the Algorithm 1 outputs the pair of sets $Q_0$ and $Q_1$ with or . Let $S_{\alpha ,\beta }$ denote the independent set obtained after applying Step 14 $\alpha$ times and Step 15 $\beta$ times, starting from $S_0$. We claim that

When $\alpha +\beta =0$, we have $S_{\alpha ,\beta }=S_0$, so the inequality trivially holds.

By the construction of the algorithm:

By induction hypothesis:

Thus, in either case, i.e., $|S_{\alpha ,\beta }|\ge \frac{1}{2k}|S_{\alpha -1,\beta }|$ or $|S_{\alpha ,\beta }|\ge \frac{1}{2}\left(1-\frac{1}{k}\right)|S_{\alpha ,\beta -1}|$ Equation 1 is satisfied. Now, since and , the loop terminates after at most $k+k^3$ steps. Therefore, the set $S_{k,k^3}$ has size at most 4, but also satisfies:

Since , we have $|S_0|\ge \frac{n}{k}$, giving $|S_{k,k^3}|\ge {\left(\frac{1}{2k}\right)}^k{\left(\frac{1}{2}\left(1-\frac{1}{k}\right)\right)}^{k^3}\frac{n}{k}$. Using the standard inequality ${(1-\frac{1}{k})}^{k^3}\ge e^{-k^2}$ for large $k$, and the condition $|S_{k,k^3}|\le 4$, we have $n\le k^{k+1}\cdot 2^{k^3+k+2}\cdot e^{k^2}$. This contradicts our assumption that $n>k^{k+1}\cdot 2^{k^3+k+2}\cdot e^{k^2}$. Therefore, either $|Q^0|\ge k$ or $|Q^1|\ge k^3$ must hold. $\mathrm{⊲}$

We now compute a pair of sets $U^0$ and $U^1$ as follows: $U^0=\{(x_{2i},x_{2i+1})\mid i\in Q^0\}$ and $U^1=\{(x_{2i},x_{2i+1})\mid i\in Q^1\}$, where $Q^0$ and $Q^1$ be the set returned by Algorithm 1.

Since $|Q^0|\ge k$, there are at least $k$ tuples of the form $(x_{2i},x_{2i+1},d_{x_{2i},x_{2i+1}})$ for $i\in [|Q^0|]$. For each such tuple, let $x_h$ denote the vertex between $x_{2i}$ and $x_{2i+1}$ that is not adjacent to $d_{x_{2i},x_{2i+1}}$. We assign a new color $c_i$ to the pair $(x_h,d_{x_{2i},x_{2i+1}})$, thereby assigning at least $k$ new colors. We now show that this coloring forms a partial $|Q^0|$-complete coloring. From the construction of $Q^0$ in Step 14 of the algorithm, we know that each vertex $d_{x_{2i},x_{2i+1}}$, for $i\in [|Q^0|]$, is adjacent to both $x_{2j}$ and $x_{2j+1}$ for all $j>i$. Thus, for any pair of colors $c_i$ and $c_j$ with $i>j$, the vertex $d_{x_{2j},x_{2j+1}}$ (colored with $c_j$) is adjacent to both $x_{2i}$ and $x_{2i+1}$, at least one of which is colored with $c_i$. Therefore, there is an edge between every pair of color classes assigned in Step 7. By applying Lemma 6, this partial $|Q^0|$-complete coloring can be extended to a complete coloring of size at least $|Q^0|$. $\mathrm{⊲}$

Let $c^{\prime }$ be the color that appears most frequently among the colors assigned to the vertices $d_{x_{2i},x_{2i+1}}$ for all $(x_{2i},x_{2i+1})\in U^1$. Define the subset $U^{\prime }\subseteq U^1$ as the set of all pairs $(x_{2i},x_{2i+1})\in U^1$ such that $c(d_{x_{2i},x_{2i+1}})=c^{\prime }$. Since the graph $G$ is colored using at most $k$ colors, it follows by the pigeonhole principle that $|U^{\prime }|\ge k^2$. We now construct a semi-independent matching from $U^{\prime }$. For each pair $(x_{2i},x_{2i+1})\in U^{\prime }$, include the vertex $d_{x_{2i},x_{2i+1}}$ and the one among $x_{2i}$ and $x_{2i+1}$ to which it is adjacent. Note that, by the definition of $Q^1$, any vertex $x_j$ in $U^1$ with $j>2i+1$ is not adjacent to $d_{x_{2i},x_{2i+1}}$. Therefore, the matching constructed in this way is semi-independent and has size at least $k^2\ge \left(\genfrac{}{}{0pt}{}{k}{2}\right)$. Hence, if $|Q^1|\ge k^3$, then we can compute a semi-independent matching of size at least $\left(\genfrac{}{}{0pt}{}{k}{2}\right)$. By applying Lemma 8, we conclude that $\psi (G)\ge k$. $\mathrm{⊲}$

The correctness of Step 3 follows from Lemma 17. In Claim 10, we show that if the Algorithm 1 outputs the pair of sets $Q_0$ and $Q_1$ then either $|Q^0|\ge k$ or $|Q^1|\ge k^3$. In both the cases, we have that $\psi (G)\ge k$ (by Claim 11 and 12). Hence we are done with showing that if the given graph $G$ is irreducible and more than $k^{k+1}{2}^{k^3+k+2}{e}^{k^2}$ vertices then $\psi (G)\ge k$. This completes the proof. $◀$

Recall that $R$ was an equivalence relation defined as follows: for a vertex $v\in V(G)$, the class $R_v$ contains the vertices $\{u|N_G(u)=N_G(v)\}$.

Now we define a rule that bounds the number of vertices to each equivalence class.

The correctness of the Reduction 2 follows from the following claim.

In the forward direction, assume that $(G,k)$ is a YES-instance of Achromatic Number. Then, $\psi (G)\ge k$. If $\psi (G)\ge k+1$ then $\psi (G-v)\ge k$ trivially holds, as deleting any vertex can decrease the achromatic number by at most one.

So we can assume that $\psi (G)=k$. Let $R_v$ be an equivalence class with at least $k+1$ vertices $u_1,u_2,\mathrm{\dots },u_{k+1}$. Without loss of generality, assume that $v=u_{k+1}$. By the definition of an equivalence class, we have $\forall i,j\in [k+1]$, $N_G(u_i)=N_G(u_j)$. On the contrary, assume that . Let $C_1,\mathrm{\dots },C_k$ be the color classes defined by the complete coloring of $G$. More precisely, for each $i\in [k]$, the set $C_i$ is the set of all vertices in $G$ with color $i$. Additionally, assume that $v\in C_k$. Now, if for all $i\in [k-1]$, we have an edge between a pair of vertices in $C_i$ and $C_k$, excluding $v$, then we are done. Else, there exists a color class $C_i$ such that, on removal of $v=u_{k+1}$, there is no edge between any pair of vertices in $C_i$ and $C_k$. Assume that $u$ is a vertex in $C_i$ such that $(u,v)\in E(G)$. Note that in this case the $k$ vertices $u_1,\mathrm{\dots }{u}_k$ are present in the remaining color classes $C_1,\mathrm{\dots }{C}_{k-1}$.

Thus by the pigeon hole principle, there exist $u_{\mathrm{\ell }}$ and $u_{{\mathrm{\ell }}^{\prime }}$ in $R_v$, with $\mathrm{\ell }\ne {\mathrm{\ell }}^{\prime }\in [k]$, which belong to the same color class, say $C_j,j\in [k-1]$. Because $N_G(u_{\mathrm{\ell }})=N_G(u_{{\mathrm{\ell }}^{\prime }})$, removing $u_{\mathrm{\ell }}$ from $C_j$ will not affect the achromatic number of $G$ as $u_{{\mathrm{\ell }}^{\prime }}$ serves the same purpose as $u_{\mathrm{\ell }}$. Now, we can add $u_{\mathrm{\ell }}$ to $C_t$. Since $u_{\mathrm{\ell }}$ and $v=u_{k+1}$ belong to the same equivalence class, they are not connected by an edge and therefore $u_{\mathrm{\ell }}$, along with the vertices of $C_t$ forms an independent set. The edge $(u,u_{\mathrm{\ell }})$ ensures an edge between the color classes $C_i$ and $C_t$, and hence the achromatic number of the graph $G-v$ is $k$. Thus, $(G^{\prime },k)$ is also a YES-instance.

In the backward direction, let $(G^{\prime },k)$ be a YES-instance of Achromatic Number. Then, $\psi (G^{\prime })\ge k$. Let $C_1,\mathrm{\dots },C_{k^{\prime }}$, where $k^{\prime }\ge k$ be the partition of color classes corresponding to a complete coloring of $G^{\prime }$. If for some $i\in [k^{\prime }]$, $v$ does not have a neighbor in the vertices corresponding to $C_i$, then we can assign the color $i$ to $v$ and get a complete coloring of $G$ with at least $k$ colors. Otherwise, for each $i\in [k^{\prime }]$, the color class $C_i$ contains a vertex from $N_G(v)$. Then, we assign a new color $k^{\prime }+1$ to $v$ and obtain a complete coloring of $G$ with $k^{\prime }+1$ colors. Hence, in both cases, we obtain a complete coloring on $G$ with at least $k$ colors. Thus, $(G,k)$ is a YES-instance. $\mathrm{⊲}$

Let $V(G)$ be partitioned into $q$ equivalence classes. Assume $q>k^{k+1}{2}^{k^3+k+2}{e}^{k^2}$. Construct a subgraph $G[S]$, where $S\subseteq V(G)$ contains exactly one arbitrarily chosen vertex from each equivalence class. Clearly, $|S|=q$. Now we show that no two distinct vertices in $S$ have the same open neighborhood. Suppose, for contradiction, that there exist distinct vertices $u,v\in S$ such that $N(u)=N(v)$. Then, by the definition of the equivalence relation, $u$ and $v$ must belong to the same equivalence class. However, since $S$ contains exactly one vertex from each equivalence class, this contradicts the assumption that both $u$ and $v$ are in $S$. Therefore, all vertices in $S$ have distinct open neighborhoods. Therefore, $G[S]$ is an irreducible graph. Since $q>k^{k+1}{2}^{k^3+k+2}{e}^{k^2}$, it follows that $|S|>k^{k+1}{2}^{k^3+k+2}{e}^{k^2}$. By applying Lemma 9, we obtain $\psi (G[S])\ge k$. This gives a partial complete coloring of $G$ with at least $k$ colors. Finally, by applying Lemma 6, we conclude that $\psi (G)\ge k$. $◀$

Let $(G,k)$ be an instance where none of Reduction Rules 1 and 2 is applicable. Then each equivalence class is bounded by $k$. This imply the following lemma.

We construct a greedy independent partition of $G$, say $I_1,I_2,\mathrm{\dots },I_p$. We color each independent set with a different color. Since the size of the greedy independent partition is at least $k$, we use at least $k$ colors. Now, from the construction of the greedy independent partition, observe that all vertices in $G$ outside $I_1$ must be adjacent to at least one vertex in $I_1$. Similarly, for each $i>1$, the neighborhood of all vertices in $I_i$ includes all vertices in ${\bigcup }_{j=i+1}^p{I}_j$. Thus, there exists no pair of independent sets in a greedy independent partition of $G$ such that their union is also an independent set. Hence, our coloring is a complete coloring of size at least $k$, that is, $\psi (G)\ge k$. $◀$

We first compute a kernel of size at most $k^{k+2}{2}^{k^3+k+2}{e}^{k^2}$ in $𝒪(m)$ time (by Theorem 5). It is easy to observe that if a graph admits a complete coloring with at least $k$ colors, then there exists an induced subgraph $H\subseteq G$ with at most $\left(\genfrac{}{}{0pt}{}{k}{2}\right)$ vertices that also admits a complete $k$-coloring. Therefore, on the kernelized instance, we can perform a brute-force search: enumerate all subsets of at most $\left(\genfrac{}{}{0pt}{}{k}{2}\right)$ vertices and check whether any of them admits a complete coloring with at least $k$ colors. Each such check can be performed in $𝒪(k^2)$ time. If such a subgraph is found, we return YES for the original instance (by Lemma 6); otherwise, we return NO. The kernelization step takes $𝒪(m)$ time, and the brute-force step takes at most $\left(\genfrac{}{}{0pt}{}{k^{k+2}{2}^{k^3+k+2}{e}^{k^2}}{\left(\genfrac{}{}{0pt}{}{k}{2}\right)}\right)\cdot 𝒪(k^2)=2^{𝒪(k^5)}$ time. Hence, the total running time of the algorithm for solving Achromatic Number is $2^{𝒪(k^5)}+𝒪(m)$.

Let $S$ be a vertex cover of size at most $\mathrm{\ell }$ in $G$. Suppose, for a contradiction, $\psi (G)>(\mathrm{\ell }+1)$. Then, there exists a complete coloring $𝒞$ using at least $\mathrm{\ell }+2$ colors. Since $|S|\le \mathrm{\ell }$, at most $\mathrm{\ell }$ color classes of $𝒞$ contain the vertices of the set $S$. This implies that there are at least two color classes, say $C_i$ and $C_j$, which do not contain any vertices of $S$. Now the subgraph of $G$ induced by the vertices of $C_i\cup C_j$ is an independent set, which implies that there is no edge across the color classes $C_i$ and $C_j$. This contradicts the fact that $𝒞$ is a complete coloring. $◀$

An input instance of our problem is $(G,S,k,\mathrm{\ell })$, where $S$ is a vertex cover of size at most $\mathrm{\ell }$. Furthermore, assume that $(G,S,k,\mathrm{\ell })$ is a YES instance and $\mathrm{\Pi }=(X_1,X_2,\mathrm{\dots },X_k)$ is a hypothetical solution where $\mathrm{\Pi }$ is a partition of vertices into $k$ independent sets $X_1,X_2,\mathrm{\dots },X_k$ and, for each pair $i,j$ there is a pair of vertices $u\in X_i$ and $v\in X_j$ such that $(u,v)\in E(G)$. Our ultimate objective is to get $\mathrm{\Pi }$. To do this, we try to obtain as much information as possible about $\mathrm{\Pi }$ in time ${\mathrm{\ell }}^{\mathrm{\ell }}\cdot n^{𝒪(1)}$. Observe that if $S$ is an empty set, then $(G,S,k,\mathrm{\ell })$ is a YES instance if and only if $k=1$, and we can obtain $\mathrm{\Pi }$ by simply setting $X_1=V(G)$. In what follows, we assume that we are given an input $(G,S,k,\mathrm{\ell })$ and a partition $\pi =(Y_1,Y_2,\mathrm{\dots },Y_k)$ of $S$, and our problem is to test whether $\pi$ can be extended to the desired partition $\mathrm{\Pi }$. More specifically, we test whether there is a feasible solution, that is, partition $\mathrm{\Pi }=(X_1,X_2,\mathrm{\dots },X_k)$ of $V(G)$ such that $Y_i\subseteq X_i$, for each $1\le i\le k$. This leads us to the following problem.

We use $(G,S,k,\mathrm{\ell },\pi )$ to denote an instance of Disjoint Achromatic Number/vc.

Our next lemma formally proves our discussion by showing that Achromatic Number/VC and Disjoint Achromatic Number/vc are FPT equivalent. That is, Achromatic Number/VC is FPT if and only if Disjoint Achromatic Number/vc is FPT.

The backward direction is obvious due to the definition of Disjoint Achromatic Number/vc. If either $(G,S,k,\mathrm{\ell },\pi )$ or $(G,S\cup X,k,2\mathrm{\ell },\pi )$ for some $X\subseteq V(G)\setminus S$ is YES, then by definition we have a feasible solution with at least $k$ colors that extends $\pi$.

In the forward direction, let $(G,S,k,\mathrm{\ell })$ be a YES instance of Achromatic Number/VC, then there exists a partition of $G$, say $C_1,\mathrm{\dots },C_t$, with $t\ge k$, such that between any two pairs of color classes $C_i$ and $C_j$, $i\ne j\in [t]$, there exist vertices $u\in C_i$ and $v\in C_j$ with $(u,v)\in E(G)$. Observe that there can be at most one color class that does not contain any vertices from $S$. Now there are two cases.

Case 1.

Every color class $C_i$ intersects $S$. In this case, we define a partition $\pi =(Y_1,Y_2,\mathrm{\dots },Y_t)$ of $S$ as follows. For each $i\in [t]$ the set $Y_i≔S\cap C_i$. Hence $(G,S,k,\mathrm{\ell },\pi )$ is a YES instance.

Case 2.

There is a color class that does not intersect $S$. Wlog, assume that $C_1$ is such a color class. Note $t\le \mathrm{\ell }+1$. Observe that for every set $C_i$, $2\le i\le t$, there is a vertex in $C_1$ that has a neighbor in $C_i$. There may be many vertices that has a neighbor in $C_i$ but we choose an arbitrary vertex $u_i\in C_1$ that has a neighbor in $C_i$. In this process, for each $i$, , we find a vertex $u_i\in C_1$. Let $X=\{u_2,\mathrm{\dots },u_q\}$, where $q\le t$. As $q\le t\le \mathrm{\ell }+1$, so $|X|\le \mathrm{\ell }$. Clearly, $S\cup X$ is a vertex cover of size at most $2\mathrm{\ell }$. Now we define a partition $\pi =(Y_1,Y_2,\mathrm{\dots },Y_k)$ of $S\cup X$ as follows. For $i=1$, define $Y_1≔X$, for all other $i$, $2\le i\le [t]$ we define the set $Y_i≔S\cap C_i$. Hence $(G,S\cup X,k,2\mathrm{\ell },\pi )$ is a YES instance.

$◀$

Next, we aim to generate a collection $ℐ$ of $f(\mathrm{\ell })$ many instances for Disjoint Achromatic Number/vc from an input instance $(G,S,k,\mathrm{\ell })$ of Achromatic Number/VC. First, for each partition $\pi$ of $S$, we include an instance $(G,S,k,\mathrm{\ell },\pi )$ into $ℐ$. Next, consider the equivalence relation $R$ defined for Lemma 13. Given that $|S|\le \mathrm{\ell }$, it follows that the number of equivalence classes is at most $2^{\mathrm{\ell }}$. Thus, for any pair of vertices $u,v$ in the same equivalence class, we have $N(u)=N(v)$. Let $Z^{\ast }$ be a set of vertices formed by arbitrarily choosing a vertex from each equivalence class. Since the number of equivalence classes is at most $2^{\mathrm{\ell }}$, it follows that $|Z^{\ast }|\le 2^{\mathrm{\ell }}$. Now for each subset $Z\subseteq Z^{\ast }$ where $|Z|\le \mathrm{\ell }$, and for each partition $\pi$ of $S\cup Z$, we add an instance $(G,S\cup Z,k,2\mathrm{\ell },\pi )$ to $ℐ$. Therefore, the total number of instances is bounded by ${\mathrm{\ell }}^{\mathrm{\ell }}+\left(\genfrac{}{}{0pt}{}{2^{\mathrm{\ell }}}{\mathrm{\ell }}\right)\cdot {(\mathrm{\ell }+1)}^{2\mathrm{\ell }}\le 2^{𝒪({\mathrm{\ell }}^2)}$. The following claim is derived from the arguments of the proof of Lemma 19 which basically tells that these two problems are FPT equivalent.