Édouard Bonnet

According to our database, Édouard Bonnet authored at least 94 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Neighbourhood complexity of graphs of bounded twin-width.

Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, Aline Parreau

Eur. J. Comb., January, 2024

Graphs without a 3-connected subgraph are 4-colorable.

Édouard Bonnet, Carl Feghali, Stéphan Thomassé, Nicolas Trotignon

CoRR, 2024

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes.

Edouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Factoring Pattern-Free Permutations into Separable ones.

Edouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Maximum Matchings in Geometric Intersection Graphs.

Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer

Discret. Comput. Geom., October, 2023

Twin-width can be exponential in treewidth.

Édouard Bonnet, Hugues Déprés

J. Comb. Theory, Ser. B, July, 2023

Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor.

Édouard Bonnet, Jedrzej Hodor, Tuukka Korhonen, Tomás Masarík

CoRR, 2023

Tight bounds on adjacency labels for monotone graph classes.

Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii

CoRR, 2023

Small But Unwieldy.

Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii

CoRR, 2023

Maximum Independent Set when excluding an induced minor: K₁ + tK₂ and tC₃ ⊎ C₄.

Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek

CoRR, 2023

Treewidth is NP-Complete on Cubic Graphs (and related results).

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý

CoRR, 2023

Grundy Coloring and Friends, Half-Graphs, Bicliques.

Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora

Algorithmica, 2023

Cutting Barnette Graphs Perfectly is Hard.

Édouard Bonnet, Dibyayan Chakraborty, Julien Duron

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication.

Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width.

Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth.

Marthe Bonamy, Edouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

PACE Solver Description: RedAlert - Heuristic Track.

Édouard Bonnet, Julien Duron

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Stretch-Width.

Édouard Bonnet, Julien Duron

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Treewidth Is NP-Complete on Cubic Graphs.

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄.

Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time <i>n</i>^4/3.

Édouard Bonnet

ACM Trans. Algorithms, 2022

Twin-width I: Tractable FO Model Checking.

Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

J. ACM, 2022

Twin-width VII: groups.

Édouard Bonnet, Colin Geniet, Romain Tessera, Stéphan Thomassé

CoRR, 2022

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond).

Édouard Bonnet, O-joung Kwon, David R. Wood

CoRR, 2022

Twin-width and Polynomial Kernels.

Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant

Algorithmica, 2022

Twin-width IV: ordered graphs and matrices.

Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Twin-width VI: the lens of contraction sequences.

Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth.

Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Twin-Width VIII: Delineation and Win-Wins.

Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

Deciding Twin-Width at Most 4 Is NP-Complete.

Pierre Bergé, Édouard Bonnet, Hugues Déprés

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs.

Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, Stéphan Thomassé

J. ACM, 2021

Parameterized Intractability of Even Set and Shortest Vector Problem.

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

J. ACM, 2021

Twin-width and permutations.

Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, Stéphan Thomassé

CoRR, 2021

4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3.

Édouard Bonnet

CoRR, 2021

The complexity of mixed-connectivity.

Édouard Bonnet, Sergio Cabello

Ann. Oper. Res., 2021

Metric Dimension Parameterized By Treewidth.

Édouard Bonnet, Nidhi Purohit

Algorithmica, 2021

The Inverse Voronoi Problem in Graphs II: Trees.

Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés

Algorithmica, 2021

Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio.

Édouard Bonnet

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Twin-width II: small classes.

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring.

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time n^{4/3}.

Édouard Bonnet

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Parameterized Hardness of Art Gallery Problems.

Édouard Bonnet, Tillmann Miltzow

ACM Trans. Algorithms, 2020

Designing RNA Secondary Structures Is Hard.

Édouard Bonnet, Pawel Rzazewski, Florian Sikora

J. Comput. Biol., 2020

Twin-width III: Max Independent Set and Coloring.

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

CoRR, 2020

The Inverse Voronoi Problem in Graphs I: Hardness.

Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés

Algorithmica, 2020

Parameterized Complexity of Independent Set in H-Free Graphs.

Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant

Algorithmica, 2020

Grundy Coloring & Friends, Half-Graphs, Bicliques.

Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth.

Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-joung Kwon

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Maximum Clique in Disk-Like Intersection Graphs.

Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

An Algorithmic Weakening of the Erdős-Hajnal Conjecture.

Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

On the parameterized complexity of red-blue points separation.

Edouard Bonnet, Panos Giannopoulos, Michael Lampis

J. Comput. Geom., 2019

Orthogonal Terrain Guarding is NP-complete.

Édouard Bonnet, Panos Giannopoulos

J. Comput. Geom., 2019

Optimality Program in Segment and String Graphs.

Édouard Bonnet, Pawel Rzazewski

Algorithmica, 2019

Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms.

Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx

Algorithmica, 2019

Constraint Generation Algorithm for the Minimum Connectivity Inference Problem.

Édouard Bonnet, Diana-Elena Falamas, Rémi Watrigant

Proceedings of the Analysis of Experimental Algorithms - Special Event, 2019

When Maximum Stable Set Can Be Solved in FPT Time.

Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

Parameterized Streaming Algorithms for Min-Ones d-SAT.

Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP.

Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Lukasz Kowalik

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Fine-grained complexity of coloring unit disks and balls.

Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski

J. Comput. Geom., 2018

Time-approximation trade-offs for inapproximable problems.

Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos

J. Comput. Syst. Sci., 2018

Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs.

Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis

Discret. Optim., 2018

Complexity of Grundy coloring and its variants.

Édouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora

Discret. Appl. Math., 2018

The inverse Voronoi problem in graphs.

Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés

CoRR, 2018

Complexity of Token Swapping and Its Variants.

Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski

Algorithmica, 2018

Sparsification and subexponential approximation.

Édouard Bonnet, Vangelis Th. Paschos

Acta Informatica, 2018

The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration.

Édouard Bonnet, Florian Sikora

Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

EPTAS for Max Clique on Disks and Unit Balls.

Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs.

Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

On the complexity of various parameterizations of common induced subgraph isomorphism.

Faisal N. Abu-Khzam, Édouard Bonnet, Florian Sikora

Theor. Comput. Sci., 2017

Dual parameterization and parameterized approximability of subset graph problems.

Édouard Bonnet, Vangelis Th. Paschos

RAIRO Oper. Res., 2017

The Graph Motif problem parameterized by the structure of the input graph.

Édouard Bonnet, Florian Sikora

Discret. Appl. Math., 2017

The Parameterized Complexity of Positional Games.

Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

An Approximation Algorithm for the Art Gallery Problem.

Édouard Bonnet, Tillmann Miltzow

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

On the complexity of connection games.

Édouard Bonnet, Florian Jamain, Abdallah Saffidine

Theor. Comput. Sci., 2016

Parameterized exact and approximation algorithms for maximum <i>k</i>-set cover and related satisfiability problems.

Édouard Bonnet, Vangelis Th. Paschos, Florian Sikora

RAIRO Theor. Informatics Appl., 2016

A Note on Edge Isoperimetric Numbers and Regular Graphs.

Édouard Bonnet, Florian Sikora

Int. J. Found. Comput. Sci., 2016

The Parameterized Hardness of the Art Gallery Problem.

Édouard Bonnet, Tillmann Miltzow

CoRR, 2016

Flip Distance to a Non-crossing Perfect Matching.

Édouard Bonnet, Tillmann Miltzow

CoRR, 2016

Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property.

Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs.

Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

The Complexity of Playing Durak.

Édouard Bonnet

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

Fixed-Parameter Approximability of Boolean MinCSPs.

Édouard Bonnet, László Egri, Dániel Marx

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

The parameterized complexity of Graph Motif relatively to the structure of the input graph.

Edouard Bonnet, Florian Sikora

CoRR, 2015

Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization.

Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

Algorithmica, 2015

On Subexponential and FPT-Time Inapproximability.

Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos

Algorithmica, 2015

Draws, Zugzwangs, and PSPACE-Completeness in the Slither Connection Game.

Edouard Bonnet, Florian Jamain, Abdallah Saffidine

Proceedings of the Advances in Computer Games - 14th International Conference, 2015

2014

Positive and Negative Results in Approximation and Parameterized Complexity. (Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée).

Édouard Bonnet

PhD thesis, 2014

Parameterized (in)approximability of subset problems.

Edouard Bonnet, Vangelis Th. Paschos

Oper. Res. Lett., 2014

On the approximation of maximum $k$-vertex cover in bipartite graphs.

Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis

CoRR, 2014

On the Complexity of General Game Playing.

Édouard Bonnet, Abdallah Saffidine

Proceedings of the Computer Games - Third Workshop on Computer Games, 2014

2013

Multiparameterizations for max $k$-set cover and related satisfiability problems.

Edouard Bonnet, Vangelis Th. Paschos, Florian Sikora

CoRR, 2013

Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization.

Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

On the Complexity of Trick-Taking Card Games.

Edouard Bonnet, Florian Jamain, Abdallah Saffidine

Proceedings of the IJCAI 2013, 2013

Havannah and TwixT are PSPACE-complete.

Edouard Bonnet, Florian Jamain, Abdallah Saffidine

Proceedings of the Computers and Games - 8th International Conference, 2013