Please use this identifier to cite or link to this item:
Title: Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
Authors: Li, W
Cao, Y 
Chen, J
Wang, J
Keywords: Local search
Maximum internal spanning tree
Parameterized computation
Issue Date: 2017
Publisher: Academic Press
Source: Information and computation, 2017, v. 252, p. 187-200 How to cite?
Journal: Information and computation 
Abstract: 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)-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). 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.
ISSN: 0890-5401
EISSN: 1090-2651
DOI: 10.1016/j.ic.2016.11.003
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Aug 12, 2018


Last Week
Last month
Citations as of Aug 17, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 13, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.