
Slack matrices, kproducts, and 2level polytopes
In this paper, we study algorithmic questions concerning products of mat...
read it

Smaller extended formulations for spanning tree polytopes in minorclosed classes and beyond
Let G be a connected nvertex graph in a proper minorclosed class 𝒢. We...
read it

On the ErdősPósa property for long holes in C_4free graphs
We prove that there exists a function f(k)=𝒪(k^2 log k) such that for ev...
read it

A simple (2+ε)approximation algorithm for Split Vertex Deletion
A split graph is a graph whose vertex set can be partitioned into a cliq...
read it

A simple 7/3approximation algorithm for feedback vertex set in tournaments
We show that performing just one round of the SheraliAdams hierarchy gi...
read it

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
We give the first 2approximation algorithm for the cluster vertex delet...
read it

Subgraph densities in a surface
Given a fixed graph H that embeds in a surface Σ, what is the maximum nu...
read it

Notes on Tree and Pathchromatic Number
Treechromatic number is a chromatic version of treewidth, where the cos...
read it

Recognizing Cartesian products of matrices and polytopes
The 1product of matrices S_1 ∈R^m_1 × n_1 and S_2 ∈R^m_2 × n_2 is the m...
read it

Excluding a ladder
Which graph classes C exclude a fixed ladder as a minor? We show that th...
read it

Notes on Graph Product Structure Theory
It was recently proved that every planar graph is a subgraph of the stro...
read it

Idealness of kwise intersecting families
A clutter is kwise intersecting if every k members have a common elemen...
read it

Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Let G be an nnode graph without two disjoint odd cycles. The algorithm ...
read it

The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Consider the family of graphs without k nodedisjoint odd cycles, where ...
read it

Unavoidable minors for graphs with large ℓ_pdimension
A metric graph is a pair (G,d), where G is a graph and d:E(G) →R_≥0 is a...
read it

Flip distances between graph orientations
Flip graphs are a ubiquitous class of graphs, which encode relations ind...
read it

The biclique covering number of grids
We determine the exact value of the biclique covering number for all gri...
read it

A tight ErdősPósa function for planar minors
Let H be a planar graph. By a classical result of Robertson and Seymour,...
read it

Short rainbow cycles in sparse graphs
Let G be a simple nvertex graph and c be a colouring of E(G) with n col...
read it

Extension Complexity of the Correlation Polytope
We prove that for every nvertex graph G, the extension complexity of th...
read it

Seymour's conjecture on 2connected graphs of large pathwidth
We prove the conjecture of Seymour (1993) that for every apexforest H_1...
read it

Strengthening Convex Relaxations of 0/1Sets Using Boolean Formulas
In convex integer programming, various procedures have been developed to...
read it

A tight ErdősPósa function for wheel minors
Let W_t denote the wheel on t+1 vertices. We prove that for every intege...
read it
Tony Huynh
is this you? claim profile