9 papers · 1 filter
Small Independent Sets versus Small Separator in Geometric Intersection Graphs
Malory Marin, Rémi Watrigant
While most classical NP-hard graph problems cannot be solved in time on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomen…
Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +2
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main re…
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time for -vertex graphs given with a witness that th…
An algorithmic weakening of the Erdős-Hajnal conjecture
Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran +1
We study the approximability of the Maximum Independent Set (MIS) problem in -free graphs (that is, graphs which do not admit as an induced subgraph). As one motivation we i…
When Maximum Stable Set can be solved in FPT time
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé +1
Maximum Independent Set (MIS for short) is in general graphs the paradigmatic -hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restr…
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
Édouard Bonnet, Diana-Elena Fălămaş, Rémi Watrigant
Given a hypergraph , the Minimum Connectivity Inference problem asks for a graph on the same vertex set as with the minimum number of edges such that the subgraph induced by…