Graphs without two vertex-disjoint $S$-cycles

Minjeong Kang; Myounghwan Lee; O-joung Kwon

Graphs without two vertex-disjoint $S$-cycles

T0 review · 0 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For rooted graphs with no two disjoint S-cycles, four vertices always hit every S-cycle, and three are not enough in general.

desk verdict 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. read the letter →

arxiv 1908.09065 v2 pith:5HWRHLZZ submitted 2019-08-24 math.CO

Minjeong Kang , O-joung Kwon , Myounghwan Lee This is my paper · ORCID

classification math.CO MSC 05C3805C70

keywords S-cyclesrootedgraphhittingsetvertex-disjointcyclescyclepackingsubdivisiontightboundfeedbackvertex

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

Referee Report

0 major / 3 minor

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.

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.

minor comments (3)

[§6.9, Claim 6.11] 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.
[§6.5, Claim 6.8] 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}}.
[§3, proof of Theorem 1.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a forward structural case analysis from the definitions; cited prior work is background, and the claimed bound is not assumed.

full rationale

Running the derivation chain from Definitions 2.1–2.2 through Lemmas 4.1–4.7 and the case analyses in Sections 5–8, I find no step in which a claimed conclusion is identical to an input by construction. The main theorem is proved by contradiction: having assumed μ(G,S) ≤ 1 and τ(G,S) > 4, the proof uses the definition of τ > 4 to obtain an S-cycle in each G − T for small candidate T; this is definitional but not circular, since the same definition is what a hitting-set statement means. The candidate sets T are constructed from the current S-cycle subdivision W (e.g., branching vertices plus chosen S-vertices or gates), and the work in each proposition is to show G − T has no S-cycle, which is a genuinely independent separation/case-analysis argument. The 21-vertex example of Theorem 1.1 is explicitly checked by enumerating possible T, not fitted to Theorem 1.2. Citations to Lovász, Erdős–Pósa variations, and the subset-feedback-vertex-set literature are background/context; the only self-citation (ref. [11]) appears in an introductory list and is not load-bearing. I note two correctness concerns that are not circularity: Lemma 4.6 invokes Lemma 4.3 without restating its T ⊆ S ∩ V(W) hypothesis, and Claim 6.11 applies Claim 5.4 (proved for a K'''_3-subdivision) to a K''''_4-subdivision without a replacement argument. These concern proof completeness, not equivalence of inputs and outputs.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

No fitted parameters, no invented objects, and no domain-specific unproved axioms appear. This is a proof-based combinatorics paper whose central claim rests on an explicit structural case analysis.

assumptions (1)

standard math Elementary finite graph theory: paths, cycles, subdivisions, connectivity, and feedback edge sets behave as in standard references.
Used throughout Sections 2 to 8. No deep external theorem is used as a black box; the proof is self-contained apart from standard definitions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Graphs without two vertex-disjoint $S$-cycles." pith.science (2026). https://pith.science/paper/5HWRHLZZ

@misc{pith2026190809065,
  author       = {Pith},
  title        = {Pith review of: Graphs without two vertex-disjoint $S$-cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5HWRHLZZ}},
  note         = {Machine review of arXiv:1908.09065}
}

abstract

Lov\'asz (1965) characterized graphs without two vertex-disjoint cycles, which implies that such graphs have at most three vertices hitting all cycles. In this paper, we ask whether such a small hitting set exists for $S$-cycles, when a graph has no two vertex-disjoint $S$-cycles. For a graph $G$ and a vertex set $S$ of $G$, an $S$-cycle is a cycle containing a vertex of $S$. We provide an example $G$ on $21$ vertices where $G$ has no two vertex-disjoint $S$-cycles, but three vertices are not sufficient to hit all $S$-cycles. On the other hand, we show that four vertices are enough to hit all $S$-cycles whenever a graph has no two vertex-disjoint $S$-cycles.

Figures

Figures reproduced from arXiv: 1908.09065 by the authors.

**Figure 1.** Graphs that appear in the proof. • Let K` 4 denote the graph obtained from K4 by adding a multiple edge to an edge of K4. Let K`` 4 denote the graph obtained from K4 by adding a multiple edge to each of two incident edges of K4. Let K``` 4 denote the graph obtained from K4 by adding two multiple edges to an edge of K4. • Let W` 4 denote the graph obtained from W4 by adding an edge between a vertex of degree 4 and a … view at source ↗

**Figure 2.** A graph G with S “ tx1, x2, y1, y2, z1, z2u where G has no two vertex-disjoint S-cycles, but it has no S-cycle hitting set of size at most 3. If T contains no vertex in tai , bi , ci : 1 ď i ď 4u, then T does not meet the S-cycle a1x1b4b2y2c3c1z1a4a2x2b3b1y1c4c2z2a3a1. So, T contains a vertex in tai , bi , ci : 1 ď i ď 4u, and by symmetry, we may assume that a1 P T. Observe that any S-cycle in G´a1 does not contain … view at source ↗

**Figure 3.** A path P in a rooted graph pG, Sq. Rectangles depict vertices in S. Lemma 4.1. Let pG, Sq be a rooted graph with µpG, Sq ď 1, and let W be a subgraph of G. Let P be a path of W whose all internal vertices have degree 2 in W such that Pmid is non-empty, W ´ V pPmidq contains an S-cycle, and G has no pW, Pmid, W ´ V pPmidqq-path. Let a and b be the gates of P. Then the following are satisfied. (1) ta, bu separates Pmi… view at source ↗

Figures from the paper (6 more)

**Figure 4.** Figure 4: K`` 3 is nice because it has no two vertex-disjoint cycles, but if we subdivide two edges and add an edge uw as in figure, then we have two vertex-disjoint cycles. Proof. Observe that a vertex v of S in G hits all cycles along a certifying path containing v. Let F be t…

**Figure 5.** Figure 5: The K`` 4 -subdivision in Proposition 6.5. one vertex, or C2 contains a W1 -extension X2. In the former case, we have two vertex-disjoint S-cycles. So, we may assume that the latter statement holds. If the both endpoints of X2 are branching vertices of W1 , then it con…

**Figure 6.** Figure 6: The three paths X1, X4, X in Claim 6.6 of Proposition 6.5. The dotted S-cycle along X1, X4, X is disjoint from Q1 Y R2 2 Y R1 2 . • adding a gate of Q1 if V pQ1 midq is non-empty, • adding a vertex w P S on Q2 Y Q3 where distQ2YQ3pw, v3q is minimum, otherwise. Clearly,…

**Figure 7.** Figure 7: The K``` 4 -subdivision in Proposition 6.9. • (Case 2. Q1 mid is non-empty.) By the construction of T, w is a gate of Q1 , and thus H contains no vertex of Q1 mid. We first deal with the case when u ‰ v3. We introduce an auxiliary graph F on the vertex set tR 1 2 , R2 …

**Figure 8.** Figure 8: The W` 4 -subdivision in Proposition 7.2. Proof. Let W be an S-cycle W4-subdivision in G. Let v1, v2, v3, v4, w be the branching vertices of W such that w is the vertex of degree 4, and for each i P t1, 2, 3u, let Qi be the certifying path from vi to vi`1, and Q4 be th…

**Figure 9.** Figure 9: The W˚ 4 -subdivision in Proposition 7.6. and i, j P t1, 2, 3u. If Xi and Rj share an endpoint, then it is easy. Suppose Xi and Rj do not share an endpoint; for example, consider R1 and P 3 . If there is an pR1 , P3 q-path Y in G ´ T, Y and one of the two subpaths from…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Birmel´ e, Ph.D Thesis, Universt´ e Lyon 1 (2003)

work page 2003
[2]

Adrian Bondy, and Bruce A

Etienne Birmel´ e, J. Adrian Bondy, and Bruce A. Reed, The Erd˝ os-P´ osa property for long circuits, Combinatorica 27 (2007), no. 2, 135–145. MR 2321919

work page 2007
[3]

Graph Theory 87 (2018), no

Henning Bruhn, Felix Joos, and Oliver Schaudt, Long cycles through prescribed vertices have the Erd˝ os-P´ osa property, J. Graph Theory 87 (2018), no. 3, 275–284. MR 3755249

work page 2018
[4]

Discrete Math

Marek Cygan, Marcin Pilipczuk, Micha/suppress l Pilipczuk, and Jakub Onufry Wojtaszczyk, Subset feedback vertex set is ﬁxed-parameter tractable , SIAM J. Discrete Math. 27 (2013), no. 1, 290–309. MR 3032920

work page 2013
[5]

Paul Erd˝ os and Louis P´ osa,On the maximal number of disjoint circuits of a graph , Publ. Math. Debrecen 9 (1962), 3–12

work page 1962
[6]

Guy Even, Joseph Naor, and Leonid Zosin, An 8-approximation algorithm for the subset feed- back vertex set problem , SIAM J. Comput. 30 (2000), no. 4, 1231–1252. MR 1786759

work page 2000
[7]

Graph Theory 77 (2014), no

Samuel Fiorini and Audrey Herinckx, A tighter Erd˝ os-P´ osa function for long cycles, J. Graph Theory 77 (2014), no. 2, 111–116. MR 3246170

work page 2014
[8]

1, 91–133

Tony Huynh, Felix Joos, and Paul Wollan,A uniﬁed Erd˝ os-P´ osa theorem for constrained cycles, Combinatorica 39 (2019), no. 1, 91–133. MR 3936194 24

work page 2019

Show all 20 references

[9]

Discrete Math.26 (2012), no

Naonori Kakimura and Ken-ichi Kawarabayashi, Packing directed circuits through prescribed vertices bounded fractionally, SIAM J. Discrete Math.26 (2012), no. 3, 1121–1133. MR 3022130

2012
[10]

Naonori Kakimura, Ken-ichi Kawarabayashi, and D´ aniel Marx, Packing cycles through pre- scribed vertices, J. Combin. Theory Ser. B 101 (2011), no. 5, 378–381. MR 2802885

2011
[11]

1665–1684

Eun Jung Kim and O-joung Kwon, Erd˝ os-P´ osa property of chordless cycles and its applications, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2018, pp. 1665–1684. MR 3775897

2018
[12]

Lapok 16 (1965), 289–299

L´ aszl´ o Lov´ asz,On graphs not containing independent circuits , Mat. Lapok 16 (1965), 289–299. MR 0211902

1965
[13]

Mousset, A

F. Mousset, A. Noever, N. ˇSkori´ c, and F. Weissenberger,A tight Erd˝ os-P´ osa function for long cycles, J. Combin. Theory Ser. B 125 (2017), 21–32. MR 3641798

2017
[14]

Pontecorvi and P

M. Pontecorvi and P. Wollan, Disjoint cycles intersecting a set of vertices , J. Combin. Theory Ser. B 102 (2012), no. 5, 1134–1141. MR 2959394

2012
[15]

Thilikos, Recent techniques and results on the Erd˝ os- P´ osa property, Discrete Appl

Jean-Florent Raymond and Dimitrios M. Thilikos, Recent techniques and results on the Erd˝ os- P´ osa property, Discrete Appl. Math. 231 (2017), 25–43. MR 3695268

2017
[16]

2, 267–296

Bruce Reed, Mangoes and blueberries , Combinatorica 19 (1999), no. 2, 267–296. MR 1723044

1999
[17]

4, 535–554

Bruce Reed, Neil Robertson, Paul Seymour, and Robin Tho mas, Packing directed circuits , Combinatorica 16 (1996), no. 4, 535–554. MR 1433641

1996
[18]

Neil Robertson and P. D. Seymour, Graph minors. V. Excluding a planar graph , J. Combin. Theory Ser. B 41 (1986), no. 1, 92–114. MR 854606

1986
[19]

Graph Theory 12 (1988), no

Carsten Thomassen, On the presence of disjoint subgraphs of a speciﬁed type , J. Graph Theory 12 (1988), no. 1, 101–111. MR 928740

1988
[20]

Voss, Eigenschaften von Graphen, die keine k ` 1 knotenfremde Kreise enthalten , Math

H.-J. Voss, Eigenschaften von Graphen, die keine k ` 1 knotenfremde Kreise enthalten , Math. Nachr. 40 (1969), 19–25. MR 284381 25

1969

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Birmel´ e, Ph.D Thesis, Universt´ e Lyon 1 (2003)

work page 2003

[2] [2]

Adrian Bondy, and Bruce A

Etienne Birmel´ e, J. Adrian Bondy, and Bruce A. Reed, The Erd˝ os-P´ osa property for long circuits, Combinatorica 27 (2007), no. 2, 135–145. MR 2321919

work page 2007

[3] [3]

Graph Theory 87 (2018), no

Henning Bruhn, Felix Joos, and Oliver Schaudt, Long cycles through prescribed vertices have the Erd˝ os-P´ osa property, J. Graph Theory 87 (2018), no. 3, 275–284. MR 3755249

work page 2018

[4] [4]

Discrete Math

Marek Cygan, Marcin Pilipczuk, Micha/suppress l Pilipczuk, and Jakub Onufry Wojtaszczyk, Subset feedback vertex set is ﬁxed-parameter tractable , SIAM J. Discrete Math. 27 (2013), no. 1, 290–309. MR 3032920

work page 2013

[5] [5]

Paul Erd˝ os and Louis P´ osa,On the maximal number of disjoint circuits of a graph , Publ. Math. Debrecen 9 (1962), 3–12

work page 1962

[6] [6]

Guy Even, Joseph Naor, and Leonid Zosin, An 8-approximation algorithm for the subset feed- back vertex set problem , SIAM J. Comput. 30 (2000), no. 4, 1231–1252. MR 1786759

work page 2000

[7] [7]

Graph Theory 77 (2014), no

Samuel Fiorini and Audrey Herinckx, A tighter Erd˝ os-P´ osa function for long cycles, J. Graph Theory 77 (2014), no. 2, 111–116. MR 3246170

work page 2014

[8] [8]

1, 91–133

Tony Huynh, Felix Joos, and Paul Wollan,A uniﬁed Erd˝ os-P´ osa theorem for constrained cycles, Combinatorica 39 (2019), no. 1, 91–133. MR 3936194 24

work page 2019