Spanning trees with few leaves
While looking up something else, I found a paper by Ling-li Sun (2007): “Spanning trees with leaves bounded by independence number”, Applied Mathematics E-Notes 7: 50–52.
Sun proves that any undirected graph
One could also phrase Sun's result as a paired approximation in the style of my upcoming SODA paper. In any graph one can find either an approximate independent set or an approximate minimum-leaf spanning tree with an approximation ratio
Comments:
2009-12-31T02:25:50Z
Isn't your DFS argument off by one if the root of the DFS tree ends up as a leaf? So if there is a graph on a,b,c,d,e,f with edges a-b and a-[c,d,e,f] and b-[c,d,e,f] (only) then alpha is 4 (c,d,e,f) but the dfs tree at a might go a-b then b-c, b-d, b-e, b-f giving 5 leaves.
2009-12-31T06:01:32Z
I was thinking of rooted trees. But the Sun paper is looking at unrooted trees. So I guess the DFS argument is weaker in that respect — thanks for the correction. I should also have noted that Sun's claim is only for
Using a DFS tree as the initial tree for Sun's algorithm does at least improve its running time to linear, since it only has to go through one iteration to get to a tree with a number of leaves at least as good as the independent set given by the leaves of the DFS tree. Sun writes the algorithm as if α is known, but in the original version of the algorithm one can just keep going until the leaves are all independent, and in the modified version one starts with a DFS tree and then (if the root is a leaf and is adjacent to some other leaves) performs a single improvement step.
2009-12-31T15:57:15Z
Very nice. If your solution fails, your DFS tree
(Valentas)
2009-12-31T16:45:03Z
That's essentially what one gets by applying one round of Sun's algorithm to the DFS tree.
2009-12-31T16:31:34Z
Hi, just to point out that the result on bounding the number of leaves of a spanning tree in terms of the independence number (via DFS) is contained in Proposition 8 of the following paper:
L. Gargano, M. Hammer, P. Hell, L. Stacho, U. Vaccaro
``Spanning Spiders and Light- Splitting Switches'',
Discrete Mathematics, vol. 285, Issue 1-3, pp. 83-95, 2004.
2009-12-31T16:44:39Z
Thanks!