Pith. sign in

REVIEW 1 major objections 17 references

Local search with augmenting configurations yields improved approximation ratios for sequential [k, ℓ]-Star Packing.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-30 12:00 UTC pith:NMVGJR4O

load-bearing objection The paper improves four approximation ratios for interval-constrained star packing and finishes the APX-hardness picture for k=2, but the local-search analysis is the part that needs the closest look. the 1 major comments →

arxiv 2605.24711 v1 pith:NMVGJR4O submitted 2026-05-23 cs.DS cs.DM

Covering vertices by sequential stars

Mengyuan Hu , An Zhang , Yong Chen , Zhikai Chen , Wei Ding , Guohui Lin , Jiaxuan Ma , Yue Sun This is my paper
classification cs.DS cs.DM
keywords star packingapproximation algorithmslocal searchamortized analysisAPX-hardnessvertex-disjoint starsgraph coveringNP-hard problems
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines covering the maximum number of vertices by vertex-disjoint stars whose satellite counts lie in a given interval [k, ℓ]. It develops approximation algorithms via local search for four parameter regimes, improving prior ratios in two infinite-ℓ cases and supplying the first known ratios when ℓ is finite. The work additionally proves APX-hardness for the remaining open case k=2. A reader would care because the results tighten the best known polynomial-time guarantees for this NP-hard graph-covering task.

Core claim

We propose either the first or an improved approximation algorithm for the following four sequential settings: a (k+1)/2-approximation algorithm when k ≥ 3 and ℓ = ∞, improving the previous best ratio of (k+1)^2/(2k+1); a 4/3-approximation algorithm when k = 2 and ℓ = ∞, improving the previous best ratio of 3/2; the first (1 + ℓ/(ℓ+1))-approximation algorithm when 2 = k < ℓ; and the first (1 + max{(k-1)/2, (k+1)ℓ/(3(ℓ+1))})-approximation algorithm when 3 ≤ k < ℓ. The problem has been shown APX-hard when k ≥ 3; we prove its APX-hardness for the last remaining case where k = 2.

What carries the argument

Local search procedure with augmenting configurations to bridge two distant neighborhoods for a local improvement operation, together with amortized analysis.

Load-bearing premise

The local search procedure with augmenting configurations and amortized analysis produces the stated approximation guarantees on arbitrary undirected graphs.

What would settle it

A concrete undirected graph on which the local-search algorithm returns a feasible packing whose size is strictly smaller than the claimed fraction of the optimal packing size.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For k ≥ 3 and ℓ = ∞ the ratio improves to (k+1)/2 from the prior (k+1)^2/(2k+1).
  • For k = 2 and ℓ = ∞ the ratio improves to 4/3 from 3/2.
  • A (1 + ℓ/(ℓ+1))-approximation holds for the first time when k=2 and ℓ is finite.
  • The ratio (1 + max{(k-1)/2, (k+1)ℓ/(3(ℓ+1))}) is the first known for 3 ≤ k < ℓ.
  • The problem is APX-hard even in the case k=2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The augmenting-configurations technique may transfer to other bounded-size packing problems on graphs.
  • Because the problem is APX-hard for k=2, the 4/3 ratio obtained for infinite ℓ may be asymptotically tight.
  • The dependence of the ratio on both k and ℓ suggests that hardness grows when the allowed star sizes become more constrained.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 0 minor

Summary. The manuscript studies the sequential [k, ℓ]-Star Packing problem of covering the maximum number of vertices by vertex-disjoint stars whose satellite counts lie in the interval [k, ℓ] (with ℓ possibly infinite). It claims four approximation results obtained via local search plus amortized analysis over augmenting configurations: a (k+1)/2-approximation for k ≥ 3 and ℓ = ∞ (improving (k+1)^2/(2k+1)), a 4/3-approximation for k = 2 and ℓ = ∞ (improving 3/2), the first (1 + ℓ/(ℓ+1))-approximation for k = 2 < ℓ, and the first (1 + max{(k-1)/2, (k+1)ℓ/(3(ℓ+1))})-approximation for 3 ≤ k < ℓ; it also proves APX-hardness for the remaining case k = 2.

Significance. If the local-search analysis holds, the stated ratios would constitute concrete improvements over prior work for several parameter regimes of a natural packing problem and would complete the APX-hardness picture.

major comments (1)
  1. [Abstract] Abstract (paragraph on algorithmic techniques): the central approximation guarantees rest on an amortized analysis of a local-search procedure that enumerates augmenting configurations bridging distant neighborhoods, yet no potential function, no explicit list of configurations, and no lemmas establishing the amortized decrease are supplied; without these the step from local optimality to the numeric ratios cannot be verified and the skeptic concern that overlapping star interactions may be missed remains open.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the comment on the abstract. We address the concern about the presentation of the local-search analysis below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph on algorithmic techniques): the central approximation guarantees rest on an amortized analysis of a local-search procedure that enumerates augmenting configurations bridging distant neighborhoods, yet no potential function, no explicit list of configurations, and no lemmas establishing the amortized decrease are supplied; without these the step from local optimality to the numeric ratios cannot be verified and the skeptic concern that overlapping star interactions may be missed remains open.

    Authors: The abstract is intentionally concise and does not contain the full technical details. The complete amortized analysis, including the potential function, the explicit list of augmenting configurations that bridge distant neighborhoods, and the lemmas establishing the amortized decrease per local improvement, appears in Sections 3–5 of the manuscript. These sections also detail how the analysis accounts for possible overlapping star interactions via the chosen amortization. To make the abstract more self-contained and directly address the verifiability concern, we will revise the relevant paragraph to briefly reference the potential function and the key classes of configurations used. revision: yes

Circularity Check

0 steps flagged

No circularity: standard local-search approximation analysis on arbitrary graphs

full rationale

The paper derives approximation ratios ((k+1)/2 for k≥3 ℓ=∞, 4/3 for k=2 ℓ=∞, 1+ℓ/(ℓ+1) for k=2<ℓ, and 1+max{(k-1)/2,(k+1)ℓ/(3(ℓ+1))} for 3≤k<ℓ) via local search plus amortized analysis over explicitly enumerated augmenting configurations. These are self-contained proof steps on undirected graphs; the APX-hardness proof for k=2 is presented as new. No equations reduce a claimed ratio to a fitted parameter, no ansatz is smuggled via self-citation, and no load-bearing uniqueness theorem is imported from the authors' prior work. The derivation chain is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Relies only on standard undirected-graph definitions and basic NP-hardness reductions; no free parameters, invented entities, or ad-hoc axioms appear in the abstract.

axioms (1)
  • standard math Undirected simple graphs with standard vertex and edge definitions.
    Problem statement presupposes ordinary graph theory.

pith-pipeline@v0.9.1-grok · 5877 in / 1334 out tokens · 36672 ms · 2026-06-30T12:00:23.137474+00:00 · methodology

0 comments
read the original 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, \ell]$, where $1 \le k < \ell$ and $\ell$ can be infinity. This is referred to as sequential {\sc $[k, \ell]$-Star Packing} problem. It is solvable in polynomial time when $k = 1$, but becomes strongly NP-hard when $k \ge 2$. In this paper, we propose either the first or an improved approximation algorithm for the following four sequential settings: 1) a $\frac {k+1}2$-approximation algorithm when $k \ge 3$ and $\ell = \infty$, improving the previous best ratio of $\frac {(k+1)^2}{2k+1}$; 2) a $\frac 43$-approximation algorithm when $k = 2$ and $\ell = \infty$, improving the previous best ratio of $\frac 32$; 3) the first $(1 + \frac \ell{\ell+1})$-approximation algorithm when $2 = k < \ell$; and 4) the first $(1 + \max\left\{\frac {k-1}2, \frac {(k+1) \ell}{3 (\ell+1)}\right\})$-approximation algorithm when $3 \le 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 \ge 3$; we prove its APX-hardness for the last remaining case where $k = 2$.

Figures

Figures reproduced from arXiv: 2605.24711 by An Zhang, Guohui Lin, Jiaxuan Ma, Mengyuan Hu, Wei Ding, Yong Chen, Yue Sun, Zhikai Chen.

Figure 1
Figure 1. Figure 1: An illustration of a companion star S ′ for a heavy star S, of which the edges are thick solid: One satellite of S receives k tokens, here k = 3; another satellite v of S and a satellite v ′ of S ′ each receives k−1 2 tokens in the optimal star S ∗ (dotted circled). Lemma 1 1. The center of a heavy star receives at most k−2 3 tokens; 2. the companion star of a heavy star is not heavy; 3. the center of a co… view at source ↗
Figure 2
Figure 2. Figure 2: An augmenting configuration for the triplet ( [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Finding a companion 2-star S ′ for a heavy 2-star S. The left half illustrates the first case where one satellite receives two tokens, and the right illustrates the second case where each of the two satellites receives one token. Solid edges are in the internal stars and dashed edges are in the optimal stars. In the second case, each of the two satellites v1 and v2 of S receives one token, in two distinct … view at source ↗
Figure 4
Figure 4. Figure 4: All possibilities of exploring from a satellite [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An augmenting configuration (for ℓ = 5) for a triplet (u, S, v), in which there is a sequence of j ≥ 1 internal ℓ-stars S1, S2, . . . , Sj . The solid edges are in these internal ℓ-stars while the dashed edges are in the input graph but not in these ℓ-stars. Swapping the dashed edges into the stars with the thin solid edges makes u covered and v uncovered, and v can provide new opportunities for local impr… view at source ↗
Figure 6
Figure 6. Figure 6: An illustration of an internal ℓ-star S of which the center c and a satellite v both receive tokens (indicated by arrows). The token of the uncovered vertex x is transferred to v in an optimal star S ∗ , which contains another covered vertex u receiving no token. There are only two possibilities for u: To the left, u is the center of another internal ℓ-star (here ℓ = 5); to the right, u is a satellite of a… view at source ↗
Figure 7
Figure 7. Figure 7: Categorizing the optimal stars into four types, using [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The gadget Uj for the clause cj = xj,1 ∨xj,2 ∨xj,3, containing 5 private vertices and 3 vertices labeled by the three literals respectively. Note that while the decision version of [2, ∞)-Star Packing asks for a packing (called perfect) to cover all the vertices, the maximization problem seeks for a packing to cover the maximum number of vertices. We next prove some structural properties for truth assignme… view at source ↗
Figure 9
Figure 9. Figure 9: The gadget Vi for the variable xi : (a) contains 13 private vertices and 2 vertices labeled by the two literals when xi appears two times in the clauses; (b) contains 14 private vertices and 3 vertices labeled by the three literals when xi appears three times in the clauses. Lemma 3 Given a truth assignment for the instance of Max 3CNF-SAT-3 that leaves some clauses unsat￾isfied, another truth assignment, … view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    J. Edmonds. Paths, trees and flowers.Canadian Journal of Mathematics, 17:449–467, 1965

    work page 1965

  2. [2]

    Engebretsen and M

    L. Engebretsen and M. Karpinski. TSP with bounded metrics.Journal of Computer and System Sciences, 72:509–546, 2006

    work page 2006

  3. [3]

    H. Eto, T. Ito, Z. Liu, and E. Miyano. Approximation algorithm for the distance-3 independent set problem on cubic graphs. InProceedings of WALCOM 2017, pages 228–240, 2017

    work page 2017

  4. [4]

    F¨ urer and H

    M. F¨ urer and H. Yu. Approximating thek-set packing problem by local improvements. InProceedings of ISCO 2014, pages 408–420, 2014

    work page 2014

  5. [5]

    J. Ha◦stad. Some optimal inapproximability results. InProceedings of STOC’97, pages 1–10, 1997

    work page 1997

  6. [6]

    J. Ha◦stad. Some optimal inapproximability results.Journal of the ACM, 48:798–859, 2001

    work page 2001

  7. [7]

    Hell and D

    P. Hell and D. G. Kirkpatrick. Packing by cliques and by finite families of graphs.Discrete Mathematics, 49:45–59, 1984

    work page 1984

  8. [8]

    Hell and D

    P. Hell and D. G. Kirkpatrick. Packing by complete bipartite graphs.SIAM Journal on Algebraic and Discrete Methods, 45:199–209, 1986. Covering vertices by sequential stars (v: May 26, 2026)24

    work page 1986

  9. [9]

    M. Hu, A. Zhang, Y. Chen, M. Gong, and G. Lin. Approximation algorithms for non-sequential star packing problems. InProceedings of WALCOM 2025, LNCS 15411, pages 229–243, 2025

    work page 2025

  10. [10]

    M. Hu, A. Zhang, Y. Chen, M. Gong, and G. Lin. Approximation algorithms for non-sequential star packing problems.Information and Computation, 308:Article 105397, 2026

    work page 2026

  11. [11]

    Huang, A

    Z. Huang, A. Zhang, M. Gao, J. Sun, and Y. Chen. Approximation algorithms for thek +-star packing problem.Operations Research Letters, 59:Article 107249, 2025

    work page 2025

  12. [12]

    Li and W

    M. Li and W. Lin. On star family packing of graphs.RAIRO-Operations Research, 55:2129–2140, 2021

    work page 2021

  13. [13]

    Li.Research on approximation algorithms for graph packing problem and graph partition problem

    S. Li.Research on approximation algorithms for graph packing problem and graph partition problem. PhD thesis, East China University of Science and Technology, June 2025

    work page 2025

  14. [14]

    C. Lin, L. Cui, D. W. Coit, and M. Lv. Performance analysis for a wireless sensor network of star topology with random nodes deployment.Wireless Personal Communications, 97:3993–4013, 2017

    work page 2017

  15. [15]

    Thiery and J

    T. Thiery and J. Ward. An improved approximation for maximum weightedk-set packing. InProceedings of SODA 2023, pages 1138–1162, 2023

    work page 2023

  16. [16]

    Xi and W

    W. Xi and W. Lin. The maximum 3-star packing problem in claw-free cubic graphs.Journal of Combinatorial Optimization, 47:Article 73, 2024

    work page 2024

  17. [17]

    W. Xi, W. Lin, and Y. Lin. Packing 2- and 3-stars into cubic graphs.Applied Mathematics and Computation, 460:Article 128287, 2024

    work page 2024