research
∙
07/15/2022
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
For any ε > 0, we give a polynomial-time n^ε-approximation algorithm for...
share
research
∙
06/01/2022
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
A graph is O_k-free if it does not contain k pairwise vertex-disjoint an...
research
∙
04/15/2022
Twin-width can be exponential in treewidth
For any small positive real ε and integer t > 1/ε, we build a graph with...
research
∙
12/16/2021