pith. sign in

arxiv: 2604.24571 · v1 · submitted 2026-04-27 · 💻 cs.DS · cs.DM

Polynomial Kernels for Spanning Tree with Diversity Requirements

Petr A. Golovach , Diptapriyo Majumdar , Saket Saurabh This is my paper

Pith reviewed 2026-05-08 01:52 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords spanning treesdiverse spanning treeskernelizationparameterized algorithmsgraph algorithmsleaf constraintsinternal vertices
0
0 comments X

The pith

Two variants of finding many pairwise diverse spanning trees with leaf and internal constraints admit polynomial kernels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the Leaf & Internal-Constrained Diverse Spanning Trees problem admits a polynomial kernel when parameterized by p + q + k + ℓ, where the task is to decide if a graph has ℓ pairwise k-diverse spanning trees each having at least p leaves and q internal vertices. It likewise gives a polynomial kernel for the Leaf & Non-terminal-Constrained Diverse Spanning Trees problem under the parameterization p + |V_NT| + k + ℓ, where a prescribed set of vertices must serve as internal vertices in each tree. These kernels consist of reduction rules that shrink the input graph to size bounded by a polynomial in the parameters while preserving the yes/no answer. A sympathetic reader would care because the kernels place both problems in the class of problems solvable by first reducing to small size and then applying any algorithm on the resulting bounded-size instance.

Core claim

The authors establish that Leaf & Internal-Constrained Diverse Spanning Trees has a polynomial kernel parameterized by p + q + k + ℓ and that Leaf & Non-terminal-Constrained Diverse Spanning Trees has a polynomial kernel parameterized by p + |V_NT| + k + ℓ. In each case the kernelization produces an equivalent instance whose number of vertices and edges is bounded by a polynomial function of the parameter values, so that the original decision question can be answered by solving the reduced instance.

What carries the argument

The kernelization algorithms that apply a sequence of reduction rules to bound the graph size while preserving the existence of ℓ pairwise k-diverse spanning trees satisfying the leaf, internal-vertex, or non-terminal constraints.

If this is right

  • Any algorithm that solves the reduced kernel instance can be used to solve the original problem in time polynomial in the input size once the kernel is computed.
  • The existence of the kernels implies that both problems belong to the fixed-parameter tractable class for the stated parameterizations.
  • The reduction rules provide an explicit way to preprocess large instances down to a size governed only by the number of required leaves, internal vertices, diversity threshold, and number of trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar reduction techniques might apply to other diversity measures on spanning trees or to problems that ask for diverse solutions in related graph structures such as paths or matchings.
  • The parameterized tractability shown here could be combined with heuristic search methods to handle cases where one or more of the parameters grow moderately.
  • The kernels open the possibility of designing approximation or enumeration algorithms that first solve the small kernel and then lift the solutions back to the original graph.

Load-bearing premise

The reduction rules correctly preserve the yes or no answer for every input while producing an instance whose size is polynomial in the parameters.

What would settle it

An explicit graph together with concrete values of p, q, k, ℓ (or |V_NT|) for which the claimed reduction rules either produce a graph larger than the stated polynomial bound or change the yes/no answer relative to the original instance.

read the original abstract

Given a connected undirected graph $G$, a spanning tree is a subgraph $T$ of $G$ such that $V(T) = V(G)$ and $T$ is a tree. A collection of $\ell$ spanning trees $T_1,\ldots,T_\ell$ is pairwise $k$-diverse if for every $i \neq j$, $|E(T_i) \triangle E(T_j)| \geq k$. Given a connected undirected graph $G$ and integers $p, q, k, \ell$, Leaf & Internal-Constrained Diverse Spanning Trees asks whether there are $\ell$ distinct spanning trees $T_1,\ldots,T_{\ell}$ of $G$ that are pairwise $k$-diverse such that each tree has at least $p$ leaves and at least $q$ internal vertices. Similarly, Leaf & Non-terminal-Constrained Diverse Spanning Trees takes a connected undirected graph $G$, $V_{NT}\subseteq V(G)$, and three integers $p, k, \ell$, and asks if $G$ has $\ell$ spanning trees that are pairwise $k$-diverse, and each has at least $p$ leaves and conains the vertices of $V_{NT}$ as internal. We consider these two problems from the kernelization perspective and provide polynomial kernels for Leaf & Internal-Constrained Diverse Spanning Trees and Leaf & Non-terminal-Constrained Diverse Spanning Trees, when parameterized by $p + q + k + \ell$ and $p + |V_{\rm NT}| + k + \ell$, respectively.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The paper claims to provide polynomial kernels for two problems: Leaf & Internal-Constrained Diverse Spanning Trees (parameterized by p + q + k + ℓ) and Leaf & Non-terminal-Constrained Diverse Spanning Trees (parameterized by p + |V_NT| + k + ℓ). These problems ask for ℓ pairwise k-diverse spanning trees of a connected graph G, subject to lower bounds on the number of leaves (p) and internal vertices (q) or the inclusion of a given set V_NT as internal vertices.

Significance. If the kernelization results are correct, they establish fixed-parameter tractability for these diversity-constrained spanning-tree problems under natural parameterizations that bound the structural constraints and diversity measure. This would be a solid contribution to parameterized algorithms for graph problems involving multiple solutions with diversity requirements, with potential relevance to network design and robust spanning-tree enumeration.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for reviewing our manuscript and for accurately summarizing the two kernelization results: polynomial kernels for Leaf & Internal-Constrained Diverse Spanning Trees (parameterized by p + q + k + ℓ) and Leaf & Non-terminal-Constrained Diverse Spanning Trees (parameterized by p + |V_NT| + k + ℓ). We are pleased that the potential significance for parameterized algorithms on diversity-constrained spanning trees is recognized, conditional on correctness. The recommendation is listed as uncertain, yet the report contains no specific major comments or questions about the proofs, reductions, or technical details. We remain available to supply any missing clarifications, expanded proof sketches, or examples if the referee has particular concerns about the kernelization arguments.

Circularity Check

0 steps flagged

No significant circularity; kernelization is a direct algorithmic construction

full rationale

The paper asserts the existence of polynomial kernels for Leaf & Internal-Constrained Diverse Spanning Trees (parameterized by p + q + k + ℓ) and Leaf & Non-terminal-Constrained Diverse Spanning Trees (parameterized by p + |V_NT| + k + ℓ). This is an algorithmic result consisting of reduction rules that produce an equivalent instance whose size is bounded by a polynomial in the parameters. No equations, fitted quantities, or self-referential definitions appear in the abstract or problem statements. The parameterizations directly bound the quantities of interest (leaves, internal vertices, diversity threshold, number of trees) without redefining or predicting those same quantities from the output. Any self-citations would be incidental and non-load-bearing for the kernel existence claim, which stands or falls on the correctness of the explicit reductions rather than imported uniqueness theorems or ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard graph-theoretic axioms (connected undirected graphs, spanning trees) and the correctness of the (unseen) kernelization reductions; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math A connected undirected graph always has at least one spanning tree.
    Invoked implicitly when defining the problems.

pith-pipeline@v0.9.0 · 5604 in / 1090 out tokens · 32652 ms · 2026-05-08T01:52:50.135364+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 27 canonical work pages

  1. [1]

    Fomin, Gregory Z

    Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, and Saket Saurabh. Spanning directed trees with many leaves. SIAM J. Discret. Math. , 23(1):466--476, 2009. https://doi.org/10.1137/070710494 doi:10.1137/070710494

    work page doi:10.1137/070710494 2009

  2. [2]

    Fellows, Lars Jaffke, Tom \' a s Masar \' k, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A

    Julien Baste, Michael R. Fellows, Lars Jaffke, Tom \' a s Masar \' k, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond. Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. Artif. Intell. , 303:103644, 2022

    2022

  3. [3]

    FPT algorithms for diverse collections of hitting sets

    Julien Baste, Lars Jaffke, Tom \' a s Masar \' k, Geevarghese Philip, and G \" u nter Rote. FPT algorithms for diverse collections of hitting sets. Algorithms , 12(12):254, 2019

    2019

  4. [4]

    Spotting trees with few leaves

    Andreas Bj \" o rklund, Vikram Kamat, Lukasz Kowalik, and Meirav Zehavi. Spotting trees with few leaves. SIAM J. Discret. Math. , 31(2):687--713, 2017. https://doi.org/10.1137/15M1048975 doi:10.1137/15M1048975

    work page doi:10.1137/15m1048975 2017

  5. [5]

    Random graphs,

    B \' e la Bollob \' a s. Modern Graph Theory , volume 184 of Graduate Texts in Mathematics . Springer, 2002. https://doi.org/10.1007/978-1-4612-0619-4 doi:10.1007/978-1-4612-0619-4

    work page doi:10.1007/978-1-4612-0619-4 2002

  6. [6]

    In: Rovan, B., V ojt´aˇa, P

    Paul S. Bonsma, Tobias Br \" u ggemann, and Gerhard J. Woeginger. A faster FPT algorithm for finding spanning trees with many leaves. In Branislav Rovan and Peter Vojt \' a s, editors, Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings , volume 2747 of Lecture N...

    work page doi:10.1007/978-3-540-45138-9 2003

  7. [7]

    Bonsma and Frederic Dorn

    Paul S. Bonsma and Frederic Dorn. Tight bounds and a fast FPT algorithm for directed max-leaf spanning tree. ACM Trans. Algorithms , 7(4):44:1--44:19, 2011. https://doi.org/10.1145/2000807.2000812 doi:10.1145/2000807.2000812

    work page doi:10.1145/2000807.2000812 2011

  8. [8]

    An approximation algorithm for maximum internal spanning tree

    Zhi - Zhong Chen, Youta Harada, Fei Guo, and Lusheng Wang. An approximation algorithm for maximum internal spanning tree. J. Comb. Optim. , 35(3):955--979, 2018. URL: https://doi.org/10.1007/s10878-017-0245-7, https://doi.org/10.1007/S10878-017-0245-7 doi:10.1007/S10878-017-0245-7

    work page doi:10.1007/s10878-017-0245-7 2018

  9. [9]

    Fomin, Gregory Z

    Nathann Cohen, Fedor V. Fomin, Gregory Z. Gutin, Eun Jung Kim, Saket Saurabh, and Anders Yeo. Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. J. Comput. Syst. Sci. , 76(7):650--662, 2010. URL: https://doi.org/10.1016/j.jcss.2010.01.001, https://doi.org/10.1016/J.JCSS.2010.01.001 doi:10.1016/J.JCSS.2010.01.001

    work page doi:10.1016/j.jcss.2010.01.001 2010

  10. [10]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015

    2015

  11. [11]

    Gutin, Eun Jung Kim, and Anders Yeo

    Jean Daligault, Gregory Z. Gutin, Eun Jung Kim, and Anders Yeo. FPT algorithms and kernels for the directed k -leaf problem. CoRR , abs/0810.4946, 2008. URL: http://arxiv.org/abs/0810.4946, https://arxiv.org/abs/0810.4946 arXiv:0810.4946

    work page arXiv 2008

  12. [12]

    On finding directed trees with many leaves

    Jean Daligault and St \' e phan Thomass \' e . On finding directed trees with many leaves. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers , volume 5917 of Lecture Notes in Computer Science , pages 86--97. Springer, ...

    work page doi:10.1007/978-3-642-11269-0 2009

  13. [13]

    Gutin, and Eun Jung Kim

    Peter Dankelmann, Gregory Z. Gutin, and Eun Jung Kim. On complexity of minimum leaf out-branching problem. Discret. Appl. Math. , 157(13):3000--3004, 2009. URL: https://doi.org/10.1016/j.dam.2009.04.012, https://doi.org/10.1016/J.DAM.2009.04.012 doi:10.1016/J.DAM.2009.04.012

    work page doi:10.1016/j.dam.2009.04.012 2009

  14. [14]

    Woodruff

    Emilie Danna and David L. Woodruff. How to select a small set of diverse solutions to mixed integer programming problems. Oper. Res. Lett. , 37(4):255--260, 2009. URL: https://doi.org/10.1016/j.orl.2009.03.004, https://doi.org/10.1016/J.ORL.2009.03.004 doi:10.1016/J.ORL.2009.03.004

    work page doi:10.1016/j.orl.2009.03.004 2009

  15. [15]

    Mark de Berg, Andr \' e s L \' o pez Mart \' nez, and Frits C. R. Spieksma. Finding diverse minimum s-t cuts. In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan , volume 283 of LIPIcs , pages 24:1--24:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informa...

    work page doi:10.4230/lipics.isaac.2023.24 2023

  16. [16]

    Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics

    Reinhard Diestel. Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics . Springer, 2012

    2012

  17. [17]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Parameterized Complexity . Monographs in Computer Science. Springer, 1999. https://doi.org/10.1007/978-1-4612-0515-9 doi:10.1007/978-1-4612-0515-9

    work page doi:10.1007/978-1-4612-0515-9 1999

  18. [18]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity . Texts in Computer Science. Springer, 2013

    2013

  19. [19]

    Finding diverse solutions parameterized by cliquewidth

    Karolina Drabik and Tom \' a s Masar \' k. Finding diverse solutions parameterized by cliquewidth. CoRR , abs/2405.20931, 2024

    work page arXiv 2024

  20. [20]

    Minimum partition of a matroid into independent subsets

    Jack Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B , 69B:67--72, 1965

    1965

  21. [21]

    Fellows, Michael A

    Vladimir Estivill - Castro, Michael R. Fellows, Michael A. Langston, and Frances A. Rosamond. FPT is p-time extremal structure I . In Hajo Broersma, Matthew Johnson, and Stefan Szeider, editors, Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD Workshop, 8-10 July 2005, Durham, UK , volume 4 of Texts in Algorithmics , pages 1--41. K...

    2005

  22. [22]

    Golovach, and Marie - France Sagot

    Henning Fernau, Petr A. Golovach, and Marie - France Sagot. Algorithmic enumeration: Output-sensitive, input-sensitive, parameterized, approximative (dagstuhl seminar 18421). Dagstuhl Reports , 8(10):63--86, 2018. URL: https://doi.org/10.4230/DagRep.8.10.63, https://doi.org/10.4230/DAGREP.8.10.63 doi:10.4230/DAGREP.8.10.63

    work page doi:10.4230/dagrep.8.10.63 2018

  23. [23]

    Fomin, Serge Gaspers, Saket Saurabh, and St \' e phan Thomass \' e

    Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and St \' e phan Thomass \' e . A linear vertex kernel for maximum internal spanning tree. J. Comput. Syst. Sci. , 79(1):1--6, 2013

    2013

  24. [24]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse pairs of matchings. Algorithmica , 86(6):2026--2040, 2024

    2026

  25. [25]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Diverse collections in matroids and graphs. Math. Program. , 204(1):415--447, 2024

    2024

  26. [26]

    Fomin, Fabrizio Grandoni, Daniel Lokshtanov, and Saket Saurabh

    Fedor V. Fomin, Fabrizio Grandoni, Daniel Lokshtanov, and Saket Saurabh. Sharp separation and applications to exact and parameterized algorithms. Algorithmica , 63(3):692--706, 2012. URL: https://doi.org/10.1007/s00453-011-9555-9, https://doi.org/10.1007/S00453-011-9555-9 doi:10.1007/S00453-011-9555-9

    work page doi:10.1007/s00453-011-9555-9 2012

  27. [27]

    Kernelization: Theory of Parameterized Preprocessing

    Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing . Cambridge University Press, 2019

    2019

  28. [28]

    M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979

    1979

  29. [29]

    Gutin, Igor Razgon, and Eun Jung Kim

    Gregory Z. Gutin, Igor Razgon, and Eun Jung Kim. Minimum leaf out-branching and related problems. Theor. Comput. Sci. , 410(45):4571--4579, 2009. URL: https://doi.org/10.1016/j.tcs.2009.03.036, https://doi.org/10.1016/J.TCS.2009.03.036 doi:10.1016/J.TCS.2009.03.036

    work page doi:10.1016/j.tcs.2009.03.036 2009

  30. [30]

    A framework to design approximation algorithms for finding diverse solutions in combinatorial problems

    Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, and Yota Otachi. A framework to design approximation algorithms for finding diverse solutions in combinatorial problems. In Brian Williams, Yiling Chen, and Jennifer Neville, editors, Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Confe...

    2023

  31. [31]

    Finding a minimum spanning tree with a small non-terminal set

    Tesshu Hanaka and Yasuaki Kobayashi. Finding a minimum spanning tree with a small non-terminal set. Theor. Comput. Sci. , 1033:115092, 2025. URL: https://doi.org/10.1016/j.tcs.2025.115092, https://doi.org/10.1016/J.TCS.2025.115092 doi:10.1016/J.TCS.2025.115092

    work page doi:10.1016/j.tcs.2025.115092 2025

  32. [32]

    Computing diverse shortest paths efficiently: A theoretical and experimental study

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, and Yota Otachi. Computing diverse shortest paths efficiently: A theoretical and experimental study. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educ...

    2022

  33. [33]

    Finding diverse trees, paths, and more

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, and Yota Otachi. Finding diverse trees, paths, and more. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Vi...

    2021

  34. [34]

    Bart M. P. Jansen. Kernelization for maximum leaf spanning tree with positive vertex weights. J. Graph Algorithms Appl. , 16(4):811--846, 2012. URL: https://doi.org/10.7155/jgaa.00279, https://doi.org/10.7155/JGAA.00279 doi:10.7155/JGAA.00279

    work page doi:10.7155/jgaa.00279 2012

  35. [35]

    Better approximation algorithms for the maximum internal spanning tree problem

    Martin Knauer and Joachim Spoerhase. Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica , 71(4):797--811, 2015. URL: https://doi.org/10.1007/s00453-013-9827-7, https://doi.org/10.1007/S00453-013-9827-7 doi:10.1007/S00453-013-9827-7

    work page doi:10.1007/s00453-013-9827-7 2015

  36. [36]

    A new algorithm for finding trees with many leaves

    Joachim Kneis, Alexander Langer, and Peter Rossmanith. A new algorithm for finding trees with many leaves. Algorithmica , 61(4):882--897, 2011. URL: https://doi.org/10.1007/s00453-010-9454-5, https://doi.org/10.1007/S00453-010-9454-5 doi:10.1007/S00453-010-9454-5

    work page doi:10.1007/s00453-010-9454-5 2011

  37. [37]

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

    Wenjun Li, Yixin Cao, Jianer Chen, and Jianxin Wang. Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree. Inf. Comput. , 252:187--200, 2017. URL: https://doi.org/10.1016/j.ic.2016.11.003, https://doi.org/10.1016/J.IC.2016.11.003 doi:10.1016/J.IC.2016.11.003

    work page doi:10.1016/j.ic.2016.11.003 2017

  38. [38]

    A 4/3-approximation algorithm for the maximum internal spanning tree problem

    Xingfu Li, Daming Zhu, and Lusheng Wang. A 4/3-approximation algorithm for the maximum internal spanning tree problem. J. Comput. Syst. Sci. , 118:131--140, 2021. URL: https://doi.org/10.1016/j.jcss.2021.01.001, https://doi.org/10.1016/J.JCSS.2021.01.001 doi:10.1016/J.JCSS.2021.01.001

    work page doi:10.1016/j.jcss.2021.01.001 2021

  39. [39]

    Hsueh - I Lu and R. Ravi. Approximating maximum leaf spanning trees in almost linear time. J. Algorithms , 29(1):132--141, 1998. URL: https://doi.org/10.1006/jagm.1998.0944, https://doi.org/10.1006/JAGM.1998.0944 doi:10.1006/JAGM.1998.0944

    work page doi:10.1006/jagm.1998.0944 1998

  40. [40]

    On the parameterized complexity of diverse SAT

    Neeldhara Misra, Harshil Mittal, and Ashutosh Rai. On the parameterized complexity of diverse SAT . In Juli \' a n Mestre and Anthony Wirth, editors, 35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia , volume 322 of LIPIcs , pages 50:1--50:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    2024

  41. [41]

    C. St.\ J. A. Nash-Williams. Decomposition of finite graphs into forests. J. London Math. Soc. , 39:12, 1964. https://doi.org/10.1112/jlms/s1-39.1.12 doi:10.1112/jlms/s1-39.1.12

    work page doi:10.1112/jlms/s1-39.1.12 1964

  42. [42]

    o rg - R \

    Elena Prieto - Rodriguez and Christian Sloper. Either/or: Using vertex cover structure in designing fpt-algorithms - the case of k-internal spanning tree. In Frank K. H. A. Dehne, J \" o rg - R \" u diger Sack, and Michiel H. M. Smid, editors, Algorithms and Data Structures, 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30 - August ...

    work page doi:10.1007/978-3-540-45078-8 2003

  43. [43]

    Reducing to independent set structure -- the case of k-internal spanning tree

    Elena Prieto - Rodriguez and Christian Sloper. Reducing to independent set structure -- the case of k-internal spanning tree. Nord. J. Comput. , 12(3):308--318, 2005

    2005

  44. [44]

    Bonsma, and Stefanie Lowski

    Roberto Solis - Oba, Paul S. Bonsma, and Stefanie Lowski. A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Algorithmica , 77(2):374--388, 2017. URL: https://doi.org/10.1007/s00453-015-0080-0, https://doi.org/10.1007/S00453-015-0080-0 doi:10.1007/S00453-015-0080-0

    work page doi:10.1007/s00453-015-0080-0 2017