Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
复制标题
对最大内部生成树的参数化和近似算法进行更深入的局部搜索
DOI：
10.1016/j.ic.2016.11.003
复制
发表时间：
2017-02
影响因子：
1
通讯作者：
Wang Jianxin
中科院分区：
文献类型：
--
作者：
Li Wenjun;Cao Yixin;Chen Jianer;Wang Jianxin
最大内部生成树问题是指在给定的图的所有生成树中，有一棵内部顶点数最大的生成树。在它的参数化版中，我们感兴趣的是图是否有至少有k个内部顶点的生成树。Fomin等人(2013)[4]精心设计了一个非常巧妙的归约规则，并证明了该规则的简单应用足以产生3k个顶点的核，这意味着O⁎(8k)时间的参数化算法。利用深度2局部搜索，Knauer和Spoerhase(2015)[9]为优化版本开发了一个(5/3)近似算法。我们尝试更深入的局部搜索：我们对获得的生成树进行彻底的组合分析，并探索它们的算法后果。我们首先观察到，从深度-3局部搜索得到的生成树中，人们可以很容易地找到一个可约结构，并应用Fomin等人的约简规则。这提供了2k个顶点的改进的核，并且作为副产品，运行时间为O⁎(4k)的确定性算法。然后，我们通过考虑深度5局部搜索得到的生成树来进一步深入。证明了该生成树的内部顶点数至少是生成树最大顶点数的2/3，从而给出了该问题的一个改进的近似算法，其比为1.5。
The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al.(2013)[4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an O⁎(8 k)-time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015)[9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2k vertices, and as a by-product, a deterministic algorithm running in time O⁎(4 k). We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1.5 for the problem.
登录
查看更多内容
DOI：
10.1016/j.tcs.2009.03.036
发表时间：
2008-01
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
G. Gutin;Igor Razgon;Eun Jung Kim
通讯作者：
G. Gutin;Igor Razgon;Eun Jung Kim
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Gábor Salamon
通讯作者：
Gábor Salamon
DOI：
10.1007/978-3-319-21840-3_41
发表时间：
2014-12
期刊：
ArXiv
影响因子：
--
作者：
Wenjun Li;Jian-xin Wang;Jianer Chen;Yixin Cao
通讯作者：
Wenjun Li;Jian-xin Wang;Jianer Chen;Yixin Cao
DOI：
10.1016/j.jcss.2015.11.008
发表时间：
2014-02
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
H. Shachnai;M. Zehavi
通讯作者：
H. Shachnai;M. Zehavi
DOI：
10.1007/978-3-319-13075-0_37
发表时间：
2014-12
期刊：
--
影响因子：
--
作者：
Xingfu Li;Daming Zhu
通讯作者：
Xingfu Li;Daming Zhu