论文标题
类统治着色的参数化和精确算法
Parameterized and Exact Algorithms for Class Domination Coloring
论文作者
论文摘要
图形的类统治着色（也称为CD色或主导着色）是一种合适的着色，其中每个颜色类都包含在某个顶点的附近。任何CD色的$ G $所需的最小颜色数量，用$χ_{CD}（G）$表示，称为$ G $的类统治色度数（CD-Chromatic编号）。在这项工作中，我们考虑了在确切的指数时间算法和参数化复杂性的上下文中与图形的CD色相关的两个问题。 （1）给定$ n $顶点上的图$ g $，找到其CD-Chromation编号。 （2）给定图形$ g $和整数$ k $和$ q $，我们可以删除最多$ k $的顶点，从而使所得图的CD-Chromation数量最多为$ Q $？对于第一个问题，我们给出了一种使用运行时间$ \ oh（2^n n^4 \ log n）$的精确算法。另外，我们证明了问题是\ fpt \相对于颜色的数字$ q $作为和弦图上的参数。在围栏的图表上，至少5个，我们表明问题还以$ \ oh（q^3）$ VERTICES接收一个内核。对于第二个（删除）问题，我们显示了每个$ Q \ geq 2 $的\ np硬度。此外，在拆分图上，我们表明，如果$ q $是输入的一部分，并且相对于$ k $和$ k $和$ q $作为组合参数，则问题是\ np-hard。由于最多最多$ q $的CD-Chromation编号的图是\ np-hard，通常是$ q \ geq 4 $，当通过一般图上的删除集的大小进行参数化时，删除问题不太可能是\ fpt \。我们使用已知算法以查找顶点盖和奇数周期横向作为子例程显示了$ q \ in \ {2,3 \} $的固定参数障碍。
A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighbourhood of some vertex. The minimum number of colors required for any cd-coloring of $G$, denoted by $χ_{cd}(G)$, is called the class domination chromatic number (cd-chromatic number) of $G$. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph $G$ on $n$ vertices, find its cd-chromatic number. (2) Given a graph $G$ and integers $k$ and $q$, can we delete at most $k$ vertices such that the cd-chromatic number of the resulting graph is at most $q$? For the first problem, we give an exact algorithm with running time $\Oh(2^n n^4 \log n)$. Also, we show that the problem is \FPT\ with respect to the number $q$ of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with $\Oh(q^3)$ vertices. For the second (deletion) problem, we show \NP-hardness for each $q \geq 2$. Further, on split graphs, we show that the problem is \NP-hard if $q$ is a part of the input and \FPT\ with respect to $k$ and $q$ as combined parameters. As recognizing graphs with cd-chromatic number at most $q$ is \NP-hard in general for $q \geq 4$, the deletion problem is unlikely to be \FPT\ when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for $q \in \{2,3\}$ using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines.
