SCIENCE CHINA Information Sciences, Volume 64 , Issue 5 : 152103(2021) https://doi.org/10.1007/s11432-019-2630-2

Incremental algorithms for the maximum internal spanning tree problem

More info
  • ReceivedJan 20, 2019
  • AcceptedJul 28, 2019
  • PublishedApr 6, 2021



[1] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: WH Freeman & Co, 1979. Google Scholar

[2] Chen Z Z, Harada Y, Guo F. An approximation algorithm for maximum internal spanning tree. J Comb Optim, 2018, 35: 955-979 CrossRef Google Scholar

[3] Cygan M, Fomin F V, Kowalik Ł, et al. Parameterized Algorithms. Berlin: Springer, 2015. Google Scholar

[4] Downey R G, Fellows M R. Parameterized Complexity. Berlin: Springer, 1999. Google Scholar

[5] Fomin F V, Golovach P A, Simonov K. Parameterized $k$-clustering: the distance matters 2019,. arXiv Google Scholar

[6] Li W, Liu H, Wang J. An improved linear kernel for complementary maximal strip recovery: Simpler and smaller. Theor Comput Sci, 2019, 786: 55-66 CrossRef Google Scholar

[7] Shi F, Chen J, Feng Q. A parameterized algorithm for the Maximum Agreement Forest problem on multiple rooted multifurcating trees. J Comput Syst Sci, 2018, 97: 28-44 CrossRef Google Scholar

[8] Guo L, Shen H, Zhu W. Efficient Approximation Algorithms for Multi-Antennae Largest Weight Data Retrieval. IEEE Trans Mobile Comput, 2017, 16: 3320-3333 CrossRef Google Scholar

[9] Feng Q, Hu J, Huang N. Improved PTAS for the constrained k-means problem. J Comb Optim, 2019, 37: 1091-1110 CrossRef Google Scholar

[10] Feng Q L, Zhu S M, Wang J X. An improved kernel for Max-Bisection above tight lower bound. Theor Comput Sci, 2018. doi: 10.1016/j.tcs.2018.06.027. Google Scholar

[11] Fomin F V, Lokshtanov D, Saurabh S, et al. Kernelization: Theory of Parameterized Preprocessing. Cambridge: Cambridge University Press, 2019. Google Scholar

[12] Prieto E, Sloper C. Either/or: using vertex cover structure in designing FPT-algorithms — the case of $k$-internal spanning tree. In: Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS), Ottawa, 2003. 474--483. Google Scholar

[13] Prieto E, Sloper C. Reducing to independent set structure: the case of $k$-internal spanning tree. Nord J Comput, 2005, 12: 308--318. Google Scholar

[14] Fomin F V, Gaspers S, Saurabh S, et al. A linear vertex kernel for maximum internal spanning tree. J Comput Syst Sci, 2013, 79: 1-6. Google Scholar

[15] Li W, Cao Y, Chen J. Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree. Inf Computation, 2017, 252: 187-200 CrossRef Google Scholar

[16] Li X F, Zhu D M. Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), Jeonju, 2014. 467--478. Google Scholar

[17] Knauer M, Spoerhase J. Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem. Algorithmica, 2015, 71: 797-811 CrossRef Google Scholar

[18] Salamon G, Wiener G. On finding spanning trees with few leaves. Inf Processing Lett, 2008, 105: 164-169 CrossRef Google Scholar

[19] Sharp A M. Incremental algorithms: solving problems in a changing world. Dissertation for Ph.D. Degree. Ithaca: Cornell University, 2007. Google Scholar

[20] Mettu R R, Plaxton C G. The Online Median Problem. SIAM J Comput, 2003, 32: 816-832 CrossRef Google Scholar

[21] Lin G, Nagarajan C, Rajaraman R. A General Approach for Incremental Approximation and Hierarchical Clustering. SIAM J Comput, 2010, 39: 3633-3669 CrossRef Google Scholar

[22] Bernstein A, Disser Y, Groß M. General bounds for incremental maximization. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, 2017. Google Scholar

[23] Blum A, Chalasani P, Coppersmith D, et al. The minimum latency problem. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), Montreal, 1994. 163--171. Google Scholar

[24] Codenotti B, De Marco G, Leoncini M. Approximation algorithms for a hierarchically structured bin packing problem. Inf Processing Lett, 2004, 89: 215-221 CrossRef Google Scholar


    Algorithm 1 Simple $2$-competitive algorithm for IMIST

    Require:A connected graph $G=(V,E)$.

    Output:A feasible solution $S$ for $G$ with competitive ratio $2$.

    if $G$ only contains one vertex then

    Return an empty sequence;

    end if

    Let $T$ be a tree comprising an arbitrary edge in $E$;

    Use $S$ to maintain the feasible solution and set the only edge in $T$ to be the first edge in $S$;

    while $\abs{V(T)}<n$ do

    if there exists a maximal path $P$ of length at least one in $G\setminus~V(T)$ whose starting vertex $v$, has a neighbor $u$ in $T$ then

    Let $P&apos;=(u,~P)$;

    Add all edges in $P&apos;$ to $T$

    Append edges in $P&apos;$ one-by-one into $S$, from the first to the last along the path


    for all $v\in~V\setminus~V(T)$

    Add an edge $\{~u,~~v\}$ connecting $v$ and some vertex $u\in~V(T)$ to $T$;

    Append $\{~u,~~v\}$ into $S$;

    end for

    end if

    end while

    Return $S$.


    Algorithm 2 Refined algorithm for the IMIST problem

    Let $P&apos;=(v,~P)$;

    Require:A connected graph $G=(V,E)$.

    Output:A feasible solution $S$ of $G$.

    Determine a $\frac{5}{3}$-approximate maximum internal spanning tree $T$ of $G$;

    Set $S$ to be an empty sequence;

    Exhaustively apply Rules 1 and 2 to $T$ and only apply Rule 2 when Rule 1 is not applicable;

    Determine a longest path $P$ in $T$;

    Individually add the edges in $P$ to $S$ such that the edges in $S$ form a tree after each addition;

    Let $T&apos;:=P$;

    while $\abs{V(T&apos;)}<n$ do

    Determined a longest path $P$ in $T\setminus~V(T&apos;)$;

    Let $u$ be the endpoint of $P$ that has a neighbor $v$ in $T&apos;$;