The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time $2^{O(l^2)} n^{O(1)}$. We present a conceptually much simpler algorithm that runs in time $2^{O(l)} n^{O(1)}$. We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple $n^{O(l)}$-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in $n^{O(1)}$-time.
翻译：圆形图 G 的叶子是最小整数 。 G 可以用树叶和叶子的交叉图解。 我们考虑古典统治的叶子和圆形图中的剪切问题进行结构参数化。 Fomina, Golovach 和 Raymond [ESA 2018, Algorithmica 2020] 已证明, 圆形图上的“ 套件” 允许在时间上运行 $2 ⁇ O(l2)} n ⁇ O(1)} 。 我们提出了一个概念上更简单的算法, 以时间为$2 ⁇ (l)} n ⁇ O(1)}。 我们扩展了我们的方法, 以获得连接的占位图和施泰纳树的类似结果。 我们接着考虑了两个经典的切分解问题, 与不易位终端和多路段截断了。 我们证明, 当根据叶子参数参数设定时, 前者是W[1] 硬的算法, 并且通过提出一个简单的美元(l)- 美元- 时间算法。 为了我们的惊喜, 我们发现“ 多路截” 和“ 美元/ 数字 平流平面” 能够解。
相关内容
微信扫码咨询专知VIP会员