Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

详细信息    查看全文

• 作者：Wenjun Li^a ; ^b ; ¹ ; ^{liwenjun@csu.edu.cn} ; Yixin Cao^c ; ² ; ^{yixin.cao@polyu.edu.hk} ; Jianer Chen^d ; ^{chen@cse.tamu.edu} ; Jianxin Wang^a ; ¹ ; ^{jxwang@mail.csu.edu.cn}
• 关键词：Maximum internal spanning tree ; Parameterized computation ; Local search
• 刊名：Information and Computation
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：252
• 期：Complete
• 页码：187-200
• 全文大小：479 K
• 卷排序：252

文摘

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⁎(8k)O⁎(8k)-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⁎(4k)O⁎(4k). 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.