Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021
DOI: 10.7155/jgaa.00590
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and clawfree graphs
Vol. 26, no. 2, pp. 209224, 2022. Regular paper.
Abstract Given a connected vertexweighted graph $G$, the maximum weight internal spanning tree (MaxwIST) problem asks for a spanning tree of $G$ that maximizes the total weight of internal nodes. This problem is NPhard and APXhard, with the currently best known approximation factor $1/2$ (Chen et al., Algorithmica 2019). For the case of clawfree graphs, Chen et al. present an involved approximation algorithm with approximation factor $7/12$. They asked whether it is possible to improve these ratios, in particular for clawfree graphs and cubic graphs.
For cubic graphs we present an algorithm that computes a spanning tree whose total weight of internal vertices is at least $\frac{3}{4}\frac{3}{n}$ times the total weight of all vertices, where $n$ is the number of vertices of $G$.
This ratio is almost tight for large values of $n$.
For clawfree graphs of degree at least three, we present an algorithm that computes a spanning tree whose total internal weight is at least $\frac{3}{5}\frac{1}{n}$ times the total vertex weight. The degree constraint is necessary as this ratio may not be achievable if we allow vertices of degree less than three.
With the above ratios, we immediately obtain better approximation algorithms with factors $\frac{3}{4}\epsilon$ and $\frac{3}{5}\epsilon$ for the MaxwIST problem in cubic graphs and clawfree graphs having no degree2 vertices, for any $\epsilon>0$.
The new algorithms are short (compared to that of Chen et al.) and fairly simple as they employ a variant of the depthfirst search algorithm. Moreover, they take linear time while previous algorithms for similar problem instances are superlinear.
This work is licensed under the terms of the CCBY license.

Submitted: March 2021.
Reviewed: June 2021.
Revised: August 2021.
Accepted: September 2021.
Final: September 2021.
Published: June 2022.

Journal Supporters
