{"id":"d51da109-ed96-446d-a21f-bd858578e254","arxiv_id":"2606.31873","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Establishes tight n^{Theta(k^{d-1})} runtime bounds for d-Clique Packing parameterized by clique-width under ETH for fixed d >= 3.","lead":"The paper gives an algorithm for deciding if a graph contains t vertex-disjoint d-cliques that runs in n to the power O of k to the d-1 when the graph has clique-width k and a k-expression is given; it also proves this is optimal under ETH. A smart generalist might read it to understand the precise computational limits for packing problems on graphs with bounded clique-width.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader correctly isolated the ETH as the weakest (external) assumption. Full-text review does not surface any additional load-bearing risk to the correctness of the stated bounds or the reduction strategy.","tokens_in":1787,"tokens_out":243,"duration_ms":43464,"concrete_test":"Re-derive the exponent in the DP recurrence (likely §3 or §4) for d=3 by counting the number of ways to label the bags with partial clique information; confirm it is at most O(k^2) rather than higher.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is an n^{O(k^{d-1})} DP algorithm for d-Clique Packing (k-expression given) together with an ETH-based n^{o(k^{d-1})} lower bound already for d-Clique Partition. The ETH assumption is explicitly flagged and is the sole external hypothesis required for tightness; the algorithmic side follows the standard clique-width DP template with state size governed by the fixed d. No internal inconsistency, hidden assumption on boundedness, or mismatch between the general and partition cases is apparent.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies the d-Clique Packing problem (decide if a graph contains t vertex-disjoint d-cliques) and its special case d-Clique Partition. For each fixed d≥3 it gives an algorithm running in n^{O(k^{d-1})} time when a k-expression is provided, and proves that, under ETH, no n^{o(k^{d-1})} algorithm exists even for d-Clique Partition. The lower bound also implies W[1]-hardness parameterized by clique-width.","tokens_in":1904,"tokens_out":379,"duration_ms":20206,"significance":"If correct, the results supply the first ETH-tight bounds for a natural packing problem on clique-width, extending the Fomin et al. program. The algorithmic side follows the standard clique-width DP template with state size governed by fixed d; the matching lower bound is obtained via an explicit reduction from a known ETH-hard problem. These are concrete strengths.","major_comments":[],"minor_comments":[{"comment":"§3, the DP recurrence for the general packing case: the transition when introducing a new label is described only at a high level; an explicit enumeration of the O(k^{d-1}) states would help verify the exponent.","section":"§3"},{"comment":"The W[1]-hardness claim is derived from the ETH lower bound but is stated without a separate parameterized reduction; a short paragraph clarifying the parameter dependence would avoid any ambiguity.","section":"§5"},{"comment":"Figure 1 (the reduction gadget) uses a non-standard notation for the clique-width labels; adding a small legend would improve readability.","section":"Figure 1"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive assessment of the paper, the accurate summary of its contributions, and the recommendation of minor revision. The results are correctly described as providing the first ETH-tight bounds for a natural packing problem parameterized by clique-width.","responses":[],"tokens_in":1248,"tokens_out":58,"duration_ms":25495,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that d-Clique Packing by clique-width has a tight bound of n to the Theta of k to the d-1. They give an explicit DP algorithm that runs in n^{O(k^{d-1})} when a k-expression is provided, and an ETH lower bound showing no n^{o(k^{d-1})} algorithm exists even for the partition version when d is fixed and at least 3.\n\nWhat is actually new is the precise dependence on d in the exponent for both the upper and lower bounds. This does not follow immediately from the earlier Max-Cut and Edge Dominating Set results, so the construction here is specific to tracking d-clique packings in the DP states over the expression tree.\n\nThe algorithmic side follows the usual clique-width DP template but with state size governed by combinations up to d-1, which produces the claimed exponent. The lower bound is stronger because it already applies to d-Clique Partition, and the W[1]-hardness comes along as a corollary. Both directions look consistent with the abstract.\n\nNo load-bearing flaws stand out. The ETH assumption is the standard external hypothesis and is clearly stated. The input model with the k-expression given is the usual one for these problems. If the full paper spells out the recurrence and the reduction without loose constants or special cases for small d, the claims should hold.\n\nThis is for researchers working on fine-grained parameterized complexity for graph problems on bounded clique-width. It fits directly into the program of ETH-tight results for packing and covering problems.\n\nI would send it to peer review. The bounds are precise enough and the techniques are worth a close technical check.","headline":"The paper delivers tight ETH bounds of n^{O(k^{d-1})} and no n^{o(k^{d-1})} for d-Clique Packing parameterized by clique-width.","tokens_in":2402,"tokens_out":426,"would_cite":false,"duration_ms":41950,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"d-Clique Packing can be solved in n^{O(k^{d-1})} time parameterized by clique-width k, with a matching ETH lower bound for d >= 3.","keywords":["clique packing","clique-width","parameterized complexity","exponential time hypothesis","dynamic programming","W[1]-hardness","graph algorithms","partition problems"],"falsifier":"An algorithm solving d-clique packing in time n^{o(k^{d-1})} for some fixed d at least 3 on graphs with given k-expression would falsify the lower bound.","tokens_in":2694,"feed_emoji":"","tokens_out":653,"duration_ms":61694,"temperature":0.7,"pith_summary":"The paper proves an algorithm for finding t disjoint d-sized cliques in a graph that runs in time n to the power of O(k to the d minus 1), where k is the clique-width and the expression is given. It shows that this is the best possible under the exponential time hypothesis, as no algorithm with a smaller exponent in the power of k exists for d at least 3. This holds even when the task is to cover all vertices with such cliques. The result also establishes that the problem is hard for the W[1] class when parameterized by clique-width. Readers care because these bounds tell exactly how the graph's construction complexity affects the packing task.","feed_headline":"d-clique packing has n^{O(k^{d-1})} algorithm","feed_subtitle":"The bound is tight under ETH even for partitioning into d-cliques, for any d at least 3.","key_machinery":"Dynamic programming on the parse tree of the given k-expression, with states sized to produce the O(k^{d-1}) exponent in the runtime.","core_discovery":"For each fixed d >= 3, the d-Clique Packing problem admits an algorithm running in n^{O(k^{d-1})} time on graphs of clique-width k when a k-expression is given. Assuming the Exponential Time Hypothesis, no algorithm exists with runtime n^{o(k^{d-1})} even for the d-Clique Partition problem. The proof also shows W[1]-hardness of both problems parameterized by clique-width.","pith_inferences":["Similar exponent patterns might appear in other packing or covering problems parameterized by clique-width.","The results highlight that providing the k-expression is key to achieving the upper bound.","One could test whether the bounds extend to related problems like packing other subgraphs of size d."],"forward_implications":["The problem is solvable in polynomial time for any constant clique-width.","The same upper and lower bounds apply to d-Clique Partition.","The problems are W[1]-hard parameterized by clique-width for d >= 3.","The exponent in the runtime depends on d but not on the number of cliques t."],"fun_headline_variants":["Tight ETH bounds for d-clique packing by clique-width","d-clique packing admits n^{O(k^{d-1})} time algorithm","No n^{o(k^{d-1})} for d-clique packing under ETH","W[1]-hard d-clique packing parameterized by clique-width"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The exponential time hypothesis holds.","fun_headline_variants_meta":{"raw":{"variants":["Tight ETH bounds for d-clique packing by clique-width","d-clique packing admits n^{O(k^{d-1})} time algorithm","No n^{o(k^{d-1})} for d-clique packing under ETH","W[1]-hard d-clique packing parameterized by clique-width"]},"model":"grok-4.3","cost_usd":0.006825,"raw_usage":{"total_tokens":3188,"prompt_tokens":701,"num_sources_used":0,"completion_tokens":78,"cost_in_usd_ticks":68249500,"prompt_tokens_details":{"text_tokens":701,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2409,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":701,"tokens_out":78,"duration_ms":32697,"temperature":1.0,"reasoning_tokens":2409,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-01T02:28:29.287831+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An algorithm solving d-clique packing in time n^{o(k^{d-1})} for some fixed d at least 3 on graphs with given k-expression would falsify the lower bound.","supporting_citations":[],"review_version":1}