{"id":"38c3c90d-eb58-4f9f-9857-fe761d3af4c0","arxiv_id":"2607.04185","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every fixed r≥3, deciding wsat(F,H)≤k is NP-complete when H is Kr or Kr,r.","lead":"The paper proves that deciding whether the weak-saturation number of a host graph F is at most k is NP-complete for every fixed complete graph Kr and every balanced complete bipartite graph Kr,r with r≥3. It does so by polynomial reductions that import flag-no-square complexes from topology into combinatorial extremal graph theory.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claim (Theorem 1.2) rests on two clean polynomial reductions from the known NP-hard triangle case. For cliques the iterative join lifting (Lemma 3.1) is elementary and preserves the exact threshold. For balanced bipartite graphs the only non-standard ingredients are the 3-clean property and the special subdivision that produces it; both are correctly established by the cited topological lemma and a short combinatorial argument. The mixed-peeling observation and the free-face analysis that relate weak saturation to collapsibility are standard and carefully written. Consequently the reader's high-confidence ACCEPT verdict stands; the concrete check above is merely a routine sanity verification of the single most delicate combinatorial claim, not an indication of a genuine flaw.","tokens_in":15822,"tokens_out":474,"duration_ms":21773,"concrete_test":"Independently verify Lemma 4.9 on a concrete flag-no-square complex (e.g., the special subdivision of a single 2-simplex, or of the barycentric subdivision of a small shellable complex from the Tancer–Tyomkyn construction): enumerate all triples X,Y and confirm that X\times Y⊆E(G°) forces X=Y and G[X]≅K3, and that no induced C4 or K4 appears. If any counter-example triple is found, the equality of Lemma 4.3 fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption correctly isolates the most delicate step (flag-no-square of the special subdivision implying 3-clean of the 1-skeleton, so that every K3,3 in B(G) arises from a unique triangle). That step is already secured by the cited Przytycki–Świątkowski lemma (Lemma 4.8) together with the elementary case analysis of Lemma 4.9; the subsequent mixed-peeling identity (Lemma 4.3) and the balanced lifting (Lemma 4.12) then go through without further hidden assumptions. No other load-bearing gap appears in the clique-lifting argument or in the collapsibility-preservation lemmas.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves that for every fixed r≥3 and H∈{K_r,K_{r,r}}, the decision problem of whether wsat(F,H)≤k (given F and k) is NP-complete. Starting from the Tancer–Tyomkyn NP-hardness of deciding wsat(F,K_3)=n-1, the authors give polynomial reductions: iterative cone joins for cliques (Lemma 3.1), and for balanced bipartite graphs an auxiliary bipartite graph B(G) together with a 3-clean property that forces every K_{3,3} to arise from a unique triangle (Lemma 4.3). The 3-clean property is obtained by applying the special subdivision of Przytycki–Świątkowski to the Tancer–Tyomkyn complex, which yields a flag-no-square complex whose 1-skeleton is 3-clean (Lemmas 4.8–4.9). Collapsibility is preserved under subdivision (Lemmas 4.10–4.11), and a balanced lifting lemma (Lemma 4.12) extends the K_{3,3} case to all K_{r,r}. Membership in NP is elementary (Observation 2.8).","tokens_in":15991,"tokens_out":873,"duration_ms":6660,"significance":"The result cleanly extends the only previously known hardness result for weak saturation (the triangle case of Tancer–Tyomkyn) to all complete graphs and all balanced complete bipartite graphs. The technical contribution is substantial: the introduction of the 3-clean property, the mixed-peeling formalism, and especially the importation of the flag-no-square property from geometric topology into extremal graph theory supply new tools that are likely to be reusable. All reductions are fully explicit, parameter-free, and polynomial-time; the key identities are proved in detail rather than sketched. The concluding discussion of the obstacles for C_4 and unbalanced K_{s,t} is honest and useful.","major_comments":[],"minor_comments":[{"comment":"Throughout: several typographical slips (\"promblem\" in §2.2, \"This constructiongivesavalidmixed\" in the proof of Lemma 4.3, missing spaces after periods). A careful copy-edit would remove them.","section":null},{"comment":"Lemma 4.5 (mixed peeling): the induction is correct but the base case when F is H-free is only mentioned in one sentence; a one-line expansion would improve readability.","section":null},{"comment":"Lemma 4.11: the Euler-characteristic bookkeeping (χ(T)=1+s-r) is sound, yet the argument that r≤s is slightly terse; an explicit sentence that every face of R contributes at least one face of S would help.","section":null},{"comment":"Figure 1 (Z_10) is helpful; a short caption sentence identifying the three true vertices A,B,C would make the special-subdivision construction self-contained for readers unfamiliar with Dranishnikov’s complex.","section":null},{"comment":"References: the arXiv numbers of the most recent related papers (e.g., Terekhov–Zhukovskii, Ascoli–He) could be updated to journal versions if they have appeared by the time of final revision.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is ready for acceptance. The only potential referee concern (whether special subdivision truly yields a 3-clean 1-skeleton) is already settled by the cited Przytycki–Świątkowski lemma plus the elementary case analysis of Lemma 4.9; no further verification is needed. Fit for a combinatorics journal is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The punchline is that the decision problem for wsat(F,H) is NP-complete for every fixed Kr and every balanced Kr,r (r≥3). They start from the Tancer–Tyomkyn hardness for triangles and give fully explicit polynomial reductions.\n\nWhat is new is not the clique case (iterated join with a universal vertex, Lemma 3.1, is routine once you have the triangle base) but the bipartite side. They introduce 3-clean graphs, the auxiliary bipartite graph B(G), and mixed peeling, then prove the exact identity wsat(B(G),K3,3)=n+m+wsat(G,K3) whenever G is 3-clean. To feed the Tancer–Tyomkyn complexes into that identity they apply the special subdivision of Przytycki–Świątkowski, which produces flag-no-square complexes whose 1-skeletons are automatically 3-clean and K4-free. That is the first systematic use of the flag-no-square property inside weak saturation, and it works. The subsequent balanced lifting (Lemma 4.12) is clean.\n\nThe proofs are written out in detail; the collapsibility-preservation lemmas under subdivision are careful, and the Euler-characteristic bookkeeping closes. The only soft spots are minor: a couple of induction steps in the mixed-peeling argument are a bit terse, and the paper correctly notes that the same method does not reach C4 or unbalanced Ks,t. Those are honest limitations, not hidden gaps. Citations are appropriate; the external hardness is used exactly once as a black box.\n\nThis is for people who already care about the complexity of extremal parameters or about shellability of 2-complexes. It will not reorganize the field, but it settles a natural infinite family cleanly. I would send it to a serious referee without hesitation; the central claims hold.","headline":"Solid NP-completeness lift from triangles to all Kr and Kr,r via clean new combinatorial gadgets and standard topology; the proofs hold.","tokens_in":16574,"tokens_out":498,"would_cite":true,"duration_ms":6416,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C35","68Q17"],"pacs":[],"model":"grok-4.5","headline":"Deciding whether the weak saturation number of a graph for Kr or Kr,r is at most k is NP-complete for every fixed r ≥ 3.","keywords":["weak saturation","NP-complete","complete graphs","balanced bipartite graphs","flag-no-square","3-clean graphs","collapsibility","graph algorithms"],"falsifier":"Produce either a flag-no-square 2-complex whose 1-skeleton is not 3-clean, or a concrete 3-clean graph G for which wsat(B(G), K3,3) differs from |V(G)| + |E(G)| + wsat(G, K3). Either counter-example collapses the K3,3 reduction and therefore the hardness claims for all larger Kr,r.","tokens_in":16727,"feed_emoji":"🔺","tokens_out":1106,"duration_ms":20117,"temperature":0.7,"pith_summary":"The paper proves that, for every fixed integer r at least 3, the problem of deciding whether the weak saturation number of an input graph F with respect to the complete graph Kr, or with respect to the balanced complete bipartite graph Kr,r, is at most a given integer k, is NP-complete. Weak saturation asks for the fewest edges in a spanning subgraph of F from which the remaining edges of F can be added one by one so that each new edge completes a fresh copy of the target. Hardness is obtained by polynomial reductions that start from the already-hard triangle case, lift it to larger cliques by successive joins with universal vertices, and lift it to balanced bipartite targets by an auxiliary bipartite graph whose K3,3 copies are forced to come from triangles. The forcing step relies on a topological subdivision that produces flag-no-square complexes, whose 1-skeletons satisfy a new combinatorial property called 3-clean. A reader who cares about extremal graph theory learns that even for the most classical targets the exact weak-saturation threshold is computationally intractable, and that a classical topological property can control combinatorial saturation numbers.","feed_headline":"Weak saturation for Kr and Kr,r is NP-complete","feed_subtitle":"Hardness lifts from triangles by cone joins and a topological clean property.","key_machinery":"The 3-clean property (every pair of triples whose complete bipartite product appears in the closed neighborhood graph must be identical and induce a triangle) together with special subdivisions that produce flag-no-square 2-complexes. These guarantee that every K3,3 in the auxiliary bipartite graph B(G) arises from a unique triangle of G, yielding the exact identity wsat(B(G), K3,3) = n + m + wsat(G, K3). Iterated cone joins and balanced liftings then raise the target from K3 to Kr and from K3,3 to Kr,r.","core_discovery":"For every fixed integer r ≥ 3 and every target H belonging to {Kr, Kr,r}, the decision problem that takes a finite graph F and an integer k and asks whether wsat(F, H) ≤ k is NP-complete. Membership in NP follows by guessing a small initial edge set together with an addition order and verifying each step in polynomial time; NP-hardness is proved by explicit polynomial-time reductions from the known hard problem of deciding whether wsat(F, K3) equals the number of vertices minus one.","pith_inferences":["Analogous “clean” combinatorial properties may allow hardness lifts to other highly symmetric targets such as complete multipartite graphs once a matching topological subdivision is available.","Collapsibility and shellability of flag complexes may continue to classify the complexity of weak saturation for further patterns beyond cliques and balanced bipartite graphs.","Any future polynomial algorithm for unbalanced Ks,t would have to exploit the asymmetry of part sizes that the present balanced lifting deliberately avoids."],"forward_implications":["No polynomial-time algorithm exists for computing wsat(F, Kr) or wsat(F, Kr,r) unless P = NP, for every fixed r ≥ 3.","Hardness already holds on the explicit infinite family of host graphs produced by the reductions from 3-SAT.","Flag-no-square 2-complexes force their 1-skeletons to be 3-clean, giving a topological certificate that controls bipartite weak-saturation numbers.","The same technique does not decide the complexity of weak saturation for C4 or for unbalanced complete bipartite graphs Ks,t with s ≠ t."],"fun_headline_variants":["Weak saturation for Kr and Kr,r is NP-complete","Deciding wsat(F,Kr) or wsat(F,Kr,r) ≤ k is NP-complete","NP-completeness of weak saturation extends to all Kr and Kr,r","Hardness of weak H-saturation for H=Kr and balanced bipartites","wsat decision problem NP-complete for every fixed Kr and Kr,r"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The special subdivision of the input complex must stay free of induced 4-cycles and force every complete triple product of neighborhoods to come from a single triangle; if that fails, the exact link between bipartite and triangle weak-saturation numbers breaks.","fun_headline_variants_meta":{"raw":{"variants":["Weak saturation for Kr and Kr,r is NP-complete","Deciding wsat(F,Kr) or wsat(F,Kr,r) ≤ k is NP-complete","NP-completeness of weak saturation extends to all Kr and Kr,r","Hardness of weak H-saturation for H=Kr and balanced bipartites","wsat decision problem NP-complete for every fixed Kr and Kr,r"]},"model":"grok-4.5","effort":"low","cost_usd":0.005624,"raw_usage":{"total_tokens":1536,"prompt_tokens":802,"num_sources_used":0,"completion_tokens":111,"cost_in_usd_ticks":56240000,"prompt_tokens_details":{"text_tokens":802,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":623,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":802,"tokens_out":111,"duration_ms":5682,"temperature":1.0,"reasoning_tokens":623,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T06:59:42.806737+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Produce either a flag-no-square 2-complex whose 1-skeleton is not 3-clean, or a concrete 3-clean graph G for which wsat(B(G), K3,3) differs from |V(G)| + |E(G)| + wsat(G, K3). Either counter-example collapses the K3,3 reduction and therefore the hardness claims for all larger Kr,r.","supporting_citations":[],"review_version":2}