PACKING AND COVERING A GIVEN DIRECTED GRAPH IN A DIRECTED GRAPH

For every fixed k \geq 4, it is proved that if an n -vertex directed graph has at most t pairwise arc -disjoint directed k -cycles, then there exists a set of at most 23 kt + o(n2) arcs that meets all directed k -cycles and that the set of k -cycles admits a fractional cover of value at most 3 kt. It is also proved that the ratio 2 2 3 k cannot be improved to a constant smaller than k2 . For k = 5 the constant 2k/3 is improved to 25/8 and for k = 3 it was recently shown by Cooper et al. [European J. Combin., 101 (2022), 103462] that the constant can be taken to be 9/5. The result implies a deterministic polynomial time 32 k -approximation algorithm for the directed k -cycle cover problem, improving upon a previous (k -1) -approximation algorithm of Kortsarz, Langberg, and Nutov, [SIAM J. Discrete Math., 24 (2010), pp. 255--269]. More generally, for every directed graph H we introduce a graph parameter f (H) for which it is proved that if an n -vertex directed graph has at most t pairwise arc -disjoint H -copies, then there exists a set of at most f(H)t + o(n2) arcs that meets all H -copies and that the set of H -copies admits a fractional cover of value at most f(H)t. It is shown that for almost all H it holds that f (H) \approx IE(H)I/2 and that for every k -vertex tournament H it holds that f (H) \leq [k2/4].