Max-Leaves Spanning Tree is APX-hard for Cubic Graphs
classification
💻 cs.DM
cs.CCcs.DS
keywords
graphscubicproblemapx-hardalgorithmapproximationknownmaxleaf
read the original abstract
We consider the problem of finding a spanning tree with maximum number of leaves (MaxLeaf). A 2-approximation algorithm is known for this problem, and a 3/2-approximation algorithm when restricted to graphs where every vertex has degree 3 (cubic graphs). MaxLeaf is known to be APX-hard in general, and NP-hard for cubic graphs. We show that the problem is also APX-hard for cubic graphs. The APX-hardness of the related problem Minimum Connected Dominating Set for cubic graphs follows.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.