{"id":"f19af3ab-a222-4a51-ae48-736123a6db26","arxiv_id":"2607.07697","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For fixed t, both C_t and Θ_t have the induced Erdős–Pósa property for induced minors with hitting set size O(tk log k), implying O(tk log k)-dominated balanced separators and a QPTAS for MWIS in kΘ_t-induced-minor-free graphs.","lead":"Long cycles and thetas as induced minors satisfy an induced Erdős–Pósa property: either many pairwise anti-adjacent copies exist, or few closed neighborhoods hit them all. This settles special cases of two structural conjectures and yields quasipolynomial approximation schemes for independent set in the corresponding graph classes.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript supplies complete, self-contained proofs of the stated special cases of the two conjectures, with algorithmic versions where detection is feasible (Ξ_⩾t and C_t) and an honest existential statement for Θ_t. The technical machinery (short models + ear growth + measure/guidance for the existential case) is carefully developed and the charging works. The reader’s weakest-assumption identification is accurate but already handled inside the paper; no further load-bearing concern surfaces under scrutiny. Verdict remains ACCEPT.","tokens_in":40467,"tokens_out":533,"duration_ms":7641,"concrete_test":"Independently re-derive the bound of Theorem 5.2 for a subcubic multigraph that arises after exactly ℓ proper ear additions starting from Θ_0 (so n_⩽2 ⩽ O(1), n_|| ⩽ O(1), n_3 ⩾ 2ℓ). Confirm that the packing of k thetas still holds whenever n_3 ⩾ f_Θ(k)+O(1); if the constant factors force a super-linear dependence on the initial model size, the O(tk log k) claim would need adjustment.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 1.3, 1.5, 1.6) rest on short t-models, controlled ear addition (Lemmas 2.8–2.9, 2.12–2.13, 6.7), and packing of cycles/thetas in the resulting nearly-cubic multigraphs (Simonovits + new Theorem 5.2). The reader correctly flags the packing step after ear growth as the weakest link, but the paper already accounts for it: Observation 2.11 bounds n_⩽2 and parallel edges by the (constant-size) initial model plus improper steps; Theorem 5.2 explicitly penalizes both (n_3 ⩾ f_Θ(k)+8n_⩽2+18n_||); and the charging arguments in §§3 and 6.3 absorb the resulting O(log k) into the stated O(tk log k) bound with explicit constants. No hidden assumption or gap appears in the reduction from packing to the induced packing/hitting statements, nor in the derivation of dominated separators (Lemma 8.1 + Corollary 7.6). The only acknowledged open point (algorithmic detection of Θ_t itself) is cleanly isolated and does not affect the existential claims.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves that for every fixed t, both long cycles C_t and long thetas Θ_t have the induced Erdős–Pósa property with respect to the induced-minor relation: every graph G either contains k pairwise vertex-disjoint anti-adjacent induced-minor models of the object, or admits a set X of size O(tk log k) whose closed neighbourhood hits every such model. The algorithmic version is obtained for the intermediate object Ξ_⩾t (t-long three-path configurations) via short t-models, controlled ear addition, and packing theorems for cycles and thetas in nearly-cubic multigraphs; the existential statements for C_t and Θ_t follow by reduction. The same machinery yields O(tk log k)-dominated balanced separators in the corresponding free classes, confirming a special case of the Gartland–Lokshtanov conjecture and producing a QPTAS for MWIS (and hereditary (tw⩾r,ψ)-MWIS) in kΘ_t-induced-minor-free graphs.","tokens_in":40724,"tokens_out":953,"duration_ms":10051,"significance":"The work settles a natural special case of the induced-minor Erdős–Pósa conjecture of Ahn–Gollin–Huynh–Kwon and of the dominated-separator conjecture of Gartland–Lokshtanov, both of which have been open even for cycles and thetas. The short-t-model / ear-decomposition technique is cleanly developed and reusable; the packing lemma for thetas (Theorem 5.2) that accounts for parallel edges and low-degree vertices is a useful technical contribution in its own right. The algorithmic consequences (QPTAS for MWIS and hereditary CMSO2 problems) are immediate from known blob-graph machinery once the separators are available, and the paper carefully isolates the remaining open detection problem for Θ_t itself. The O(tk log k) bound matches the classical non-induced order of magnitude up to the linear factor in t, and the lower-bound discussion is honest.","major_comments":[],"minor_comments":[{"comment":"The constant λ = 896(λ_Sim + 1) appearing in the proof of Theorem 1.3 (and the analogous constant in §6.3) is never written out explicitly in the statement of the theorems; a short remark that the O-notation hides a concrete (albeit large) absolute constant would help readers who wish to track the dependence.","section":"§3, proof of Theorem 1.3"},{"comment":"Figure 3 is referenced as showing an induced-minor model of Θ_t that does not contain Ξ_⩾t-1, but the caption and surrounding text could more clearly label the degree-3 bags versus the degree-2 vertices so that the necessity of the +2 slack in Lemma 1.4 is immediately visible.","section":"§4.1, Figure 3"},{"comment":"In the definition of a short t-model (Definition 2.5) the phrase “any ear of distance at least t+3 is of length more than t” is slightly ambiguous when the ear is a loop on a single edge; a parenthetical clarification would remove any doubt.","section":"Definition 2.5"},{"comment":"The algorithmic claim of Theorem 1.7 states running time n^{O(tk log k)}; it would be useful to note that the exponent is linear in the size of the separator returned by the recursive procedure, so that the dependence is fully explicit.","section":"Theorem 1.7"}],"recommendation":"accept","confidential_remarks":"The manuscript is already in excellent shape for a top combinatorics journal. The only non-algorithmic step (detection of Θ_t) is cleanly isolated and does not affect the existential claims that form the core of the paper. I see no reason to request a major revision."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the induced Erdős–Pósa property for long cycles and long thetas as induced minors, with the O(tk log k) bound, and gets the corresponding dominated balanced separators. That is the first infinite family of non-trivial planar graphs for both the Ahn–Gollin–Huynh–Kwon conjecture and the Gartland–Lokshtanov separator conjecture, and it immediately gives the expected QPTAS for MWIS (and hereditary CMSO variants) on those classes.\n\nWhat is new is the technical core: short t-models (guarded bags of size O(1) plus controlled ears), the ear-addition lemmas that preserve shortness, the “winning scenario” that lets them escape the single-component corner case for 3PCs, and the reduction that turns a packing of thetas in the nearly-cubic multigraph into an induced packing of Ξ_⩾t. Theorem 5.2 (packing thetas while penalizing degree-⩽2 vertices and parallel edges) is a useful intermediate lemma. The recursive charging with convexity of x log x is standard but carefully quantified, and they give explicit constants.\n\nThe soft spots are minor and already flagged by the authors. Detection of Θ_t itself remains open, so the packing/hitting statement for thetas is only existential; they isolate this cleanly and still obtain the algorithmic result for the intermediate object Ξ_⩾t and for holes. The packing theorems after ear growth are the weakest link, but Observation 2.11 bounds the junk (n_⩽2 and parallels) by the constant-size start plus improper steps, Theorem 5.2 charges for them, and the O(log k) is absorbed into the stated bound. No circularity, no free parameters, full proofs supplied.\n\nThis is for people working on induced minors, packing/hitting, or approximation on hereditary classes. A specialist can verify the arguments. It deserves a serious referee; I would accept it for peer review and expect it to appear after the usual polishing of constants and exposition.","headline":"Solid special cases of two open conjectures via a clean short-model + ear framework; the packing step after ear growth is controlled and the proofs check out.","tokens_in":41426,"tokens_out":516,"would_cite":true,"duration_ms":6611,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C83","05C85"],"pacs":[],"model":"grok-4.5","headline":"Long induced cycles and thetas pack or are hit by O(tk log k) neighborhoods.","keywords":["induced Erdős–Pósa","induced minors","long holes","thetas","dominated balanced separators","QPTAS","Maximum Weight Independent Set"],"falsifier":"A concrete infinite family of graphs in which the maximum number of pairwise anti-adjacent induced C_t-minors (or Θ_t-minors) is k, yet every hitting set of closed neighborhoods has size ω(tk log k).","tokens_in":41379,"feed_emoji":"🔗","tokens_out":626,"duration_ms":5773,"temperature":0.7,"pith_summary":"The paper proves that long cycles and long thetas, viewed as induced minors, obey an induced Erdős–Pósa property: in any graph you can either pack many pairwise non-adjacent copies of them, or hit every copy with the closed neighborhoods of only O(tk log k) vertices. The argument works by building short t-models of a core graph and repeatedly adding carefully chosen ears until the model becomes rich enough to apply classical packing theorems for cycles or thetas; the remaining components are then handled by recursion. Because the same bound also produces small dominated balanced separators in graphs that exclude k such thetas, the authors obtain a quasipolynomial-time approximation scheme for Maximum Weight Independent Set (and several generalizations) on those graphs. A sympathetic reader cares because the result settles a concrete special case of two widely discussed conjectures that aim to lift classical minor theorems into the induced-minor world.","feed_headline":"Long holes and thetas pack or fall to O(tk log k) hits","feed_subtitle":"Induced packing of cycles and thetas yields separators and a QPTAS for independent set","key_machinery":"The short t-model of a multigraph H (together with controlled ear addition that preserves shortness). It encodes an induced-minor model whose bags are short enough that classical packing theorems for cycles or thetas inside H translate directly into an induced packing of long holes or long three-path configurations in the original graph.","core_discovery":"For every fixed t, both the cycle C_t and the theta Θ_t have the induced Erdős–Pósa property under the induced-minor relation: any graph either contains k pairwise vertex-disjoint anti-adjacent induced-minor models of the object, or admits a set X of size O(tk log k) whose closed neighborhood hits every such model.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Long holes and thetas pack or hit via O(tk log k) neighborhoods","Induced packing of C_t, Θ_t or O(tk log k) closed hits","K anti-adjacent long cycles/thetas or O(tk log k) hitter set","Fixed t: long cycles, thetas pack induced or O(tk log k) cover","Pack long induced holes/thetas or N[X] hits all with |X|=O(tk log k)"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The classical packing theorems for cycles and for thetas still apply after the ear-addition process has introduced only a controlled number of parallel edges and low-degree vertices.","fun_headline_variants_meta":{"raw":{"variants":["Long holes and thetas pack or hit via O(tk log k) neighborhoods","Induced packing of C_t, Θ_t or O(tk log k) closed hits","K anti-adjacent long cycles/thetas or O(tk log k) hitter set","Fixed t: long cycles, thetas pack induced or O(tk log k) cover","Pack long induced holes/thetas or N[X] hits all with |X|=O(tk log k)"]},"model":"grok-4.5","effort":"low","cost_usd":0.010506,"raw_usage":{"total_tokens":2443,"prompt_tokens":942,"num_sources_used":0,"completion_tokens":105,"cost_in_usd_ticks":105060000,"prompt_tokens_details":{"text_tokens":942,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1396,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":942,"tokens_out":105,"duration_ms":86846,"temperature":1.0,"reasoning_tokens":1396,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T18:13:10.241157+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"A concrete infinite family of graphs in which the maximum number of pairwise anti-adjacent induced C_t-minors (or Θ_t-minors) is k, yet every hitting set of closed neighborhoods has size ω(tk log k).","supporting_citations":[],"review_version":2}