Showing 2024Show all
2 papers · 1 filter
math.GT2024
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-…
cs.CC2024
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…