THTony Huynh
Tony Huynh
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Tony Huynh has a total of 100 co-authors. Here are the top co-authors by number of shared publications:
- Samuel Fiorini
Universite Libre de Bruxelles
15 shared publications - Gwenaël Joret
Computer Science Department Université libre de Bruxelles Brussels Belgium
12 shared publications - David R. Wood
Monash University, Melbourne, Australia
8 shared publications - Manuel Aprile
Department of Mathematics, University of Padova, 35122 Padua, Italy
5 shared publications - Marco Macchia
Universite Libre de Bruxelles
5 shared publications Matthew Drescher
5 shared publications
Latest Publications
- 12 March 2026
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 76 (3) , 1537-1546
Triangulated Spheres with Holes in Triangulated Surfaces
- 12 March 2026
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 76 (3) , 1537-1546
Triangulated Spheres with Holes in Triangulated Surfaces
- 30 December 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 172, 80-93
Aharoni's rainbow cycle conjecture holds up to an additive constant
- 30 December 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 172, 80-93
Aharoni's rainbow cycle conjecture holds up to an additive constant
- Open Access
- 7 December 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 33 (3) , 351-376
Product structure of graph classes with bounded treewidth
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$ , for every graph $G \in \mathcal{G}$ there is a graph $H$ with $\textrm{tw}(H) \leqslant c$ such that $G$ is isomorphic to a subgraph of $H \boxtimes K_{f(\textrm{tw}(G))}$ . We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth $3$ ; the class of $K_{s,t}$ -minor-free graphs has underlying treewidth $s$ (for $t \geqslant \max \{s,3\}$ ); and the class of $K_t$ -minor-free graphs has underlying treewidth $t-2$ . In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.- 7 December 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 33 (3) , 351-376
Open AccessProduct structure of graph classes with bounded treewidth
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$ , for every graph $G \in \mathcal{G}$ there is a graph $H$ with $\textrm{tw}(H) \leqslant c$ such that $G$ is isomorphic to a subgraph of $H \boxtimes K_{f(\textrm{tw}(G))}$ . We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth $3$ ; the class of $K_{s,t}$ -minor-free graphs has underlying treewidth $s$ (for $t \geqslant \max \{s,3\}$ ); and the class of $K_t$ -minor-free graphs has underlying treewidth $t-2$ . In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star. - Open Access
- 19 May 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 337, 149-160
A -approximation algorithm for feedback vertex set in tournaments via Sherali–Adams- 19 May 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 337, 149-160
Open AccessA -approximation algorithm for feedback vertex set in tournaments via Sherali–Adams - 23 August 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 354, 199-213
Slack matrices, -products, and 2-level polytopes- 23 August 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 354, 199-213
Slack matrices, -products, and 2-level polytopes- Open Access
- 1 February 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 192 (1-2) , 51-55
Correction to: Idealness of k-wise intersecting families
A Correction to this paper has been published: 10.1007/s10107-020-01587-x
- 1 February 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 192 (1-2) , 51-55
Open AccessCorrection to: Idealness of k-wise intersecting families
A Correction to this paper has been published: 10.1007/s10107-020-01587-x
- 7 January 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1069-1091
A tight approximation algorithm for the cluster vertex deletion problem
- 7 January 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1069-1091
A tight approximation algorithm for the cluster vertex deletion problem
- Open Access
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
Let $G$ be a connected $n$-vertex graph in a proper minor-closed class $\mathcal G$. We prove that the extension complexity of the spanning tree polytope of $G$ is $O(n^{3/2})$. This improves on the $O(n^2)$ bounds following from the work of Wong (1980) and Martin (1991). It also extends a result of Fiorini, Huynh, Joret, and Pashkovich (2017), who obtained a $O(n^{3/2})$ bound for graphs embedded in a fixed surface. Our proof works more generally for all graph classes admitting strongly sublinear balanced separators: We prove that for every constant $\beta$ with $0<\beta<1$, if $\mathcal G$ is a graph class closed under induced subgraphs such that all $n$-vertex graphs in $\mathcal G$ have balanced separators of size $O(n^\beta)$, then the extension complexity of the spanning tree polytope of every connected $n$-vertex graph in $\mathcal{G}$ is $O(n^{1+\beta})$. We in fact give two proofs of this result, one is a direct construction of the extended formulation, the other is via communication protocols. Using the latter approach we also give a short proof of the $O(n)$ bound for planar graphs due to Williams (2002).Open AccessSmaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
Let $G$ be a connected $n$-vertex graph in a proper minor-closed class $\mathcal G$. We prove that the extension complexity of the spanning tree polytope of $G$ is $O(n^{3/2})$. This improves on the $O(n^2)$ bounds following from the work of Wong (1980) and Martin (1991). It also extends a result of Fiorini, Huynh, Joret, and Pashkovich (2017), who obtained a $O(n^{3/2})$ bound for graphs embedded in a fixed surface. Our proof works more generally for all graph classes admitting strongly sublinear balanced separators: We prove that for every constant $\beta$ with $0<\beta<1$, if $\mathcal G$ is a graph class closed under induced subgraphs such that all $n$-vertex graphs in $\mathcal G$ have balanced separators of size $O(n^\beta)$, then the extension complexity of the spanning tree polytope of every connected $n$-vertex graph in $\mathcal{G}$ is $O(n^{1+\beta})$. We in fact give two proofs of this result, one is a direct construction of the extended formulation, the other is via communication protocols. Using the latter approach we also give a short proof of the $O(n)$ bound for planar graphs due to Williams (2002). - Open Access
Subgraph densities in a surface
Given a fixed graph $H$ that embeds in a surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph $G$ that embeds in $\Sigma$? We show that the answer is $\Theta(n^{f(H)})$, where $f(H)$ is a graph invariant called the `flap-number' of $H$, which is independent of $\Sigma$. This simultaneously answers two open problems posed by Eppstein (1993). When $H$ is a complete graph we give more precise answers.Open AccessSubgraph densities in a surface
Given a fixed graph $H$ that embeds in a surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph $G$ that embeds in $\Sigma$? We show that the answer is $\Theta(n^{f(H)})$, where $f(H)$ is a graph invariant called the `flap-number' of $H$, which is independent of $\Sigma$. This simultaneously answers two open problems posed by Eppstein (1993). When $H$ is a complete graph we give more precise answers.