论文标题
迭代类型分区
Iterated Type Partitions
论文作者
论文摘要
本文通过{测量为} clique-width（例如模块化宽度和邻居多样性）进行参数时处理了一些自然图问题的复杂性。本文的主要贡献是引入一个新的参数，称为迭代类型分区，该参数可以在多项式时间内计算，并且在模块化宽度和邻里多样性之间很好地计算。我们证明，当迭代类型分区参数化时，公平的着色问题是w [1] - hard。该结果扩展到模块化宽度，回答一个关于在通过模块化宽度参数时具有fpt算法的可能性的开放问题。此外，我们表明，当通过邻里多样性参数化时，公平的着色问题是FTP。此外，我们提出了由迭代类型分区参数化的简单而快速的FPT算法，该算法为几个图形问题提供了最佳解决方案。特别是，本文介绍了主导集，顶点着色和顶点覆盖问题的算法。 While the above problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient: For the Dominating set and Vertex Cover problems, our algorithms output an optimal set in time $O(2^t+poly(n))$, while for the Vertex Coloring problem, our algorithm outputs an optimal set in time $ o（t^{2.5t+o（t）} \ log n+poly（n））$，其中$ n $和$ t $分别是输入图的大小和迭代类型分区。
This paper deals with the complexity of some natural graph problems when parametrized by {measures that are restrictions of} clique-width, such as modular-width and neighborhood diversity. The main contribution of this paper is to introduce a novel parameter, called iterated type partition, that can be computed in polynomial time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W[1]-hard when parametrized by the iterated type partition. This result extends to modular-width, answering an open question about the possibility to have FPT algorithms for Equitable Coloring when parametrized by modular-width. Moreover, we show that the Equitable Coloring problem is instead FTP when parameterized by neighborhood diversity. Furthermore, we present simple and fast FPT algorithms parameterized by iterated type partition that provide optimal solutions for several graph problems; in particular, this paper presents algorithms for the Dominating Set, the Vertex Coloring and the Vertex Cover problems. While the above problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient: For the Dominating set and Vertex Cover problems, our algorithms output an optimal set in time $O(2^t+poly(n))$, while for the Vertex Coloring problem, our algorithm outputs an optimal set in time $O(t^{2.5t+o(t)}\log n+poly(n))$, where $n$ and $t$ are the size and the iterated type partition of the input graph, respectively.
