{"id":"3539b110-677b-4d9b-afba-6358f8ad3957","arxiv_id":"1908.09065","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A rooted graph with no two vertex-disjoint S-cycles always has an S-cycle hitting set of size at most four, and three do not suffice.","lead":"The paper determines the exact smallest size of a hitting set for S-cycles when a graph has no two vertex-disjoint S-cycles: four vertices always suffice, and a 21-vertex example shows three do not. Readers in graph theory and parameterized algorithms get a tight packing-covering constant for a rooted-cycle variant.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof gap in Proposition 6.9: Claim 6.11 cites Claim 5.4, a separation lemma proved for K'''_3-subdivisions, to justify the same separation in a K''''_4-subdivision; no replacement argument is given.","rationale":"I read the paper as proving Theorem 1.2 through a finite reduction: every S-cycle subdivision is extended, via Lemma 4.3, until it reaches one of a short list of structures whose branching vertices plus one gate form a hitting set. The early machinery (Lemmas 4.1, 4.3, 4.5) is sound, and the 21-vertex example's case analysis is plausible. The main risk is exactly what the reader identified: an unverified case analysis. I found one concrete instance of that risk: in Proposition 6.9, Claim 6.11 invokes Claim 5.4, which was proved for a K'''_3-subdivision and whose notation and hypotheses do not match the K''''_4-subdivision at hand. This is not an objection to the plausibility of the theorem, and the gap may be fillable, but as written the proof is incomplete at a load-bearing point. The verdict should therefore be conditional on repairing this cross-reference and supplying the missing separation argument.","tokens_in":26007,"tokens_out":18652,"duration_ms":190519,"concrete_test":"Derive the separation assertion in Claim 6.11 of Proposition 6.9 directly from Lemma 4.1 and the path-exclusion facts already proved for the K''''_4-subdivision, without citing Claim 5.4. Concretely, prove or disprove: for I = {j : G-T has a (P_j, Q^1_{v1})-path}, the gate z of Q1 closer to v1 separates (∪_{j∈I}P_j) ∪ Q^1_{v1} from the rest of W in G-T. If the derivation succeeds, replace the citation of Claim 5.4 with this new argument; if it fails, Proposition 6.9 is unsupported and the K''''_4 branch of Theorem 1.2 is unproved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Proposition 6.9 handles the case where G contains an S-cycle K''''_4-subdivision. In its Claim 6.11, after finding a gate z of Q1, the text says \"By Claim 5.4, z separates (∪_{j∈I}P_j) ∪ Q^1_{v1} and the rest of W in G-T.\" But Claim 5.4 was proved inside Proposition 5.2 for a K'''_3-subdivision with a different path system: there P^i run from v1 to v2, Q^1 runs from v2 to v3, and Q^1_{v2} is the component of Q^1 at v2. In Proposition 6.9 the graph W is a K''''_4-subdivision: Q^1 runs from v4 to v1, so the notation Q^1_{v2} has no referent and the separation statement does not follow from Claim 5.4. No other argument in the text proves this separation. Since Claim 6.11 is needed to rule out S-cycles through Q^1_mid, and Proposition 6.9 is one of the structural branches closing Theorem 1.2, the proof as written has a load-bearing gap at this point. The gap looks repairable, but it is not established in the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Erdős–Pósa-type parameter for S-cycles in rooted graphs (G,S), where an S-cycle is a cycle meeting a prescribed vertex set S. It proves Theorem 1.2: if μ(G,S) ≤ 1, then there is an S-cycle hitting set of size at most 4. It also constructs, in Theorem 1.1, a 21-vertex rooted graph with μ(G,S)=1 and τ(G,S) ≥ 4, showing that the bound 4 is tight. The proof of Theorem 1.2 proceeds by contradiction: assuming τ(G,S) > 4, the authors start from an S-cycle subgraph and repeatedly use Lemma 4.3 to force larger S-cycle subdivisions, eventually reducing to the cases K4, W4, and K'_3,3. Sections 5–8 contain a long case analysis showing that each structural branch either produces an S-cycle K'_3,3-subdivision or yields an S-cycle hitting set of size at most 4.","tokens_in":26241,"tokens_out":18227,"duration_ms":176282,"significance":"If correct, the paper resolves the k=2 case for S-cycles by determining the tight bound τ ≤ 4, in contrast to the bound 3 for ordinary cycles. This is a natural and nontrivial result with direct connections to the Subset Feedback Vertex Set problem. The paper’s main strengths are the explicit 21-vertex extremal example with a fully worked verification, the parameter-free derivation of the upper bound, and a self-contained proof that does not rely on circular arguments or unstated numerical inputs. The proof is long and mostly hand-verified rather than machine-checked, but the overall strategy is transparent and the individual lemmas are carefully organized.","major_comments":[],"minor_comments":[{"comment":"The sentence “By Claim 5.4, z separates (∪_{j∈I}P^j) ∪ Q^1_{v1} and the rest of W in G−T” is formally unjustified, because Claim 5.4 is proved inside Proposition 5.2 for a K'''_3-subdivision in which Q^1 runs from v2 to v3 and refers to Q^1_{v2}, whereas in Proposition 6.9 Q^1 runs from v4 to v1 and the relevant side is Q^1_{v1}. The needed separation does follow from the immediately preceding no-path assertion, the earlier observation that there is no (P^i,P^j)-path in G−T, and the fact that z is the boundary of the segment Q^1_{v1}; the authors should replace the incorrect citation with this short self-contained argument.","section":"§6.9, Claim 6.11"},{"comment":"In the definition of the auxiliary graph F, the displayed vertex set appears to contain a duplicated entry and to omit R^1_1; it should be {R^1_1, R^1_2, R^2_1, R^2_2, A1, A2, Q^1_{v1}, Q^1_{v2}}.","section":"§6.5, Claim 6.8"},{"comment":"The first paragraph of the proof says “In each case, we can observe that C2 contains neither y2 nor z2” without explicitly enumerating the cases; adding a sentence describing the two symmetric choices for C1 would make the verification easier for the reader.","section":"§3, proof of Theorem 1.1"}],"recommendation":"minor_revision","confidential_remarks":"I found no fatal gap in the main derivation. The one technical issue, the misplaced citation to Claim 5.4 in Proposition 6.9, is local and repairable with a short argument that is already implicit in the surrounding text. The length and complexity of the case analysis make the paper demanding to referee, but I did not find evidence of a deeper structural problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves a genuinely new tight result: if a rooted graph has no two vertex-disjoint S-cycles, then four vertices hit all S-cycles, and the explicit 21-vertex example shows three do not suffice. That is a clean analogue of Lovász's three-vertex theorem for ordinary cycles and a sharpening of the known Erdős-Pósa results for S-cycles. The lower-bound example is convincing, and the overall strategy—start with an S-cycle, grow it to one of a few exceptional subdivisions, then find a small hitting set for each—is sensible. Lemmas 4.3–4.6 are the right tools and appear sound.\n\nThe soft spot is a genuine gap in Proposition 6.9, Claim 6.11. The claim asserts, by citing Claim 5.4, that a certain gate separates a union of P-paths plus Q1_v1 from the rest of the W in G-T. But Claim 5.4 was proved inside Proposition 5.2 for a K'''_3-subdivision with a different path system: there Q1 runs from v2 to v3 and Q1_v2 has a clear referent. In the K'''_4-subdivision of Proposition 6.9, Q1 runs from v4 to v1, so Q1_v2 does not even make sense and the separation does not follow from Claim 5.4. No replacement argument is given. Since Claim 6.11 is used to rule out S-cycles through Q1_mid and Proposition 6.9 is one of the main branches closing Theorem 1.2, this is a load-bearing hole in the written proof. It is likely repairable—the same style of argument may work with Q1_v1 and the K'''_4 topology—but the authors need to supply it.\n\nThe citation pattern is fine; self-citations are to directly relevant earlier work. The paper is aimed at specialists in structural graph theory, the Erdős-Pósa property, or subset feedback vertex set. It deserves a serious referee, not a desk reject, but the referee should require a complete proof of Claim 6.11 before acceptance. This is a solid, significant result waiting for a patch, not a paper that should be waved through as is.","headline":"Tight bound of 4 for S-cycle hitting sets is plausible and the counterexample is solid, but Proposition 6.9 has a load-bearing gap: Claim 6.11 cites Claim 5.4 in a different subdivided graph where the notation and the separation argument do not carry over as written.","tokens_in":26813,"tokens_out":3971,"would_cite":true,"duration_ms":35120,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C38","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"For rooted graphs with no two disjoint S-cycles, four vertices always hit every S-cycle, and three are not enough in general.","keywords":["S-cycles","rooted graph","hitting set","vertex-disjoint cycles","cycle packing","subdivision","tight bound","feedback vertex set"],"falsifier":"A single rooted graph with no two vertex-disjoint S-cycles but with $\\tau(G,S)\\ge 5$ would disprove the upper bound; such a graph could be sought by exhaustive search on small graphs with an exact packing-hitting computation. As a sanity check, the paper's own 21-vertex example should have $\\tau(G,S)=4$.","tokens_in":1592,"feed_emoji":"🎯","tokens_out":9437,"duration_ms":192625,"temperature":0.7,"pith_summary":"The paper determines the exact packing-covering constant for constrained cycles in rooted graphs. Given a graph $G$ and a set $S$, an $S$-cycle is a cycle that meets $S$; $\\mu(G,S)$ is the maximum number of pairwise vertex-disjoint $S$-cycles and $\\tau(G,S)$ is the minimum size of a vertex set meeting all $S$-cycles. The main theorem states that $\\mu(G,S)\\le 1$ implies $\\tau(G,S)\\le 4$. The authors also construct a 21-vertex rooted graph with $\\mu(G,S)=1$ but $\\tau(G,S)\\ge 4$, so the constant four is tight and cannot be reduced to three.","feed_headline":"Four vertices always hit all S-cycles; three do not always","feed_subtitle":"A 21-vertex example shows three can fail, while a new proof caps every such graph at four.","key_machinery":"The proof rests on the notion of an $S$-cycle subgraph, a subgraph whose every cycle is an $S$-cycle, and on $W$-extensions: paths that start and end in $W$, have no internal vertices in $W$, and whose addition to $W$ preserves the property that every cycle is an $S$-cycle. Lemma 4.3 says that if $W$ is an $S$-cycle subgraph and $T\\subseteq S\\cap V(W)$ hits all $S$-cycles of $W$, then any $S$-cycle of $G-T$ either meets $W$ in exactly one vertex or contains a $W$-extension. Repeated application of this lemma, together with a bound from Lemma 4.5 on the size of small hitting sets in subdivisions, forces the existence of larger and larger $S$-cycle subdivisions. The analysis in Sections 5$-$8 shows that only certain unavoidable configurations can stop this growth, and each yields a four-vertex hitting set.","core_discovery":"The central discovery is that the $S$-cycle analogue of the classical three-vertex theorem for ordinary cycles fails by exactly one vertex. For every rooted graph $(G,S)$, if $\\mu(G,S)\\le 1$, then $\\tau(G,S)\\le 4$. Moreover, there is a rooted graph on 21 vertices with $\\mu(G,S)=1$ and $\\tau(G,S)\\ge 4$, so the constant 4 is best possible. The upper bound is proved by a structural case analysis. Assuming $\\tau>4$, the proof grows an $S$-cycle subdivision by repeatedly adding paths that preserve the property that all cycles are $S$-cycles, eventually forcing one of a finite list of special subdivisions. Each such terminal subgraph is then shown to admit an $S$-cycle hitting set of size at most four, contradicting $\\tau>4$.","pith_inferences":["Editorial inference: the 21-vertex example may not be vertex-minimal; a computer search could reveal a smaller counterexample.","Editorial inference: the subdivision-enlargement scheme might generalize to the case $\\mu(G,S)\\le 2$, but it is unclear whether the list of terminal configurations remains finite.","Editorial inference: the proof's explicit finite terminal shapes suggest that $\\tau\\le 4$ can be certified in polynomial time by either finding a forbidden structure or exhibiting a four-vertex hitting set.","Editorial inference: comparing ordinary cycles and S-cycles, the off-by-one gap may be a sign that other constrained-cycle classes require their own exact small-packing analyses."],"forward_implications":["Every rooted graph with no two vertex-disjoint S-cycles has a set of at most four vertices meeting all S-cycles; this yields a constant-size deletion set in such graphs.","The 21-vertex example proves that three vertices are insufficient, so the theorem cannot be improved to a smaller constant.","The result confirms that the classical three-vertex theorem for ordinary cycles does not extend unchanged to S-cycles; the correct constant is exactly one larger.","For the next open case, rooted graphs with no three vertex-disjoint S-cycles, the proof structure suggests a finite case analysis but does not determine the constant."],"supporting_citations":[{"why":"Supplies the classical result that three vertices hit all cycles when no two cycles are disjoint; this is the unrooted baseline whose S-cycle analogue the paper determines.","marker":"[12]"},{"why":"Establishes the general packing-hitting theorem for cycles that motivates the question and whose k=2 case is here made exact.","marker":"[5]"},{"why":"Provides the analogous tight constant for three ordinary cycles, against which the S-cycle constant four is compared.","marker":"[20]"}],"fun_headline_variants":["S-cycle hitting set: optimal size is 4","For no two disjoint S-cycles, 4 vertices always hit all","Three vertices can miss S-cycles; four never do","Best possible bound: 4 vertices for S-cycle hitting","S-cycles: 4 hits all, 3 not enough"],"cache_read_input_tokens":28928,"weakest_assumption_plain":"The proof requires that the recursive case analysis in Sections 5 through 8 is exhaustive: every S-cycle subdivision that cannot be extended must be one of the listed special structures, and each such structure must admit a hitting set of size at most four. If a structural case is missed, the contradiction argument for $\\tau(G,S)>4$ does not go through.","fun_headline_variants_meta":{"raw":{"variants":["S-cycle hitting set: optimal size is 4","For no two disjoint S-cycles, 4 vertices always hit all","Three vertices can miss S-cycles; four never do","Best possible bound: 4 vertices for S-cycle hitting","S-cycles: 4 hits all, 3 not enough"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000742,"raw_usage":{"total_tokens":3268,"prompt_tokens":858,"completion_tokens":2410,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":2325}},"tokens_in":474,"tokens_out":2410,"duration_ms":17609,"temperature":1.0,"reasoning_tokens":2325,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:24:29.557487+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A single rooted graph with no two vertex-disjoint S-cycles but with $\\tau(G,S)\\ge 5$ would disprove the upper bound; such a graph could be sought by exhaustive search on small graphs with an exact packing-hitting computation. As a sanity check, the paper's own 21-vertex example should have $\\tau(G,S)=4$.","supporting_citations":[{"cited_title":"Lapok 16 (1965), 289–299","cited_arxiv_id":null,"evidence_quote":"Supplies the classical result that three vertices hit all cycles when no two cycles are disjoint; this is the unrooted baseline whose S-cycle analogue the paper determines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the general packing-hitting theorem for cycles that motivates the question and whose k=2 case is here made exact."},{"cited_title":"Voss, Eigenschaften von Graphen, die keine k ` 1 knotenfremde Kreise enthalten , Math","cited_arxiv_id":null,"evidence_quote":"Provides the analogous tight constant for three ordinary cycles, against which the S-cycle constant four is compared."}],"review_version":1}