论文标题
在立方图和无爪图中，最好的近似算法，用于最大重量内部跨越树
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
论文作者
论文摘要
给定连接的顶点加权图$ g $，最大重量内部跨越树（MaxWist）问题要求$ g $的生成树，以最大化内部节点的总重量。这个问题是NP-HARD和APX-HARD，目前最著名的近似因子$ 1/2 $（Chen等，Algorithmica 2019）。对于无爪图的情况，Chen等人。以近似因子$ 7/12 $的形式呈现涉及的近似算法。他们询问是否可以提高这些比率，特别是对于无爪图和立方图。 我们改善了在立方图和无爪图中的MaxWist问题的近似因子。对于立方图，我们提出了一种计算一个生成树的算法，其内部顶点的总重量至少为$ \ frac {3} {4} {4} {4} - \ frac {3} {n} $乘以所有顶点的总重量，其中$ n $是$ g $ $ g $的$ n $的数量。对于$ n $的巨大值，这个比率几乎很紧。对于至少三个的无爪图，我们提出了一种计算一个跨度树的算法，该算法的总重量至少为$ \ frac {3} {5} {5} {5} - \ frac {1} {n} {n} $乘以总角度的总重量。程度限制是必要的，因为如果我们允许少于三个程度的顶点，则该比率可能无法达到。 在上述比率的情况下，我们立即获得了具有因子$ \ frac {3} {4}-ε$和$ \ frac {3} {3} {5}-ε$的Maxwist问题的$ \ frac {3} {3} {3} {3} {3} {3} {3} {3} {3} {3} -mam $的Maxwist问题，至少三个，我们至少是三个。除了改善近似因素外，与Chen等人相比，新算法相对较短。新算法相当简单，并且采用了深度优先搜索算法的变体，该算法选择每个分支步骤中相对大的范围量顶点。此外，新算法需要线性时间，而以前的类似问题实例的算法是超线性的。
Given a connected vertex-weighted 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 NP-hard and APX-hard, with the currently best known approximation factor $1/2$ (Chen et al., Algorithmica 2019). For the case of claw-free 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 claw-free graphs and cubic graphs. We improve the approximation factors for the MaxwIST problem in cubic graphs and claw-free 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 claw-free 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}-ε$ and $\frac{3}{5}-ε$ for the MaxwIST problem in cubic graphs and claw-free graphs of degree at least three, for any $ε>0$. In addition to improving the approximation factors, the new algorithms are relatively short compared to that of Chen et al.. The new algorithms are fairly simple, and employ a variant of the depth-first search algorithm that selects a relatively-large-weight vertex in every branching step. Moreover, the new algorithms take linear time while previous algorithms for similar problem instances are super-linear.
