论文标题
用于边缘修饰问题的多项式内核，朝向块和严格的和弦图
Polynomial kernels for edge modification problems towards block and strictly chordal graphs
论文作者
论文摘要
我们考虑对块和严格的和弦图的边缘修改问题，其中为一个无方向的图$ g =（v，e）$和一个整数$ k \ in \ mathbb {n} $中的整数$ k \ in \ mathbb {n} $，并寻求从$ g $中最多从$ g $中编辑（添加或删除）$ k $ edete，以获取block Graph或严格的Chordly Grapher。这些问题的完成和删除变体仅通过允许对后者的前方和唯一的边删除来添加边缘添加来定义。块图是一类精心绘制的图形，并接受了几种特征，例如它们是无钻石的弦图。严格的和弦图，也称为块重复图，是块图的自然概括，可以在其中添加真正的双胞胎cut-vertices。严格的和弦图完全是飞镖和无宝贵的和弦图。我们证明了这些问题的大多数变体的NP完整性，并提供了$ O（k^2）$ pertex-kernels用于块图编辑和块图删除，$ O（k^3）$ o（k^3）$ pertex-kernels严格完成和弦完成，并严格删除和圆环删除和A $ O（k^4）$ o（k^4）$ vertex-kernel for Chordel for Chordel for Chordel for Chordel。
We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph $G = (V,E)$ and an integer $k \in \mathbb{N}$ and seeks to edit (add or delete) at most $k$ edges from $G$ to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide $O(k^2)$ vertex-kernels for Block Graph Editing and Block Graph Deletion, $O(k^3)$ vertex-kernels for Strictly Chordal Completion and Strictly Chordal Deletion and a $O(k^4)$ vertex-kernel for Strictly Chordal Editing.
