Dominator Coloring Parameterized by Cluster Vertex Deletion Number

The Dominator Coloring (DC) problem borrows properties of two classical problems in graph theory - Graph Coloring and Dominating Set. A dominator coloring $\chi_d$ of a graph $G$ is a proper coloring of its vertices such that each vertex dominates a color class - that is, for each $v \in V(G)$, there exists a color $c$ such that $\emptyset \subset \chi^{-1}_d(c) \subseteq N_G[v]$. Given a graph $G$ and a natural number $\ell$, DC asks if there is a dominator coloring of $G$ which uses at most $\ell$-many colors. DC, which was first described in 2006 and studied in several papers since then, still hosts several important open questions. While it is known that DC is FPT when parameterized by $(t,\ell)$ where $\ell$ is the number of colors used and $t$ the treewidth of $G$, the structural parameterized landscape of the problem remains unexplored. We initiate the study of DC through the lens of structural parameterization. Our first result in this paper is a randomized $O^*(c^k)$ algorithm for DC where $c$ is a constant and $k$ is the size of a graph's Clique Modulator, a set of vertices whose deletion results in a clique. This algorithm is obtained by a non-trivial adaptation of the recent work by Gutin et al. for List Coloring (LC) parameterized by the clique modulator that uses an inclusion-exclusion based polynomial sieving technique, and in addition uses a DP based exact algorithm we develop for DC. Later, we prove the main result of the paper - DC is FPT when parameterized by the size of a graph's Cluster Vertex Deletion (CVD) set; in contrast to the W[i]-hardness result for LC parameterized by the CVD set size. En route, we design a simpler and faster deterministic FPT algorithm when the problem is parameterized by the size of a graph's Twin Cover. We believe that this algorithm's approach, which uses a relationship between DC and LC that we establish, is of independent interest.