Tony Huynh

SODA Conference 2025 Conference Paper

A coarse Erdős-Pósa theorem

• Jungho Ahn
• Jochen Pascal Gollin
• Tony Huynh
• O-joung Kwon

SODA Conference 2020 Conference Paper

The stable set problem in graphs with bounded genus and bounded odd cycle packing number

• Michele Conforti
• Samuel Fiorini
• Tony Huynh
• Gwenaël Joret
• Stefan Weltge

Consider the family of graphs without k node-disjoint odd cycles, where k is a constant. Determining the complexity of the stable set problem for such graphs G is a long-standing problem. We give a polynomial-time algorithm for the case that G can be further embedded in a (possibly nonorientable) surface of bounded genus. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface (Kawarabayashi & Nakamoto, 2007). Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost nonnegative integer circulation of a certain homology class, which turns out to be efficiently solvable in our case.

SODA Conference 2019 Conference Paper

A tight Erdős-Pósa function for planar minors

• Wouter Cames van Batenburg
• Tony Huynh
• Gwenaël Joret
• Jean-Florent Raymond

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f: ℕ → ℝ such that for all k ∊ ℕ and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f ( k ) vertices such that G–X has no H -minor. We prove that this remains true with f ( k ) = ck log k for some constant c = c ( H ). This bound is best possible, up to the value of c, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with f ( k ) = ck log d k for some universal constant d. The proof is constructive and yields a polynomial-time O (log OPT)-approximation algorithm for packing subgraphs containing an H -minor.

I&C Journal 2017 Journal Article

Space proof complexity for random 3-CNFs

• Patrick Bennett
• Ilario Bonacina
• Nicola Galesi
• Tony Huynh
• Mike Molloy
• Paul Wollan

We investigate the space complexity of refuting 3-CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random 3-CNF φ in n variables requires, with high probability, Ω ( n ) distinct monomials to be kept simultaneously in memory. The same construction also proves that every Resolution refutation of φ requires, with high probability, Ω ( n ) clauses each of width Ω ( n ) to be kept at the same time in memory. This gives a Ω ( n 2 ) lower bound for the total space needed in Resolution to refute φ. These results are best possible (up to a constant factor) and answer questions about space complexity of 3-CNFs. The main technical innovation is a variant of Hall's Lemma. We show that in bipartite graphs with bipartition ( L, R ) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW -matchings, provided that L expands in R by a factor of ( 2 − ϵ ), for ϵ < 1 5.