论文标题
分区良好的和弦图：障碍物集和不相交路径
Well-partitioned chordal graphs: obstruction set and disjoint paths
论文作者
论文摘要
我们引入了一个新的和弦图的子类，该类别概括了拆分图，我们称之为分区的和弦图。拆分图是将顶点的分区录入可以在恒星结构中排列的集团的图形，其叶子的叶子是一个大小。分区良好的和弦图是以下两种方式对此概念的概括。首先，分区中的集团可以在树结构中排列，其次，每个集团都是任意大小的。我们通过禁止感应的子图提供了分区良好的弦图的表征，并给出了一个多项式时算法，该算法给出了任何图，要么找到障碍物，要么输出其顶点套件的分区，该分区表明该图是分区良好的弦乐。我们通过证明在k对k之间找到成对的分离路径的两个变体的算法使用该图类别的算法使用，以k在分区良好的和弦图上的fpt参数化，而在弦图上，这些问题仅在XP中为XP。从另一端开始，我们观察到可以在分裂图上溶解多项式时间的问题，但是在分区良好的弦图上已成为NP完整的。
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given any graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices is in FPT parameterized by k on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we observe that there are problems that are polynomial-time solvable on split graphs, but become NP-complete on well-partitioned chordal graphs.
