Covering vertices by sequential stars

Mengyuan Hu, An Zhang, Yong ChenZhikai ChenWei Ding, Guohui Lin, Jiaxuan Ma, Yue Sun · 2026

Read Covering vertices by sequential stars by Mengyuan Hu, An Zhang, Yong ChenZhikai ChenWei Ding, Guohui Lin, Jiaxuan Ma, Yue Sun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24711.txt.

Introduction

Mengyuan Hu and others study covering the most vertices with disjoint stars whose satellite counts fall in a given interval. It runs in polynomial time for one-satellite stars, but turns strongly NP-hard at two or more. The authors give new or improved approximation algorithms for four settings, including (k+1)/2 for large intervals and 4/3 for two satellites. Local search with amortized analysis drives the methods, plus augmenting configurations bridging distant neighborhoods. They also prove APX-hardness for the last open case, where the smallest star has two satellites.

Catalog record

CREATORMengyuan Hu, An Zhang, Yong ChenZhikai ChenWei Ding, Guohui Lin, Jiaxuan Ma, Yue Sun
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE98718
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24711

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Covering vertices by sequential stars Mengyuan Hu, An Zhang, Yong ChenZhikai ChenWei Ding, Guohui Lin, Jiaxuan Ma, Yue Sun Abstract We study the problem of covering the maximum number of vertices in a graph by a collection of vertex-disjoint stars, each with a number of satellites in a given interval [ k , ℓ ] [k,\ell] , where 1 ≤ k < ℓ 1\leq k<\ell and ℓ \ell can be infinity. This is referred to as sequential [ k , ℓ ] [k,\ell] -Star Packing problem. It is solvable in polynomial time when k = 1 k=1 , but becomes strongly NP-hard when k ≥ 2 k\geq 2 . In this paper, we propose either the first or an improved approximation algorithm for the following four sequential settings: • a k + 1 2 \frac{k+1}{2} -approximation algorithm when k ≥ 3 k\geq 3 and ℓ = ∞ \ell=\infty , improving the previous best ratio of ( k + 1 ) 2 2 ​ k + 1 \frac{(k+1)^{2}}{2k+1} ; • a 4 3 \frac{4}{3} -approximation algorithm when k = 2 k=2 and ℓ = ∞ \ell=\infty , improving the previous best ratio of 3 2 \frac{3}{2} ; • the first ( 1 + ℓ ℓ + 1 ) (1+\frac{\ell}{\ell+1}) -approximation algorithm when 2 = k < ℓ 2=k<\ell ; • and the first ( 1 + max ⁡ { k − 1 2 , ( k + 1 ) ​ ℓ 3 ​ ( ℓ + 1 ) } ) (1+\max\left\{\frac{k-1}{2},\frac{(k+1)\ell}{3(\ell+1)}\right\}) -approximation algorithm when 3 ≤ k < ℓ 3\leq k<\ell . Besides the main algorithmic techniques being local search coupled with amortized analysis, we observe augmenting configurations to bridge two distant neighborhoods for a local improvement operation. Additionally, the problem has been shown APX-hard when k ≥ 3 k\geq 3 ; we prove its APX-hardness for the last remaining case where k = 2 k=2 . Keywords: Star packing; local search; augmenting configuration; approximation algorithm; inapproximability Acknowledgments The research is supported by 2026XMHD034, the NNSF of China (Grants 12371316, 12471301, 92567201), the PNSF of Zhejiang China (Grant LZ25A010001), the China Scholarship Council (Grant Nos. 202306540092, 202508330173, 202508330175), the Nanxun Scholars Program of ZJWEU (No. RC2023010481), and the NSERC Canada. 1 Introduction Given an integer i\geq 1 , an i -star is a complete bipartite graph in which one part contains one vertex, called the center of the star, and the other part contains i vertices called the satellites . An i -star is also called a k^{+} -star if i\geq k , or an \ell^{-} -star if i\leq\ell . The star packing problem is to find a collection of vertex-disjoint stars in a given graph G=(V,E) so that the number of vertices in these stars is maximized. One sees that, if any star can be used, then the problem is easy, i.e., solvable in polynomial time. The more interesting case is where there are constraints on the candidate stars, leading to many variants that have been studied in the literature for their theoretical importance and a wide range of applications such as wireless sensor networking [ 14 ] . We examine the sequential star packing problem in this paper, here by sequential it means the candidate stars have their numbers of satellites in a given interval [k,\ell] , for 1\leq k\leq\ell and \ell can be a fixed integer or infinity. The problem is denoted as [k,\ell] -Star Packing . We remark that in the literature, sequential was used to refer to the case where k=1 only [ 8 ] . Hell and Kirkpatrick showed both [1,\infty) -Star Packing and [1,\ell] -Star Packing , for any fixed integer \ell , to be polynomial time solvable [ 8 ] , and the star packing problem using any other candidate star family to be strongly NP-hard [ 7 ] . It follows that [k,\ell] -Star Packing is hard for any k\geq 2 , and we study it in this paper from the approximation algorithm perspective. When k=\ell , that is, only one candidate star is allowed, [k,k] -Star Packing reduces to the (k+1) -Set Packing problem (by constructing a (k+1) -set of vertices whenever these k+1 vertices can form into a k -star, in O(|V|^{k+1}) time), the latter of which admits a (\frac{k+2}{3}+\epsilon) -approximation algorithm, for any \epsilon>0 [ 4 ] . It turns out the design and analysis techniques we develop in this paper do not work out a better approximation algorithm, and thus we assume k<\ell throughout the paper, i.e., in each variant we have at least two candidate stars. We also observe the case where k=2 to be quite different from the other case where k\geq 3 . Therefore, we distinguish four distinct variants, namely, [2,\infty) -Star Packing , [k,\infty) -Star Packing where k\geq 3 , [2,\ell] -Star Packing where \ell>2 , and [k,\ell] -Star Packing where \ell>k\geq 3 . The [k,\infty) -Star Packing problem is also denoted as k^{+} -Star Packing , and has received several studies. It is NP-hard for any k\geq 2 even on bipartite graphs [ 12 ] . Specially, [2,\infty) -Star Packing remains NP-hard on even more restricted graph classes such as bipartite graphs of maximum degree 4 [ 12 ] and cubic graphs [ 17 ] . On the inapproximability, [3,3] -Star Packing on cubic graphs is observed APX-complete [ 16 ] , since it is equivalent to the maximum distance- 3 independent set problem [ 3 ] . Recently, Li [ 13 ] proved a lower bound of \frac{12k+19}{12k+18.994} on the approximation ratio for [k,\infty) -Star Packing when k\geq 3 , if P \neq NP. A number of approximation algorithms have been designed for [k,\infty) -Star Packing . Li and Lin [ 12 ] presented the first 2 -approximation algorithm for k=2 , and the approximation ratio was later improved to \frac{9}{5} by Huang et al. [ 11 ] and to \frac{3}{2} by Hu et al. [ 9 , 10 ] which is the state-of-the-art. When k\geq 3 , Huang et al. [ 11 ] proposed a local search (1+\frac{k}{2}) -approximation algorithm, Li [ 13 ] proposed an almost the same algorithm independently, and Hu et al. [ 9 , 10 ] designed an improved (1+\frac{k^{2}}{2k+1}) -approximation algorithm which is the state-of-the-art. We note that there are approximation algorithms proposed for other variants and/or on special graph classes [ 12 , 17 , 9 , 10 ] . 1.1 Other related work The star packing problem belongs to the general \mathcal{H} -packing framework, where \mathcal{H} is a family of (non-isomorphic) graphs. Given an \mathcal{H} , an \mathcal{H} -packing in an input graph G=(V,E) is a set of vertex-disjoint subgraphs of G , each isomorphic to a graph in \mathcal{H} . A vertex in G is said to be covered by the \mathcal{H} -packing if it is contained in one of the subgraphs in the packing. The \mathcal{H} -packing problem aims to find an \mathcal{H} -packing to cover the maximum number of vertices. For another example of \mathcal{H} , we can look at an i -clique, typically denoted as K_{i} , which is the complete graph on i vertices. When \mathcal{H}=\{K_{2}\} , i.e., it contains only a single 2 -clique, the \mathcal{H} -packing problem

Read the complete text