research
∙
03/22/2023
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
We consider the feedback vertex set problem in undirected graphs (FVS). ...
share
research
∙
06/24/2021
Slack matrices, k-products, and 2-level polytopes
In this paper, we study algorithmic questions concerning products of mat...
research
∙
06/22/2021
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 𝒢. We...
research
∙
06/10/2021
Integer programs with bounded subdeterminants and two nonzeros per row
We give a strongly polynomial-time algorithm for integer linear programs...
research
∙
09/23/2020
A simple (2+ε)-approximation algorithm for Split Vertex Deletion
A split graph is a graph whose vertex set can be partitioned into a cliq...
research
∙
08/20/2020
A simple 7/3-approximation algorithm for feedback vertex set in tournaments
We show that performing just one round of the Sherali-Adams hierarchy gi...
research
∙
07/16/2020
A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
We give the first 2-approximation algorithm for the cluster vertex delet...
research
∙
02/06/2020
Recognizing Cartesian products of matrices and polytopes
The 1-product of matrices S_1 ∈R^m_1 × n_1 and S_2 ∈R^m_2 × n_2 is the m...
research
∙
11/27/2019
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Let G be an n-node graph without two disjoint odd cycles. The algorithm ...
research
∙
09/18/2019
Regular matroids have polynomial extension complexity
We prove that the extension complexity of the independence polytope of e...
research
∙
04/05/2019
Unavoidable minors for graphs with large ℓ_p-dimension
A metric graph is a pair (G,d), where G is a graph and d:E(G) →R_≥0 is a...
research
∙
08/30/2018
Improved approximation algorithms for hitting 3-vertex paths
We study the problem of deleting a minimum cost set of vertices from a g...
research
∙
06/15/2018
Bounds on the number of 2-level polytopes, cones and configurations
We prove an upper bound of the form 2^O(d^2 polylog d) on the number of ...
research
∙
06/01/2018
Extension Complexity of the Correlation Polytope
We prove that for every n-vertex graph G, the extension complexity of th...
research
∙
11/03/2017
Strengthening Convex Relaxations of 0/1-Sets Using Boolean Formulas
In convex integer programming, various procedures have been developed to...
research
∙
10/17/2017