TY - GEN

T1 - Multi-transversals for triangles and the Tuza's conjecture

AU - Chalermsook, Parinya

AU - Khuller, Samir

AU - Sukprasert, Pattara

AU - Uniyal, Sumedha

N1 - Funding Information:
Part of this work was done while PC and SK were visiting the Simons Institute for the Theory of Computing. It was partially supported by the DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization through NSF grant #CCF-1740425. PC is currently supported by European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 759557) and by Academy of Finland Research Fellows, under grant number 310415. SK is currently supported on research grants by Adobe and Amazon. We also thank the anonymous reviewers for their detailed comments and suggestions.
Publisher Copyright:
Copyright © 2020 by SIAM
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - In this paper, we study a primal and dual relationship about triangles: For any graph G, let ν(G) be the maximum number of edge-disjoint triangles in G, and τ(G) be the minimum subset F of edges such that G \ F is triangle-free. It is easy to see that ν(G) ≤ τ(G) ≤ 3ν(G), and in fact, this rather obvious inequality holds for a much more general primal-dual relation between k-hyper matching and covering in hypergraphs. Tuza conjectured in 1981 that τ(G) ≤ 2ν(G), and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every k ≥ 2, there exist a (multi)-set F ⊆ E(G): |F| ≤ 2kν(G) such that each triangle in G overlaps at least k elements in F. Our result can be seen as a strengthened statement of Krivelevich's result on the fractional version of Tuza's conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in F based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza's conjecture in particular.

AB - In this paper, we study a primal and dual relationship about triangles: For any graph G, let ν(G) be the maximum number of edge-disjoint triangles in G, and τ(G) be the minimum subset F of edges such that G \ F is triangle-free. It is easy to see that ν(G) ≤ τ(G) ≤ 3ν(G), and in fact, this rather obvious inequality holds for a much more general primal-dual relation between k-hyper matching and covering in hypergraphs. Tuza conjectured in 1981 that τ(G) ≤ 2ν(G), and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every k ≥ 2, there exist a (multi)-set F ⊆ E(G): |F| ≤ 2kν(G) such that each triangle in G overlaps at least k elements in F. Our result can be seen as a strengthened statement of Krivelevich's result on the fractional version of Tuza's conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in F based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza's conjecture in particular.

UR - http://www.scopus.com/inward/record.url?scp=85084072757&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084072757&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85084072757

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1955

EP - 1974

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -