{"ID":2898512,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.03807","arxiv_id":"2507.03807","title":"A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs","abstract":"For a directed graph $G$, let $\\mathrm{mindeg}(G)$ be the minimum among in-degrees and out-degrees of all vertices of $G$. It is easy to see that $G$ contains a directed cycle of length at least $\\mathrm{mindeg}(G)+1$. In this note, we show that, even if $G$ is $2$-connected, it is NP-hard to check if $G$ contains a cycle of length at least $\\mathrm{mindeg}(G)+3$. This is in contrast with recent algorithmic results of Fomin, Golovach, Sagunov, and Simonov [SODA 2022] for analogous questions in undirected graphs.","short_abstract":"For a directed graph $G$, let $\\mathrm{mindeg}(G)$ be the minimum among in-degrees and out-degrees of all vertices of $G$. It is easy to see that $G$ contains a directed cycle of length at least $\\mathrm{mindeg}(G)+1$. In this note, we show that, even if $G$ is $2$-connected, it is NP-hard to check if $G$ contains a cy...","url_abs":"https://arxiv.org/abs/2507.03807","url_pdf":"https://arxiv.org/pdf/2507.03807v1","authors":"[\"Jadwiga Czyżewska\",\"Marcin Pilipczuk\"]","published":"2025-07-04T20:57:33Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}