8 citations · 9 across the 3 of their papers we have counts for
5 papers
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
Pierre Bergé, Édouard Bonnet, Hugues Déprés +1
For any , we give a polynomial-time -approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an -sequence.…
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…
Twin-width can be exponential in treewidth
Édouard Bonnet, Hugues Déprés
For any small positive real and integer , we build a graph with a vertex deletion set of size to a tree, and twin-width greater than $2…
Deciding twin-width at most 4 is NP-complete
Pierre Bergé, Édouard Bonnet, Hugues Déprés
We show that determining if an -vertex graph has twin-width at most 4 is NP-complete, and requires time unless the Exponential-Time Hypothesis fails. Along the…
Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments
Jørgen Bang-Jensen, Hugues Depres, Anders Yeo
A digraph is {\bf eulerian} if it is connected and every vertex has its in-degree equal to its out-degree. Having a spanning eulerian subdigraph is thus a weakening of having a ham…