Multi-transversals for Triangles and the Tuza’s Conjecture
Published in Symposium on Discrete Algorithms (SODA), 2020
Recommended citation: Chalermsook, Parinya, Samir Khuller, Pattara Sukprasert, and Sumedha Uniyal. "Multi-transversals for Triangles and the Tuza`s Conjecture." In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1955-1974. Society for Industrial and Applied Mathematics, 2020. https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.121
Tuza conjectured that the ratio between max triangle packing and min triangle covering is bounded by two. We prove the multi-tranversals version of the conjecture.