default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDÉdouard Bonnet
Edouard Bonnet
Person information
- affiliation: ENS de Lyon, France
- affiliation: Paris Dauphine University, Paris, France
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2024
[b2]Édouard Bonnet:
Twin-Width and Contraction Sequences. École normale supérieure de Lyon, France, 2024- 2014
- [b1]Édouard Bonnet:
Positive and Negative Results in Approximation and Parameterized Complexity. (Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée). Paris Dauphine University, France, 2014
Journal Articles
- 2025
- [j45]Édouard Bonnet, Carl Feghali, Tung Nguyen, Alex Scott, Paul D. Seymour, Stéphan Thomassé, Nicolas Trotignon:
Graphs without a 3-Connected Subgraph are 4-Colourable. Electron. J. Comb. 32(1) (2025) - [j44]Hans L. Bodlaender
, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý:
Treewidth is NP-Complete on Cubic Graphs. Electron. J. Comb. 32(3) (2025) - [j43]Édouard Bonnet:
Sparse induced subgraphs of large treewidth. J. Comb. Theory B 173: 184-203 (2025) - 2024
- [j42]Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, Aline Parreau:
Neighbourhood complexity of graphs of bounded twin-width. Eur. J. Comb. 115: 103772 (2024) - [j41]Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk:
Twin-Width IV: Ordered Graphs and Matrices. J. ACM 71(3): 21 (2024) - [j40]Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek:
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. J. Comb. Theory B 167: 215-249 (2024) - [j39]Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, Stéphan Thomassé:
Twin-width and permutations. Log. Methods Comput. Sci. 20(3) (2024) - [j38]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii:
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes. SIAM J. Comput. 53(5): 1578-1601 (2024) - [j37]Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring. SIAM J. Comput. 53(5): 1602-1640 (2024) - [j36]Édouard Bonnet, Dibyayan Chakraborty, Julien Duron:
Cutting Barnette graphs perfectly is hard. Theor. Comput. Sci. 1010: 114701 (2024) - 2023
- [j35]Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora:
Grundy Coloring and Friends, Half-Graphs, Bicliques. Algorithmica 85(1): 1-28 (2023) - [j34]Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer:
Maximum Matchings in Geometric Intersection Graphs. Discret. Comput. Geom. 70(3): 550-579 (2023) - [j33]Édouard Bonnet, Hugues Déprés:
Twin-width can be exponential in treewidth. J. Comb. Theory B 161: 1-14 (2023) - 2022
- [j32]Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant:
Twin-width and Polynomial Kernels. Algorithmica 84(11): 3300-3337 (2022) - [j31]Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width II: small classes. Comb. Theory 2(2) (2022) - [j30]Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width I: Tractable FO Model Checking. J. ACM 69(1): 3:1-3:46 (2022) - [j29]Édouard Bonnet:
4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n4/3. ACM Trans. Algorithms 18(2): 11:1-11:14 (2022) - 2021
- [j28]Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés:
The Inverse Voronoi Problem in Graphs II: Trees. Algorithmica 83(5): 1165-1200 (2021) - [j27]Édouard Bonnet, Nidhi Purohit:
Metric Dimension Parameterized By Treewidth. Algorithmica 83(8): 2606-2633 (2021) - [j26]Édouard Bonnet, Sergio Cabello:
The complexity of mixed-connectivity. Ann. Oper. Res. 307(1): 25-35 (2021) - [j25]Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, Stéphan Thomassé:
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs. J. ACM 68(2): 9:1-9:38 (2021) - [j24]Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
Parameterized Intractability of Even Set and Shortest Vector Problem. J. ACM 68(3): 16:1-16:40 (2021) - 2020
- [j23]Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant:
Parameterized Complexity of Independent Set in H-Free Graphs. Algorithmica 82(8): 2360-2394 (2020) - [j22]Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés:
The Inverse Voronoi Problem in Graphs I: Hardness. Algorithmica 82(10): 3018-3040 (2020) - [j21]Édouard Bonnet, Pawel Rzazewski, Florian Sikora:
Designing RNA Secondary Structures Is Hard. J. Comput. Biol. 27(3): 302-316 (2020) - [j20]Édouard Bonnet, Tillmann Miltzow:
Parameterized Hardness of Art Gallery Problems. ACM Trans. Algorithms 16(4): 42:1-42:23 (2020) - 2019
- [j19]Édouard Bonnet, Pawel Rzazewski:
Optimality Program in Segment and String Graphs. Algorithmica 81(7): 3047-3073 (2019) - [j18]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms. Algorithmica 81(10): 3890-3935 (2019) - [j17]Edouard Bonnet, Panos Giannopoulos, Michael Lampis:
On the parameterized complexity of red-blue points separation. J. Comput. Geom. 10(1): 181-206 (2019) - [j16]Édouard Bonnet, Panos Giannopoulos:
Orthogonal Terrain Guarding is NP-complete. J. Comput. Geom. 10(2): 21-44 (2019) - 2018
- [j15]Édouard Bonnet, Vangelis Th. Paschos:
Sparsification and subexponential approximation. Acta Informatica 55(1): 1-15 (2018) - [j14]Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski:
Complexity of Token Swapping and Its Variants. Algorithmica 80(9): 2656-2682 (2018) - [j13]Édouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora:
Complexity of Grundy coloring and its variants. Discret. Appl. Math. 243: 99-114 (2018) - [j12]Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis:
Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs. Discret. Optim. 27: 26-56 (2018) - [j11]Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos:
Time-approximation trade-offs for inapproximable problems. J. Comput. Syst. Sci. 92: 171-180 (2018) - [j10]Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski:
Fine-grained complexity of coloring unit disks and balls. J. Comput. Geom. 9(2): 47-80 (2018) - 2017
- [j9]Édouard Bonnet, Florian Sikora:
The Graph Motif problem parameterized by the structure of the input graph. Discret. Appl. Math. 231: 78-94 (2017) - [j8]Édouard Bonnet, Vangelis Th. Paschos:
Dual parameterization and parameterized approximability of subset graph problems. RAIRO Oper. Res. 51(1): 261-266 (2017) - [j7]Faisal N. Abu-Khzam, Édouard Bonnet, Florian Sikora:
On the complexity of various parameterizations of common induced subgraph isomorphism. Theor. Comput. Sci. 697: 69-78 (2017) - 2016
- [j6]Édouard Bonnet, Florian Sikora:
A Note on Edge Isoperimetric Numbers and Regular Graphs. Int. J. Found. Comput. Sci. 27(6): 771-774 (2016) - [j5]Édouard Bonnet, Vangelis Th. Paschos, Florian Sikora:
Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems. RAIRO Theor. Informatics Appl. 50(3): 227-240 (2016) - [j4]Édouard Bonnet, Florian Jamain, Abdallah Saffidine:
On the complexity of connection games. Theor. Comput. Sci. 644: 2-28 (2016) - 2015
- [j3]Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos:
On Subexponential and FPT-Time Inapproximability. Algorithmica 71(3): 541-565 (2015) - [j2]Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire:
Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization. Algorithmica 71(3): 566-580 (2015) - 2014
- [j1]Edouard Bonnet, Vangelis Th. Paschos:
Parameterized (in)approximability of subset problems. Oper. Res. Lett. 42(3): 222-225 (2014)
Conference and Workshop Papers
- 2025
- [c69]Édouard Bonnet, Kristóf Huszár:
On the Twin-Width of Smooth Manifolds. SoCG 2025: 23:1-23:16 - [c68]Édouard Bonnet, Pawel Rzazewski:
An 11/6-Approximation Algorithm for Vertex Cover on String Graphs. SoCG 2025: 24:1-24:15 - [c67]Pierre Aboulker, Édouard Bonnet, Timothé Picavet, Nicolas Trotignon:
Induced Disjoint Paths Without an Induced Minor. ICALP 2025: 4:1-4:14 - [c66]Benjamin Bergougnoux, Édouard Bonnet, Julien Duron:
Mim-Width Is paraNP-Complete. ICALP 2025: 25:1-25:17 - [c65]Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis, Colin Geniet, Nikolas Mählmann, Michal Pilipczuk, Wojciech Przybyszewski, Szymon Torunczyk:
Separability Properties of Monadically Dependent Graph Classes. ICALP 2025: 147:1-147:19 - [c64]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev:
Adjacency Labeling Schemes for Small Classes. ITCS 2025: 21:1-21:22 - [c63]Manuel Bodirsky, Édouard Bonnet, Zaneta Semanisinová:
Temporal Valued Constraint Satisfaction Problems. MFCS 2025: 24:1-24:19 - [c62]Édouard Bonnet:
Treewidth Inapproximability and Tight ETH Lower Bound. STOC 2025: 2130-2135 - 2024
- [c61]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii:
Tight Bounds on Adjacency Labels for Monotone Graph Classes. ICALP 2024: 31:1-31:20 - [c60]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev:
Symmetric-Difference (Degeneracy) and Signed Tree Models. MFCS 2024: 32:1-32:16 - [c59]Edouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé:
Factoring Pattern-Free Permutations into Separable ones. SODA 2024: 752-779 - [c58]Edouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii:
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes. SODA 2024: 1147-1165 - 2023
- [c57]Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek:
Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄. ESA 2023: 23:1-23:15 - [c56]Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý:
Treewidth Is NP-Complete on Cubic Graphs. IPEC 2023: 7:1-7:13 - [c55]Édouard Bonnet, Julien Duron:
Stretch-Width. IPEC 2023: 8:1-8:15 - [c54]Édouard Bonnet, Julien Duron:
PACE Solver Description: RedAlert - Heuristic Track. IPEC 2023: 40:1-40:5 - [c53]Marthe Bonamy, Edouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek:
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. SODA 2023: 3006-3028 - [c52]Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant:
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width. STACS 2023: 10:1-10:15 - [c51]Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé:
Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication. STACS 2023: 15:1-15:16 - [c50]Édouard Bonnet, Dibyayan Chakraborty, Julien Duron:
Cutting Barnette Graphs Perfectly is Hard. WG 2023: 116-129 - 2022
- [c49]Pierre Bergé, Édouard Bonnet, Hugues Déprés:
Deciding Twin-Width at Most 4 Is NP-Complete. ICALP 2022: 18:1-18:20 - [c48]Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé:
Twin-Width VIII: Delineation and Win-Wins. IPEC 2022: 9:1-9:18 - [c47]Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk:
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. LICS 2022: 54:1-54:13 - [c46]Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé:
Twin-width VI: the lens of contraction sequences. SODA 2022: 1036-1056 - [c45]Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk:
Twin-width IV: ordered graphs and matrices. STOC 2022: 924-937 - 2021
- [c44]Édouard Bonnet:
4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time n^{4/3}. ICALP 2021: 34:1-34:15 - [c43]Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. ICALP 2021: 35:1-35:20 - [c42]Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant:
Twin-Width and Polynomial Kernels. IPEC 2021: 10:1-10:16 - [c41]Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width II: small classes. SODA 2021: 1977-1996 - [c40]Édouard Bonnet:
Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio. STACS 2021: 17:1-17:13 - 2020
- [c39]Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant:
An Algorithmic Weakening of the Erdős-Hajnal Conjecture. ESA 2020: 23:1-23:18 - [c38]Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width I: tractable FO model checking. FOCS 2020: 601-612 - [c37]Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow:
Maximum Clique in Disk-Like Intersection Graphs. FSTTCS 2020: 17:1-17:18 - [c36]Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-joung Kwon:
Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth. IPEC 2020: 3:1-3:17 - [c35]Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer:
Maximum Matchings in Geometric Intersection Graphs. STACS 2020: 31:1-31:17 - [c34]Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora:
Grundy Coloring & Friends, Half-Graphs, Bicliques. STACS 2020: 58:1-58:18 - 2019
- [c33]Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Lukasz Kowalik:
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP. ESA 2019: 23:1-23:14 - [c32]Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh:
Parameterized Streaming Algorithms for Min-Ones d-SAT. FSTTCS 2019: 8:1-8:20 - [c31]Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant:
When Maximum Stable Set Can Be Solved in FPT Time. ISAAC 2019: 49:1-49:22 - [c30]Édouard Bonnet, Nidhi Purohit:
Metric Dimension Parameterized by Treewidth. IPEC 2019: 5:1-5:15 - [c29]Édouard Bonnet, Diana-Elena Falamas, Rémi Watrigant:
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem. SEA² 2019: 167-183 - 2018
- [c28]Édouard Bonnet, Panos Giannopoulos:
Orthogonal Terrain Guarding is NP-complete. SoCG 2018: 11:1-11:15 - [c27]Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora:
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs. SoCG 2018: 12:1-12:15 - [c26]Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé:
EPTAS for Max Clique on Disks and Unit Balls. FOCS 2018: 568-579 - [c25]Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant:
Parameterized Complexity of Independent Set in H-Free Graphs. IPEC 2018: 17:1-17:13 - [c24]Édouard Bonnet, Florian Sikora:
The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration. IPEC 2018: 26:1-26:15 - [c23]Édouard Bonnet, Pawel Rzazewski, Florian Sikora:
Designing RNA Secondary Structures Is Hard. RECOMB 2018: 248-250 - [c22]Édouard Bonnet, Pawel Rzazewski:
Optimality Program in Segment and String Graphs. WG 2018: 79-90 - 2017
- [c21]Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski:
Fine-Grained Complexity of Coloring Unit Disks and Balls. SoCG 2017: 18:1-18:16 - [c20]Édouard Bonnet, Tillmann Miltzow:
An Approximation Algorithm for the Art Gallery Problem. SoCG 2017: 20:1-20:15 - [c19]Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine:
The Parameterized Complexity of Positional Games. ICALP 2017: 90:1-90:14 - [c18]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. IPEC 2017: 7:1-7:13 - [c17]Édouard Bonnet, Panos Giannopoulos, Michael Lampis:
On the Parameterized Complexity of Red-Blue Points Separation. IPEC 2017: 8:1-8:13 - [c16]Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski:
Complexity of Token Swapping and its Variants. STACS 2017: 16:1-16:14 - 2016
- [c15]Édouard Bonnet, László Egri, Dániel Marx:
Fixed-Parameter Approximability of Boolean MinCSPs. ESA 2016: 18:1-18:18 - [c14]Édouard Bonnet, Tillmann Miltzow:
Parameterized Hardness of Art Gallery Problems. ESA 2016: 19:1-19:17 - [c13]Édouard Bonnet:
The Complexity of Playing Durak. IJCAI 2016: 109-115 - [c12]Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis:
A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs. LATIN 2016: 235-248 - [c11]Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos:
Time-Approximation Trade-offs for Inapproximable Problems. STACS 2016: 22:1-22:14 - [c10]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property. WG 2016: 233-244 - 2015
- [c9]Edouard Bonnet, Florian Jamain, Abdallah Saffidine:
Draws, Zugzwangs, and PSPACE-Completeness in the Slither Connection Game. ACG 2015: 160-176 - [c8]Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora:
Complexity of Grundy Coloring and Its Variants. COCOON 2015: 109-120 - [c7]Edouard Bonnet, Florian Sikora:
The Graph Motif Problem Parameterized by the Structure of the Input Graph. IPEC 2015: 319-330 - 2014
- [c6]Édouard Bonnet, Abdallah Saffidine:
On the Complexity of General Game Playing. CGW@ECAI 2014: 90-104 - [c5]Faisal N. Abu-Khzam, Edouard Bonnet, Florian Sikora:
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism. IWOCA 2014: 1-12 - 2013
- [c4]Edouard Bonnet, Florian Jamain, Abdallah Saffidine:
Havannah and TwixT are PSPACE-complete. Computers and Games 2013: 175-186 - [c3]Edouard Bonnet, Florian Jamain, Abdallah Saffidine:
On the Complexity of Trick-Taking Card Games. IJCAI 2013: 482-488 - [c2]Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos:
On Subexponential and FPT-Time Inapproximability. IPEC 2013: 54-65 - [c1]Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire:
Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization. IPEC 2013: 66-77
Editorship
- 2024
- [e1]Édouard Bonnet, Pawel Rzazewski:
19th International Symposium on Parameterized and Exact Computation, IPEC 2024, September 4-6, 2024, Royal Holloway, University of London, Egham, United Kingdom. LIPIcs 321, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-353-9 [contents]
Data and Artifacts
- 2023
- [d1]Édouard Bonnet, Julien Duron:
RedAlert. Zenodo, 2023
Informal and Other Publications
- 2025
- [i83]Benjamin Bergougnoux, Édouard Bonnet, Julien Duron:
Mim-Width is paraNP-complete. CoRR abs/2501.05638 (2025) - [i82]Édouard Bonnet:
Answering Related Questions. CoRR abs/2501.10633 (2025) - [i81]Pierre Aboulker, Édouard Bonnet, Timothé Picavet, Nicolas Trotignon:
Induced Disjoint Paths Without an Induced Minor. CoRR abs/2502.05289 (2025) - [i80]Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana, Nicolas Trotignon:
Every Graph is Essential to Large Treewidth. CoRR abs/2502.14775 (2025) - [i79]Édouard Bonnet, Robert Hickingbotham:
Induced Minors and Region Intersection Graphs. CoRR abs/2504.21115 (2025) - [i78]Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis, Colin Geniet, Nikolas Mählmann, Michal Pilipczuk, Wojciech Przybyszewski, Szymon Torunczyk:
Separability Properties of Monadically Dependent Graph Classes. CoRR abs/2505.11144 (2025) - [i77]Édouard Bonnet, Daniel Neuen, Marek Sokolowski:
Treedepth Inapproximability and Exponential ETH Lower Bound. CoRR abs/2507.13818 (2025) - 2024
- [i76]Édouard Bonnet, Carl Feghali, Stéphan Thomassé, Nicolas Trotignon:
Graphs without a 3-connected subgraph are 4-colorable. CoRR abs/2402.06338 (2024) - [i75]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev:
Symmetric-Difference (Degeneracy) and Signed Tree Models. CoRR abs/2405.09011 (2024) - [i74]Édouard Bonnet:
Sparse Induced Subgraphs of Large Treewidth. CoRR abs/2405.13797 (2024) - [i73]Édouard Bonnet:
Treewidth Inapproximability and Tight ETH Lower Bound. CoRR abs/2406.11628 (2024) - [i72]Édouard Bonnet, Kristóf Huszár:
On the twin-width of smooth manifolds. CoRR abs/2407.10174 (2024) - [i71]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev:
Adjacency Labeling Schemes for Small Classes. CoRR abs/2409.04821 (2024) - [i70]Manuel Bodirsky, Édouard Bonnet, Zaneta Semanisinová:
Temporal Valued Constraint Satisfaction Problems. CoRR abs/2409.07285 (2024) - [i69]Édouard Bonnet, Pawel Rzazewski:
An 11/6-Approximation Algorithm for Vertex Cover on String Graphs. CoRR abs/2409.18820 (2024) - 2023
- [i68]Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, Aline Parreau:
Neighbourhood complexity of graphs of bounded twin-width. CoRR abs/2301.04217 (2023) - [i67]Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý:
Treewidth is NP-Complete on Cubic Graphs (and related results). CoRR abs/2301.10031 (2023) - [i66]Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek:
Maximum Independent Set when excluding an induced minor: K1 + tK2 and tC3 ⊎ C4. CoRR abs/2302.08182 (2023) - [i65]Édouard Bonnet, Dibyayan Chakraborty, Julien Duron:
Cutting Barnette graphs perfectly is hard. CoRR abs/2302.11667 (2023) - [i64]Édouard Bonnet, Julien Duron:
Stretch-width. CoRR abs/2305.12023 (2023) - [i63]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii:
Small But Unwieldy. CoRR abs/2307.11225 (2023) - [i62]Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé:
Factoring Pattern-Free Permutations into Separable ones. CoRR abs/2308.02981 (2023) - [i61]Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii:
Tight bounds on adjacency labels for monotone graph classes. CoRR abs/2310.20522 (2023) - [i60]Édouard Bonnet, Jedrzej Hodor, Tuukka Korhonen, Tomás Masarík:
Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor. CoRR abs/2312.07962 (2023) - 2022
- [i59]Édouard Bonnet, O-joung Kwon, David R. Wood:
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond). CoRR abs/2202.11858 (2022) - [i58]Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk:
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. CoRR abs/2202.13014 (2022) - [i57]Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé:
Twin-width VIII: delineation and win-wins. CoRR abs/2204.00722 (2022) - [i56]Édouard Bonnet, Hugues Déprés:
Twin-width can be exponential in treewidth. CoRR abs/2204.07670 (2022) - [i55]Édouard Bonnet, Colin Geniet, Romain Tessera, Stéphan Thomassé:
Twin-width VII: groups. CoRR abs/2204.12330 (2022) - [i54]Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek:
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. CoRR abs/2206.00594 (2022) - [i53]Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant:
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width. CoRR abs/2207.07708 (2022) - [i52]Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé:
Twin-width V: linear minors, modular counting, and matrix multiplication. CoRR abs/2209.12023 (2022) - 2021
- [i51]Édouard Bonnet:
4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n4/3. CoRR abs/2101.02312 (2021) - [i50]Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk:
Twin-width IV: ordered graphs and matrices. CoRR abs/2102.03117 (2021) - [i49]Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, Stéphan Thomassé:
Twin-width and permutations. CoRR abs/2102.06880 (2021) - [i48]Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant:
Twin-width and polynomial kernels. CoRR abs/2107.02882 (2021) - [i47]Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, Stéphan Thomassé:
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs. CoRR abs/2110.15419 (2021) - [i46]Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé:
Twin-width VI: the lens of contraction sequences. CoRR abs/2111.00282 (2021) - [i45]Pierre Bergé, Édouard Bonnet, Hugues Déprés:
Deciding twin-width at most 4 is NP-complete. CoRR abs/2112.08953 (2021) - 2020
- [i44]Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora:
Grundy Coloring & friends, Half-Graphs, Bicliques. CoRR abs/2001.03794 (2020) - [i43]Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow:
Maximum Clique in Disk-Like Intersection Graphs. CoRR abs/2003.02583 (2020) - [i42]Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant:
An algorithmic weakening of the Erdős-Hajnal conjecture. CoRR abs/2004.12166 (2020) - [i41]Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width I: tractable FO model checking. CoRR abs/2004.14789 (2020) - [i40]Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width II: small classes. CoRR abs/2006.09877 (2020) - [i39]Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant:
Twin-width III: Max Independent Set and Coloring. CoRR abs/2007.14161 (2020) - [i38]Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-joung Kwon:
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth. CoRR abs/2007.14179 (2020) - [i37]Édouard Bonnet:
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio. CoRR abs/2008.11315 (2020) - [i36]Édouard Bonnet, Sergio Cabello:
The Complexity of Mixed-Connectivity. CoRR abs/2010.04799 (2020) - 2019
- [i35]Édouard Bonnet, Nidhi Purohit:
Metric Dimension Parameterized by Treewidth. CoRR abs/1907.08093 (2019) - [i34]Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Lukasz Kowalik:
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP. CoRR abs/1908.09325 (2019) - [i33]Édouard Bonnet, Diana-Elena Falamas, Rémi Watrigant:
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem. CoRR abs/1908.09586 (2019) - [i32]Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
Parameterized Intractability of Even Set and Shortest Vector Problem. CoRR abs/1909.01986 (2019) - [i31]Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant:
When Maximum Stable Set can be solved in FPT time. CoRR abs/1909.08426 (2019) - [i30]Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer:
Maximum Matchings in Geometric Intersection Graphs. CoRR abs/1910.02123 (2019) - [i29]Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
Parameterized Intractability of Even Set and Shortest Vector Problem. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i28]Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé:
EPTAS for Max Clique on Disks and Unit Balls. CoRR abs/1803.01822 (2018) - [i27]Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant:
Parameterized Complexity of Independent Set in H-Free Graphs. CoRR abs/1810.04620 (2018) - [i26]Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés:
The inverse Voronoi problem in graphs. CoRR abs/1811.12547 (2018) - 2017
- [i25]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms. CoRR abs/1704.06757 (2017) - [i24]Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine:
The Parameterized Complexity of Positional Games. CoRR abs/1704.08536 (2017) - [i23]Édouard Bonnet, Panos Giannopoulos:
Orthogonal Terrain Guarding is NP-complete. CoRR abs/1710.00386 (2017) - [i22]Édouard Bonnet, Panos Giannopoulos, Michael Lampis:
On the Parameterized Complexity of Red-Blue Points Separation. CoRR abs/1710.00637 (2017) - [i21]Édouard Bonnet, Pawel Rzazewski, Florian Sikora:
Designing RNA Secondary Structures is Hard. CoRR abs/1710.11513 (2017) - [i20]Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora:
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs. CoRR abs/1712.05010 (2017) - [i19]Édouard Bonnet, Pawel Rzazewski:
Optimality Program in Segment and String Graphs. CoRR abs/1712.08907 (2017) - 2016
- [i18]Édouard Bonnet, László Egri, Dániel Marx:
Fixed-parameter Approximability of Boolean MinCSPs. CoRR abs/1601.04935 (2016) - [i17]Edouard Bonnet, Florian Sikora:
A note on Edge Isoperimetric Numbers and Regular Graphs. CoRR abs/1601.05190 (2016) - [i16]Édouard Bonnet, Tillmann Miltzow:
Flip Distance to a Non-crossing Perfect Matching. CoRR abs/1601.05989 (2016) - [i15]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Parameterized vertex deletion problems for hereditary graph classes with a block property. CoRR abs/1603.05945 (2016) - [i14]Édouard Bonnet, Tillmann Miltzow:
The Parameterized Hardness of the Art Gallery Problem. CoRR abs/1603.08116 (2016) - [i13]Édouard Bonnet, Florian Jamain, Abdallah Saffidine:
On the Complexity of Connection Games. CoRR abs/1605.04715 (2016) - [i12]Édouard Bonnet, Tillmann Miltzow:
An Approximation Algorithm for the Art Gallery Problem. CoRR abs/1607.05527 (2016) - [i11]Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski:
Complexity of Token Swapping and its Variants. CoRR abs/1607.07676 (2016) - 2015
- [i10]Edouard Bonnet, Michael Lampis, Vangelis Th. Paschos:
Time-Approximation Trade-offs for Inapproximable Problems. CoRR abs/1502.05828 (2015) - [i9]Edouard Bonnet, Florian Sikora:
The parameterized complexity of Graph Motif relatively to the structure of the input graph. CoRR abs/1503.05110 (2015) - 2014
- [i8]Edouard Bonnet, Vangelis Th. Paschos:
Sparsification and subexponential approximation. CoRR abs/1402.2843 (2014) - [i7]Edouard Bonnet, Florian Jamain, Abdallah Saffidine:
Havannah and TwixT are PSPACE-complete. CoRR abs/1403.6518 (2014) - [i6]Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora:
Complexity of Grundy coloring and its variants. CoRR abs/1407.5336 (2014) - [i5]Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis:
On the approximation of maximum $k$-vertex cover in bipartite graphs. CoRR abs/1409.6952 (2014) - [i4]Faisal N. Abu-Khzam, Edouard Bonnet, Florian Sikora:
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism. CoRR abs/1412.1261 (2014) - 2013
- [i3]Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire:
Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization. CoRR abs/1306.2217 (2013) - [i2]Edouard Bonnet, Vangelis Th. Paschos, Florian Sikora:
Multiparameterizations for max $k$-set cover and related satisfiability problems. CoRR abs/1309.4718 (2013) - [i1]Edouard Bonnet, Vangelis Th. Paschos:
Parameterized (in)approximability of subset problems. CoRR abs/1310.5576 (2013)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-11-04 00:47 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
