10 papers
1-Extendability of independent sets
Pierre Bergé, Anthony Busson, Carl Feghali +1
In the 70s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in th…
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…
Twin-width II: small classes
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
The twin-width of a graph is the minimum integer such that has a -contraction sequence, that is, a sequence of iterated vertex identifications for which t…
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…