A half-integral Erd\H{o}s-P\'osa theorem for directed odd cycles

DOI10.1137/1.9781611977554.CH118OpenAlexW4316652406MaRDI QIDQ6345733FDOQ6345733

Authors Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie 

Publication date 23 July 2020

Full work available at URL https://doi.org/10.1137/1.9781611977554.ch118

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We prove that there exists a function $f:mathbbNightarrowmathbbR$ such that every directed graph $G$ contains either $k$ directed odd cycles where every vertex of $G$ is contained in at most two of them, or a set of at most $f(k)$ vertices meeting all directed odd cycles. We also give a polynomial-time algorithm for fixed $k$ which outputs one of the two outcomes. Using this algorithmic result, we give a polynomial-time algorithm for fixed $k$ to decide whether such $k$ directed odd cycles exist, or there are no $k$ vertex-disjoint directed odd cycles. This extends the half-integral ErdH{o}s-P'osa theorem for undirected odd cycles by Reed [Combinatorica 1999] to directed graphs.

This page was built for publication: A half-integral Erd\H{o}s-P\'osa theorem for directed odd cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345733)