{"id":"cb87d9d3-5f80-43bf-96dd-edcef5e01900","arxiv_id":"2411.13348","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Star Decomposition is para-NP-hard for several structural parameters, W[1]-hard for vertex cover number, FPT for (vc,d), (td,s), and (nd,s), and XP for treewidth and vc.","lead":"Researchers map the computational difficulty of splitting a graph's edges into stars of prescribed sizes. The problem is hard even on very simple graphs for some parameters, but tractable for others, giving a nearly complete parameterized complexity picture.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 17's lifting step omits the case where pendant edges of the contracted graph are covered by length-1 stars centered at artificial leaves; the gap is real but repairable.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing gap in the central FPT result. Theorem 17 is the paper's main positive contribution for neighborhood diversity, and its proof hinges on the equivalence between star decompositions of G and multi-star decompositions of the contracted graph tilde-G. The unhandled pendant-edge case is not a mere cosmetic issue: Lemma 18 is only valid when the assigned star lengths have total weight equal to the number of edges in the graph to be decomposed, and an inward-oriented pendant edge breaks that equality. I verified that the difficulty can be removed by transferring length-1 stars from pendant leaves to b_i, so the theorem itself is not obviously false; however, the proof as submitted does not contain this argument, and without it the 'if' direction does not follow. This warrants a CONDITIONAL verdict rather than REJECT: the main landscape claims are supported elsewhere, and the gap is localized to one step of Theorem 17. The reader's assessment is accurate and appropriately calibrated.","tokens_in":16818,"tokens_out":27022,"duration_ms":307032,"concrete_test":"Formalize the missing normalization: take any multi-star decomposition of tilde-G, define q_i as the number of pendant edges incident to b_i that are oriented toward the pendant leaf, and modify the decomposition by deleting those q_i length-1 stars centered at leaves and adding q_i length-1 stars centered at b_i. Verify that the global multiplicity vector a is unchanged and that the new star vector at b_i satisfies the equality (s_i,a_i') dot 1 = |E(G_i)|, where |E(G_i)| is |E(G[B_i])| plus the number of edges directed from B_i to V\\B_i. If this check passes for every B_i, the proof's 'if' direction can be repaired by inserting this transfer argument; if any step fails, Theorem 17 would need a counterexample rather than a patch.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 17, the 'if' direction of the G-vs-tilde-G equivalence is asserted by applying Lemma 18 to each G_i with the star vector (s_i,a_i) assigned to contracted vertex b_i. A multi-star decomposition of tilde-G orients every edge; a pendant edge added for |E(B_i)| can be oriented either b_i -> leaf or leaf -> b_i. In the latter case the edge is covered by a length-1 star centered at the artificial leaf, not by any star assigned to b_i. Then the total length of (s_i,a_i) equals |E(G_i)| - q, where q is the number of inward pendant edges, because G_i contains all of G[B_i] plus all edges directed from B_i to V\\B_i, while the inward pendant edges correspond to internal edges of G[B_i] that still must be covered in G_i. Lemma 18 requires the star lengths to sum exactly to |E(G_i)|, so the invocation as written is invalid. The gap is genuine but repairable: every inward pendant edge is a length-1 star centered at a degree-1 leaf, so those stars can be reassigned to b_i without changing the global multiset S; after this transfer the star vector at b_i sums to |E(G_i)| and Lemma 18 applies. The paper never states this normalization, so the proof of Theorem 17 is incomplete even though the underlying FPT claim is likely correct.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17106,"tokens_out":37445,"duration_ms":370467,"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":[{"comment":"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.","section":"Section 5, proof of Theorem 17"}],"minor_comments":[{"comment":"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":"Sections 4 and 5, runtime analyses"},{"comment":"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.","section":"Section 5, proof of Theorem 17"},{"comment":"There are minor typos: 'an star' should be 'a star' and 'isomporphic' should be 'isomorphic'.","section":"Abstract and Introduction"},{"comment":"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.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The gap in Theorem 17 is real but easily repairable, and I do not see other load-bearing errors. The paper is suitable for the journal once the proof is patched and the d=1 runtime expression is fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nSoft 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.\n\nBottom 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.","headline":"First parameterized complexity study of Star Decomposition, mostly sound, with a repairable gap in Theorem 17.","tokens_in":17644,"tokens_out":17542,"would_cite":true,"duration_ms":152250,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","68Q27","90C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Star decomposition's parameterized complexity is mapped, with FPT algorithms for several combined parameters and matching hardness results.","keywords":["star decomposition","edge decomposition","parameterized complexity","fixed-parameter tractability","neighborhood diversity","vertex cover","tree-depth","integer linear programming"],"falsifier":"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.","tokens_in":16639,"feed_emoji":"⭐","tokens_out":16082,"duration_ms":135448,"temperature":0.7,"pith_summary":"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.","feed_headline":"Star decomposition made FPT by neighborhood diversity and star size","feed_subtitle":"The paper maps star decomposition as FPT with combined parameters and W[1]-hard for vertex cover or star types alone.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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,Δ)."],"supporting_citations":[{"why":"Supplies the expansion-based sufficient condition for star decomposition and the orientation lemma with prescribed out-degrees that Lemma 18 generalizes.","marker":"[27]"},{"why":"Establishes the integer-programming algorithm with a fixed number of variables that solves the bounded-variable ILP formulations used for the FPT results.","marker":"[21]"},{"why":"Establishes the dual-tree-depth bound for integer programs, used to derive the FPT result for (td,s).","marker":"[12]"},{"why":"Establishes the dual-treewidth bound for integer programs, used to derive the XP result for (tw,d).","marker":"[11]"},{"why":"Shows NP-hardness of decomposing maximum-degree-4 graphs into stars of length 3, the baseline hardness result the paper starts from.","marker":"[10]"},{"why":"Shows NP-hardness of Independent Set on Hamiltonian planar cubic graphs, the reduction source for the new NP-hardness result.","marker":"[14]"},{"why":"Proves W[1]-hardness of unary bin packing parameterized by the number of bins, used in the reductions to vertex cover.","marker":"[18]"},{"why":"Proves W[1]-hardness of unary bin packing parameterized by the number of item types, used for hardness with respect to d.","marker":"[19]"}],"fun_headline_variants":["Star decomposition FPT with neighborhood diversity plus star size","W[1]-hard for vertex cover or star types alone","Star decomposition: FPT with combined parameters, W[1]-hard alone","New complexity map for star decomposition problems","Parameterized star decomposition: FPT vs W[1]-hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Star decomposition FPT with neighborhood diversity plus star size","W[1]-hard for vertex cover or star types alone","Star decomposition: FPT with combined parameters, W[1]-hard alone","New complexity map for star decomposition problems","Parameterized star decomposition: FPT vs W[1]-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000164,"raw_usage":{"total_tokens":1263,"prompt_tokens":975,"completion_tokens":288,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":205}},"tokens_in":591,"tokens_out":288,"duration_ms":3119,"temperature":1.0,"reasoning_tokens":205,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:36:32.624120+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On the decomposition of a graph into stars","cited_arxiv_id":null,"evidence_quote":"Supplies the expansion-based sufficient condition for star decomposition and the orientation lemma with prescribed out-degrees that Lemma 18 generalizes."},{"cited_title":"Integer programming and incidence treedepth","cited_arxiv_id":null,"evidence_quote":"Establishes the dual-treewidth bound for integer programs, used to derive the XP result for (tw,d)."},{"cited_title":"On the complexity of partitioning graphs into connected subgraphs","cited_arxiv_id":null,"evidence_quote":"Shows NP-hardness of decomposing maximum-degree-4 graphs into stars of length 3, the baseline hardness result the paper starts from."},{"cited_title":"Maximum independent sets in 3-and 4-regular hamiltonian graphs","cited_arxiv_id":null,"evidence_quote":"Shows NP-hardness of Independent Set on Hamiltonian planar cubic graphs, the reduction source for the new NP-hardness result."},{"cited_title":"Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines","cited_arxiv_id":"2009.11840","evidence_quote":"Proves W[1]-hardness of unary bin packing parameterized by the number of item types, used for hardness with respect to d."}],"review_version":1}