Parameterized Complexity of the Star Decomposition Problem

Ramin Javadi; Sahab Hajebi

REVIEW 1 major objections 4 minor 29 references

Parameterized Complexity of the Star Decomposition Problem

T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Star decomposition's parameterized complexity is mapped, with FPT algorithms for several combined parameters and matching hardness results.

desk verdict First parameterized complexity study of Star Decomposition, mostly sound, with a repairable gap in Theorem 17. read the letter →

arxiv 2411.13348 v2 pith:5LXW3T4Y submitted 2024-11-20 cs.CC

Sahab Hajebi , Ramin Javadi This is my paper · ORCID

classification cs.CC MSC 05C7068Q2790C10

keywords stardecompositionedgeparameterizedcomplexityfixed-parametertractabilityneighborhooddiversityvertexcovertree-depthintegerlinearprogramming

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Star decomposition asks whether the edges of a graph can be partitioned into stars whose lengths are specified in advance. The paper establishes an almost complete parameterized complexity map for this problem. The main positive results are that the problem is fixed-parameter tractable for the combined parameters (vc,d), (td,s), and (nd,s), and is in XP for vc and for (tw,d). The main negative results are W[1]-hardness with respect to vc alone and d alone, even on complete bipartite graphs and on trees of depth two, and NP-hardness on Hamiltonian planar cubic graphs when the two allowed star lengths are 1 and 3. The classification matters because it shows exactly where star decomposition becomes tractable in structural graph parameters, complementing earlier NP-completeness results.

What carries the argument

The tractability results rest on two integer-programming formulations. The first formulation uses variables counting stars per vertex per length and binary variables for edge orientation; its dual tree-depth is bounded by the tree-depth of the graph plus the number of distinct star lengths, so standard fixed-parameter results for integer programs give FPT for (td,s) and XP for (tw,d). The second formulation, used for (vc,d), introduces variables indexed by the in-neighborhood types of vertices outside a vertex cover, reducing the number of variables to a function of vc and d; a classical algorithm for integer programming with few variables then solves it. For the (nd,s) result, the graph is partitioned into blocks that are complete or complete bipartite, each contracted to a vertex with pendant edges so that the resulting multigraph has a vertex cover of size O(nd·√(log log n)); a generalization of an existing edge-expansion sufficient condition (Lemma 18) then ensures each block can be expanded back into a star decomposition, because every block has edge expansion at least s.

What would settle it

Exhaustively check small graphs with two twin classes, comparing the answer produced by the contracted-multigraph method against brute-force star decomposability of the original graph, especially cases where a length-1 star in the contracted graph is centered at a pendant leaf; a yes-instance for the contracted graph that is a no-instance for the original graph would break the lifting step.

Watch

Extended reading notes

Core claim

The paper's central claim is that star decomposition is FPT with respect to (nd,s) — neighborhood diversity plus maximum star length — and, more broadly, with respect to (vc,d) and (td,s). It proves W[1]-hardness for vc alone and d alone, with reductions from unary bin packing that work even on the very restricted classes of complete bipartite graphs and depth-two trees; this implies W[1]-hardness for (td,d) and (nd,d) as corollaries. On the degree side it shows NP-hardness for (d,s,Δ)=(2,3,3) on Hamiltonian planar cubic graphs, which is the strongest degree restriction possible because the problem becomes polynomial for s≤2 and for subcubic graphs when the only star length is 3. On the tractability side it gives XP algorithms for vertex cover and for (tw,d), completing the landscape summarized in the paper's Table 1.

Load-bearing premise

The lifting step in the (nd,s) proof assumes that the star vector assigned to a contracted block has total length exactly equal to the number of edges inside that block, so that every internal edge is covered by stars centered in the block and Lemma 18 can decompose the block internally.

Editorial extensions

If this is right

An FPT algorithm exists for star decomposition parameterized by (vc,d), the vertex cover number plus the number of distinct star lengths.
The problem is FPT for (td,s) and for (nd,s), so bounding tree-depth or neighborhood diversity together with maximum star length yields tractability.
The problem is W[1]-hard with respect to vc alone and d alone, and NP-hard on Hamiltonian planar cubic graphs when the only star lengths are 1 and 3, so the combined parameters are essentially necessary.
The XP algorithms for vc and (tw,d) provide n^{O(vc)} and n^{O(tw+d)}-type upper bounds where FPT is ruled out.
Since s≤Δ, the FPT result for (nd,s) also gives FPT for (nd,Δ).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The (vc,d) FPT algorithm can in principle be run with a generic integer-programming solver for moderate vc and d, because its variable count is O(d·2^{O(vc)}) and its coefficients are small; the paper does not discuss the practical performance of this route.
The reductions from unary bin packing suggest that star decomposition inherits a rich hardness structure from bin packing; in particular, the parameter d is as hard as the number of item types, so any improvement on the hardness results would correspond to an improvement for bin packing.
Lemma 18, which extends the expansion-based sufficient condition to graphs with a large stable set removed, is a transferable tool that could be applied to decompositions into paths or other bounded-radius subgraphs, though this direction is not explored in the paper.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this is the first parameterized complexity study of Star Decomposition, and it gives a nearly complete landscape. The main classification is likely correct, but the proof of Theorem 17 has a genuine gap that is easy to repair.

What's actually new: prior work settled NP-completeness and some polynomial cases; this paper gives the first FPT, W[1]-hard, and XP results with respect to vc, tw, td, nd, d, s, and Δ. The reductions from Unary Bin Packing on complete bipartite graphs and depth-2 trees are clean and establish W[1]-hardness for vc and d separately. The borderline NP-hardness on Hamiltonian planar cubic graphs with d=2, s=3, Δ=3 is nice, and the polynomial case (d,s,Δ)=(1,3,3) completes the picture. The ILP-based FPT algorithm for (vc,d) is the key technical step; the variable compression using a vertex cover is well done. The XP dynamic program for vc is also solid. The paper is honest about open questions, which I appreciate.

Soft spots: the 'if' direction of Theorem 17 lifts a multi-star decomposition of the contracted multigraph ~G by applying Lemma 18 to each G_i with the star vector assigned to b_i. The problem is that a pendant edge of ~G may be covered by a length-1 star centered at the artificial leaf rather than at b_i. Then the total length of the stars assigned to b_i is |E(G_i)| - q, where q is the number of inward pendant edges, so the lemma does not apply as written. This is a real gap, but it is repairable: reassign those length-1 stars to b_i (the edge is incident to b_i) and all pendant edges become oriented outward. The paper never states this normalization. There are also minor issues: the bound on z-variables in Theorem 14 uses 2^{3vc} when the natural bound is slightly larger, but the FPT conclusion is unaffected, and Table 1 is hard to parse.

Bottom line: the paper is for parameterized complexity researchers and graph decomposition people. It deserves a serious referee; the gap in Theorem 17 is a repair, not a rewrite. I would send it to peer review with a request to fix the pendant-edge case and clean up the small errors.

Referee Report

1 major / 4 minor

Summary. The paper studies the parameterized complexity of the Star Decomposition problem, in which the edge set of a graph must be partitioned into stars whose lengths are prescribed by a high-multiplicity multiset. The authors give a border NP-hardness result for (d,s,Δ)=(2,3,3), prove W[1]-hardness for the vertex cover number and the number of star types on complete bipartite graphs and on depth-two trees, and provide FPT algorithms for (vc,d), (td,s), and (nd,s), as well as XP algorithms for vc and (tw,d). The main technical ingredients are ILP formulations with bounded dual tree-depth or bounded variable count, an expansion-based decomposition lemma generalizing Tarsi's theorem, and a contraction argument for neighborhood diversity.

Significance. If correct, the paper gives a nearly complete parameterized complexity landscape for a natural edge-decomposition problem. The reductions from Unary Bin Packing are clean and parameter-preserving, and Lemma 18 is a useful standalone tool. The ILP formulations are explicit and their correctness is argued in detail. The main concern is a repairable gap in the proof of the FPT (nd,s) result, which is a central claim of the paper.

major comments (1)

[Section 5, proof of Theorem 17] In the 'if' direction of the equivalence between G and the contracted multigraph \tilde G, the proof applies Lemma 18 to each G_i using the star vector (s_i,a_i) assigned to contracted vertex b_i. This invocation is invalid as written: a pendant edge added for |E(B_i)| may be oriented from the artificial leaf to b_i, in which case it is covered by a length-1 star centered at the leaf and is not counted in (s_i,a_i). Then the total length of (s_i,a_i) equals |E(G_i)| minus the number of inward-oriented pendant edges, while Lemma 18 requires the star lengths to sum exactly to |E(G_i)|. The gap is genuine but repairable: every inward pendant edge is a length-1 star centered at a degree-one leaf, so one can reassign that length-1 star to b_i and reverse the orientation of the edge; after doing this for all such edges, the star vector at b_i sums to |E(G_i)| and Lemma 18 applies. The proof should state this normalization explicitly before applying Lemma 18.

minor comments (4)

[Sections 4 and 5, runtime analyses] The expressions involving log d vanish for d=1 (for instance k=nd·d·log d in Theorem 17 becomes 0, and the stated bound 2^{O(d log d · vc · 2^{3vc})} in Theorem 14 becomes vacuous). Since d=1 is a legitimate case, the bounds should use log(d+1) or include a separate treatment for d=1; the FPT conclusions themselves are unaffected because Lenstra's bound gives 2^{O(vc·2^{3vc})} for d=1.
[Section 5, proof of Theorem 17] The assertion that 'there is no edge between B0 and \cup_{i=1}^t B_i' is stated as clear but depends on the bottom-up order of the pruning procedure; a one-sentence justification would make the proof easier to verify.
[Abstract and Introduction] There are minor typos: 'an star' should be 'a star' and 'isomporphic' should be 'isomorphic'.
[Table 1] The table is hard to read in its current formatting; presenting it as a proper table with clear row and column separators would improve the paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the results are derived from external ILP/orientation theorems and self-contained reductions; the only concern in Theorem 17 is a repairable proof gap, not a circular step.

full rationale

This paper contains no circular derivation chain. Each parameterized tractability result is obtained either from external FPT machinery (Lenstra's ILP theorem, Eisenbrand et al., Ganian et al.) or from Tarsi's orientation/expansion results, and each hardness result is a standard reduction from Independent Set or Unary Bin Packing. The ILP encodings in Section 4 are not assumed feasible; the proofs establish equivalence to the definition of an (s,a)-star decomposition in both directions, with no fitted parameters and no use of the target conclusion as an input. Theorem 14 is proved directly from ILP2 and Theorem 5, and Theorem 17 applies the independently proven Lemma 18 and Theorem 14 inside a contraction argument, again without assuming the statement being proved. The paper contains no load-bearing self-citations and no imported uniqueness claims. One manuscript passage does warrant a non-circularity flag: the lifting step in the proof of Theorem 17 (Section 5) does not explicitly handle length-1 stars centered at the artificial pendant leaves when those leaves receive the stars, which can make the star vector passed to Lemma 18 sum to less than |E(G_i)|. This is a genuine but repairable proof gap, since such stars can be reassigned to the contracted vertex, and it is a correctness issue rather than a circularity: the FPT claim is still derived from the ILP and contraction machinery, not from itself.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper is purely mathematical. It introduces no fitted constants and no new unverified entities. All axioms are standard mathematical theorems or prior complexity results taken as black boxes.

assumptions (6)

standard math Lenstra's theorem: ILP feasibility with p variables is FPT in p
Used in Theorem 14 and 17 to solve ILP2 and ILP1 with bounded variable count.
standard math Eisenbrand et al.: ILP solvable in FPT time parameterized by dual tree-depth and coefficient bound
Used to prove Corollary 12.
standard math Ganian et al.: ILP solvable in time Γ^{O(tw_D(A))}
Used to prove Corollary 13.
standard math Generalized Hall's theorem for η-SDR
Used in Theorem 14 sufficiency.
domain assumption Tarsi's orientation lemma (Lemma 19) and expansion theorem (Theorem 6)
Prior results on graph orientations and star decompositions; used in Lemma 18 and Theorem 17.
domain assumption W[1]-hardness of Unary Bin Packing parameterized by number of bins and number of item types
External complexity results referenced as [18],[19]; basis for Theorems 8 and 10.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Parameterized Complexity of the Star Decomposition Problem." pith.science (2026). https://pith.science/paper/5LXW3T4Y

@misc{pith2026241113348,
  author       = {Pith},
  title        = {Pith review of: Parameterized Complexity of the Star Decomposition Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5LXW3T4Y}},
  note         = {Machine review of arXiv:2411.13348}
}

abstract

A star of length $ \ell $ is defined as the complete bipartite graph $ K_{1,\ell } $. In this paper we deal with the problem of edge decomposition of graphs into stars of varying lengths. Given a graph $ G $ and a list of integers $S=(s_1,\ldots, s_t) $, an $S$-star decomposition of $ G $ is an edge decomposition of $ G $ into graphs $G_1 ,G_2 ,\ldots,G_t $ such that $G_i$ is isomorphic to an star of length $s_i$, for each $i \in\{1,2,\ldots,t\}$. Given a graph $G$ and a list of integers $S$, the \sdp problem asks if $G$ admits an $ S $-star decomposition. The problem is known to be NP-complete even when all stars are of length three. In this paper, we investigate parametrized complexity of the problem with respect to the structural parameters of the input graph such as minimum vertex cover, treewidth, tree-depth and neighborhood diversity as well as some intrinsic parameters of the problem such as the number of distinct star lengths, the maximum size of stars and the maximum degree of the input graph, giving a roughly complete picture of the parameterized complexity landscape of the problem.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 25 canonical work pages

[1]

Domination in convex bipartite and convex-round graphs

J rgen Bang-Jensen, Jing Huang, Gary MacGillivray, Anders Yeo, et al. Domination in convex bipartite and convex-round graphs . Citeseer, 1999

work page 1999
[2]

On the restriction of some NP-complete graph problems to permutation graphs

Andreas Brandst \"a dt and Dieter Kratsch. On the restriction of some NP-complete graph problems to permutation graphs . Springer, 1985

work page 1985
[3]

Decompositions of complete multigraphs into stars of varying sizes

Rosalind A Cameron and Daniel Horsley. Decompositions of complete multigraphs into stars of varying sizes. Journal of Combinatorial Theory, Series B , 145:32--64, 2020

work page 2020
[4]

On the star decomposition of a graph: Hardness results and approximation for the max--min optimization problem

Ferdinando Cicalese and Eduardo Sany Laber. On the star decomposition of a graph: Hardness results and approximation for the max--min optimization problem. Discrete Applied Mathematics , 289:503--515, 2021

work page 2021
[5]

Parameterized algorithms , volume 5

Marek Cygan, Fedor V Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms , volume 5. Springer, 2015

2015
[6]

Domination in convex and chordal bipartite graphs

Peter Damaschke, Haiko M \"u ller, and Dieter Kratsch. Domination in convex and chordal bipartite graphs. Information Processing Letters , 36(5):231--236, 1990

work page 1990
[7]

On star partition of split graphs

D Divya and S Vijayakumar. On star partition of split graphs. In Conference on Algorithms and Discrete Applied Mathematics , pages 209--223. Springer, 2024

work page 2024
[8]

Graph decomposition is np-complete: A complete proof of holyer's conjecture

Dorit Dor and Michael Tarsi. Graph decomposition is np-complete: A complete proof of holyer's conjecture. SIAM Journal on Computing , 26(4):1166--1187, 1997

work page 1997

Show all 29 references

[9]

Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs

Oleg Duginov. Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs. Discrete Mathematics & Theoretical Computer Science , 16(Graph Theory), 2014

2014
[10]

On the complexity of partitioning graphs into connected subgraphs

Martin E Dyer and Alan M Frieze. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics , 10(2):139--153, 1985

1985
[11]

Integer programming and incidence treedepth

Eduard Eiben, Robert Ganian, Du s an Knop, Sebastian Ordyniak, Micha Pilipczuk, and Marcin Wrochna. Integer programming and incidence treedepth. In International Conference on Integer Programming and Combinatorial Optimization , pages 194--204. Springer, 2019

2019
[12]

An algorithmic theory of integer programming

Friedrich Eisenbrand, Christoph Hunkenschr \"o der, Kim-Manuel Klein, Martin Kouteck \`y , Asaf Levin, and Shmuel Onn. An algorithmic theory of integer programming. arXiv preprint arXiv:1904.01361 , 2019

1904 arXiv
[13]

Domination in permutation graphs

Martin Farber and J Mark Keil. Domination in permutation graphs. Journal of algorithms , 6(3):309--321, 1985

1985
[14]

Maximum independent sets in 3-and 4-regular hamiltonian graphs

Herbert Fleischner, Gert Sabidussi, and Vladimir I Sarvanov. Maximum independent sets in 3-and 4-regular hamiltonian graphs. Discrete mathematics , 310(20):2742--2749, 2010

2010
[15]

Computers and intractability: A guide to the theory of np-completeness, 1979

Michael R Gary and David S Johnson. Computers and intractability: A guide to the theory of np-completeness, 1979

1979
[16]

A linear al-gorithm for the domination number of a tree

ST Hedetniemi, SE Goodman, and EJ Cockayne. A linear al-gorithm for the domination number of a tree. Information Processing Letters , 4:41--44, 1975

1975
[17]

The np-completeness of some edge-partition problems

Ian Holyer. The np-completeness of some edge-partition problems. SIAM Journal on Computing , 10(4):713--717, 1981

1981
[18]

Bin packing with fixed number of bins revisited

Klaus Jansen, Stefan Kratsch, D \'a niel Marx, and Ildik \'o Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences , 79(1):39--49, 2013

2013
[19]

Complexity of scheduling few types of jobs on related and unrelated machines

Martin Kouteck \`y and Johannes Zink. Complexity of scheduling few types of jobs on related and unrelated machines. arXiv preprint arXiv:2009.11840 , 2020

2009 arXiv
[20]

Structural Graph Parameters, Fine-Grained Complexity, and Approximation

Michael Lampis. Structural Graph Parameters, Fine-Grained Complexity, and Approximation . Habilitation \`a diriger des recherches, Universit \'e Paris Dauphine , March 2022

2022
[21]

Integer programming with a fixed number of variables

Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research , 8(4):538--548, 1983

1983
[22]

u ller and Andreas Brandst \

Haiko M \"u ller and Andreas Brandst \"a dt. The np-completeness of steiner tree and dominating set for chordal bipartite graphs. Theoretical Computer Science , 53(2-3):257--265, 1987

1987
[23]

X. Nguyen. Induced star partition of graphs with respect to structural parameters. Charles University in Prague, Technical report . 2023

2023
[24]

Short cycles make w-hard problems hard: Fpt algorithms for w-hard problems in graphs with no short cycles

Venkatesh Raman and Saket Saurabh. Short cycles make w-hard problems hard: Fpt algorithms for w-hard problems in graphs with no short cycles. Algorithmica , 52:203--225, 2008

2008
[25]

Induced star partition of graphs

MA Shalu, S Vijayakumar, TP Sandhya, and Joyashree Mondal. Induced star partition of graphs. Discrete Applied Mathematics , 319:81--91, 2022

2022
[26]

Decomposition of complete multigraphs into stars

Michael Tarsi. Decomposition of complete multigraphs into stars. Discrete Mathematics , 26(3):273--278, 1979

1979
[27]

On the decomposition of a graph into stars

Michael Tarsi. On the decomposition of a graph into stars. Discrete Mathematics , 36(3):299--304, 1981

1981
[28]

On claw-decomposition of a complete multipartite graph

Kazuhiko Ushio, Shinsei Tazawa, and Sumiyasu Yamamoto. On claw-decomposition of a complete multipartite graph. Hiroshima Mathematical Journal , 8(1):207--210, 1978

1978
[29]

On claw-decomposition of complete graphs and complete bigraphs

Sumiyasu Yamamoto, Hideto Ikeda, Shinsei Shige-Eda, Kazuhiko Ushio, and Noboru Hamada. On claw-decomposition of complete graphs and complete bigraphs. Hiroshima Mathematical Journal , 5(1):33--42, 1975

1975

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Domination in convex bipartite and convex-round graphs

J rgen Bang-Jensen, Jing Huang, Gary MacGillivray, Anders Yeo, et al. Domination in convex bipartite and convex-round graphs . Citeseer, 1999

work page 1999

[2] [2]

On the restriction of some NP-complete graph problems to permutation graphs

Andreas Brandst \"a dt and Dieter Kratsch. On the restriction of some NP-complete graph problems to permutation graphs . Springer, 1985

work page 1985

[3] [3]

Decompositions of complete multigraphs into stars of varying sizes

Rosalind A Cameron and Daniel Horsley. Decompositions of complete multigraphs into stars of varying sizes. Journal of Combinatorial Theory, Series B , 145:32--64, 2020

work page 2020

[4] [4]

On the star decomposition of a graph: Hardness results and approximation for the max--min optimization problem

Ferdinando Cicalese and Eduardo Sany Laber. On the star decomposition of a graph: Hardness results and approximation for the max--min optimization problem. Discrete Applied Mathematics , 289:503--515, 2021

work page 2021

[5] [5]

Parameterized algorithms , volume 5

Marek Cygan, Fedor V Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms , volume 5. Springer, 2015

2015

[6] [6]

Domination in convex and chordal bipartite graphs

Peter Damaschke, Haiko M \"u ller, and Dieter Kratsch. Domination in convex and chordal bipartite graphs. Information Processing Letters , 36(5):231--236, 1990

work page 1990

[7] [7]

On star partition of split graphs

D Divya and S Vijayakumar. On star partition of split graphs. In Conference on Algorithms and Discrete Applied Mathematics , pages 209--223. Springer, 2024

work page 2024

[8] [8]

Graph decomposition is np-complete: A complete proof of holyer's conjecture

Dorit Dor and Michael Tarsi. Graph decomposition is np-complete: A complete proof of holyer's conjecture. SIAM Journal on Computing , 26(4):1166--1187, 1997

work page 1997