论文标题
在定向方向上计数内核
Counting Kernels in Directed Graphs with Arbitrary Orientations
论文作者
论文摘要
有向图的内核是一个独立且吸收的顶点的子集（内核中的每个顶点在内核中都有近外的纽布）。并非所有有向图都包含内核，即使在低度平面挖掘机上，计算内核或决定不存在的核心也是np完整的。此问题的现有多项式时间算法都限制了输入的无向结构和边缘方向：例如，无与伦比的边缘（Pass-Lanneau，igarashi and Meunier，igarashi and Meunier，Invete Appl Math 2020）或每个clique都有一个clique（abbas and saula and saoula and Saoula and saoula and saoula and 2005）。相比之下，我们在多项式时间内计算模糊圆间隔图的内核，无论其边缘方向如何，并在存在时返回核。 （Chudnovsky和Seymour在其结构定理中引入了模糊的圆形图。）我们还考虑了Cographs上的内核，在那里我们在其中建立了NP-Hardness在阈值图的子类上，但在阈值子类上建立了线性运行时间。
A kernel of a directed graph is a subset of vertices that is both independent and absorbing (every vertex not in the kernel has an out-neighbour in the kernel). Not all directed graphs contain kernels, and computing a kernel or deciding that none exist is NP-complete even on low-degree planar digraphs. The existing polynomial-time algorithms for this problem all restrict both the undirected structure and the edge orientations of the input: for example, to chordal graphs without bidirectional edges (Pass-Lanneau, Igarashi and Meunier, Discrete Appl Math 2020) or to permutation graphs where each clique has a sink (Abbas and Saoula, 4OR 2005). By contrast, we count the kernels of a fuzzy circular interval graph in polynomial time, regardless of its edge orientations, and return a kernel when one exists. (Fuzzy circular graphs were introduced by Chudnovsky and Seymour in their structure theorem for claw-free graphs.) We also consider kernels on cographs, where we establish NP-hardness in general but linear running times on the subclass of threshold graphs.
