4 papers
Treedepth Inapproximability and Exponential ETH Lower Bound
Édouard Bonnet, Daniel Neuen, Marek Sokołowski
Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a -time exact algorith…
On the twin-width of smooth manifolds
Édouard Bonnet, Kristóf Huszár
Building on Whitney's classical method of triangulating smooth manifolds, we show that every compact -dimensional smooth manifold admits a triangulation with dual graph of twin-…
Treewidth Inapproximability and Tight ETH Lower Bound
Édouard Bonnet
We present a simple, self-contained, linear reduction from 3-SAT to Treewidth. Specifically, it shows that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly…
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…