Hitting Cycles through Prescribed Vertices or Edges
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 988-999
DOI: 10.1137/24m1716604 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 07.07.2026. Verfasst von Nathan Bowler und 4 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Gefördert von: Alexander von Humboldt-Stiftung, Cusanuswerk - Bischofliche Studienforderung, Studienstiftung des Deutschen Volkes.
Abstract (Originalsprache)
We prove that for every set [Formula: see text] of vertices of a directed graph [Formula: see text], the maximum number of vertices in [Formula: see text] contained in a collection of vertex-disjoint cycles in [Formula: see text] is at least the minimum size of a set of vertices that hits all cycles containing a vertex of [Formula: see text]. As a consequence, the directed tree-width of a directed graph is linearly bounded in its cycle-width, which improves the previously known quadratic upper bound. We further show that the corresponding statement in bidirected graphs is true and that its edge-variant holds in both undirected and directed graphs, but fails in bidirected graphs. The vertex-version in undirected graphs remains an open problem.
Förderung
- Alexander von Humboldt-Stiftung
- Cusanuswerk - Bischofliche Studienforderung
- Studienstiftung des Deutschen Volkes
Zitieren
APA
Bowler, N., Ghorbani, E., Gut, F., Jacobs, R. W., & Reich, F. (2026). Hitting Cycles through Prescribed Vertices or Edges. SIAM Journal on Discrete Mathematics, 40(3), 988-999. https://doi.org/10.1137/24m1716604
Vancouver
Bowler N, Ghorbani E, Gut F, Jacobs RW, Reich F. Hitting Cycles through Prescribed Vertices or Edges. SIAM Journal on Discrete Mathematics. 2026;40(3):988-999. doi:10.1137/24m1716604
BibTeX
@article{Bowler2026,
author = {Bowler, Nathan and Ghorbani, Ebrahim and Gut, Florian and Jacobs, Raphael W. and Reich, Florian},
title = {Hitting Cycles through Prescribed Vertices or Edges},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {988--999},
doi = {10.1137/24m1716604}
}
EUVIMED