Édouard Bonnet

The planar separator theorem by Lipton and Tarjan [FOCS ’77, SIAM Journal on Applied Mathematics ’79] states that any planar graph with n vertices has a balanced separator of size O(√n) that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan’s theorem to nonplanar graphs, Alon, Seymour, and Thomas [STOC ’90, Journal of the AMS ’90] showed that any minor-free graph admits a balanced separator of size O(√n) that can be found in O(n^3/2) time. The superlinear running time in their separator theorem is a key bottleneck for generalizing algorithmic results from planar to minor-free graphs. Despite extensive research for more than two decades, finding a balanced separator of size O(√n) in (linear) O(n) time for minor-free graphs has remained a major open problem. Known algorithms either give a separator of size much larger than O(√n) or have superlinear running time, or both. In this paper, we answer the open problem affirmatively. Our algorithm is very simple: it runs a vertex-weighted variant of breadth-first search (BFS) a constant number of times on the input graph. Our key technical contribution is a weighting scheme on the vertices to guide the search for a balanced separator, offering a new connection between the size of a balanced separator and the existence of a clique-minor model. We believe that our weighting scheme may be of independent interest.

Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée: De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah.

As the class T4 of graphs of twin-width at most 4 contains every finite subgraph of the infinite grid and every graph obtained by subdividing each edge of an n-vertex graph at least 2 log n times, most NP-hard graph problems, like Max Independent Set, Dominating Set, Hamiltonian Cycle, remain so on T4. However, Min Coloring and k-Coloring are easy on both families because they are 2-colorable and 3-colorable, respectively. We show that Min Coloring is NP-hard on the class T3 of graphs of twin-width at most 3. This is the first hardness result on T3 for a problem that is easy on cographs (twin-width 0), on trees (whose twin-width is at most 2), and on unit circular-arc graphs (whose twin-width is at most 3). We also show that for every k ⩾ 3, k-Coloring is NP-hard on T4. We finally make two observations: (1) there are currently very few problems known to be in P on Td (graphs of twin-width at most d) and NP-hard on Td+1 for some nonnegative integer d, and (2) unlike T4, which contains every graph as an induced minor, the class T3 excludes a fixed planar graph as an induced minor; thus it may be viewed as a special case (or potential counterexample) for conjectures about classes excluding a (planar) induced minor. These observations are accompanied by several open questions.

Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-width is preserved by quasiisometry. Thus, through Cayley graphs, it defines a group invariant. We prove that groups which are abelian, hyperbolic, ordered, solvable, or with polynomial growth, have finite twin-width. Twin-width can be characterised by excluding patterns in the self-action by product of the group elements. Based on this characterisation, we propose a strengthening called uniform twin-width, which is stable under constructions such as group extensions, direct products, and direct limits. The existence of finitely generated groups with infinite twin-width is not immediate. We construct one using a result of Osajda on embeddings of graphs into groups. This implies the existence of a class of finite graphs with unbounded twin-width but containing 2 O(n) • n! graphs on vertex set {1, . . . , n}, settling a question asked in a previous work.

In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid, and on cubic line graphs.