6 papers
Random Serial Dictatorship is -Envy-Free
Frank Connor, Max Dupré la Tour, Louis-Roy Langevin +4
We analyze the house allocation problem, in which a set of agents must be matched to a set of objects for which they have cardinal utilities. A central mechanism for this problem i…
On the hardness of recognizing graphs of small mim-width and its variants
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
The mim-width of a graph is a powerful structural parameter that, when bounded by a constant, allows several hard problems to be polynomial-time solvable - with a recent meta-theor…
Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
Leaf powers and pairwise compatibility graphs were introduced over twenty years ago as simplified graph models for phylogenetic trees. Despite significant research, several propert…
The Popular Dimension of Matchings
Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye +3
We study popular matchings in three classical settings: the house allocation problem, the marriage problem, and the roommates problem. In the popular matching problem, (a subset of…
Optimizing the CGMS upper bound on Ramsey numbers
Parth Gupta, Ndiame Ndiaye, Sergey Norin +1
In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the diagonal Ramsey numbers since 1935. We shor…
-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye +1
A graph is a -leaf power if there is a tree whose leaves are the vertices of with the property that a pair of leaves and induce an edge in if and o…