Édouard Bonnet

activity

20152026

most citedEPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

13 citations · 48 across the 17 of their papers we have counts for

collaborators

Showing 2026 · cs.CCShow all

2 papers · 2 filters

cs.CC2026

Arc Kayles is PSPACE-complete

Édouard Bonnet

We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1978.

cs.CC2026

Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

Édouard Bonnet

For every $ε > 0$ , it is NP-hard to $n^{1 - ε}$ -approximate Max Independent Set in $n$ -vertex graphs [Hastad '96, Zuckerman '07]. In triangle-free graphs, a simpl…