Tony Huynh

activity

20122026

most citedA unified Erdős-Pósa theorem for constrained cycles

20 citations · 171 across the 37 of their papers we have counts for

collaborators

Showing cs.DMShow all

6 papers · 1 filter

cs.DM2021

Slack matrices, $k$ -products, and $2$ -level polytopes

Manuel Aprile, Michele Conforti, Yuri Faenza +3

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1-product of matrices $S_{1}$ , $S_2…

cs.DM2019★ 4 cited

Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles

Michele Conforti, Samuel Fiorini, Tony Huynh +1

Let $G$ be an $n$ -node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maxi…

cs.DM2019★ 1 cited

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

Michele Conforti, Samuel Fiorin, Tony Huynh +2

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 lon…

cs.DM2018

Extension Complexity of the Correlation Polytope

Pierre Aboulker, Samuel Fiorini, Tony Huynh +2

We prove that for every $n$ -vertex graph $G$ , the extension complexity of the correlation polytope of $G$ is $2^{O (tw (G) + l o g n)}$ , where $tw (G)$ is the treewid…

cs.DM2017★ 2 cited

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

Pierre Aboulker, Samuel Fiorini, Tony Huynh +3

Let $W_{t}$ denote the wheel on $t + 1$ vertices. We prove that for every integer $t \geq 3$ there is a constant $c = c (t)$ such that for every integer $k \geq 1$ and every graph $G$ , eit…

cs.DM2017★ 4 cited

Extension complexity of stable set polytopes of bipartite graphs

Manuel Aprile, Yuri Faenza, Samuel Fiorini +2

The extension complexity $xc (P)$ of a polytope $P$ is the minimum number of facets of a polytope that affinely projects to $P$ . Let $G$ be a bipartite graph with $n$ verti…