论文标题
围绕有界叶的弦图上的统治和切断的问题
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
论文作者
论文摘要
和弦图G的叶片是最小整数L，因此可以将G视为带有L叶的树子树的相交图。我们考虑通过经典统治的叶片和弦图上的剪切问题来考虑结构参数化。 Fomin，Golovach和Raymond [ESA 2018，Algorithmica 2020]证明，在弦图上占主导地位的算法承认，算法在时间上运行$ 2^{o（l^2）} n^{o（o（1）} $。我们提出了一种概念上要简单得多的算法，该算法在时间上运行$ 2^{o（l）} n^{o（1）} $。我们扩展了我们的方法，以获取连接的统治集和施泰纳树的类似结果。然后，我们将两个经典的切割问题多刺激，并使用无法释放的端子进行多道路终端。我们证明，当叶子参数化时，前者是w [1] - hard，并通过提出一个简单的$ n^{o（l）} $ - 时间算法来补充此结果。令人惊讶的是，我们发现在$ n^{o（1）} $ - 时间上，可以在弦图上使用无法删除的终端切割多路。
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.
