Packing and covering directed triangles asymptotically (Q2065998)

A well-known conjecture by Tuza states that the minimum number of edges that have to be removed to make a graph triangle-free is at most two times the size of the largest set of pairwise edge-disjoint triangles, see [\textit{Z. Tuza}, Graphs Comb. 6, No. 4, 373--380 (1990; Zbl 0724.05059)]. The conjecture is known to be true for directed multi-graphs and was proven in [\textit{J. McDonald} et al., Graphs Comb. 36, No. 4, 1059--1063 (2020; Zbl 1442.05077)], where it is conjectured that the constant \(2\) can be replaced by \(1.5\). This article proves that the constant \(2\) can be replaced by \(1.8 + o(n^2)\), where \(n\) is the number of vertices of the input graph. The authors use fractional triangle packings and covers to prove their results. By linear programming duality, the fractional packing and covering numbers are equal. Then a fractional triangle cover is used to construct a set of edges meeting all directed triangles. The article concludes with two constructions of directed dense graphs which asymptotically achieve the bound of \(1.5\) conjectured in [\textit{J. McDonald} et al., Graphs Comb. 36, No. 4, 1059--1063 (2020; Zbl 1442.05077)].