Follow

The first sighting of one of my Wikipedia illustrations in a SODA talk goes to Michał Włodarczyk, whose "Losing treewidth by separating subsets" (doi.org/10.1137/1.978161197548) concerns removing few graph vertices to reach a subgraph with some desired property. If the optimal solution removes \(k\) vertices and graphs with the property have treewidth \(\le t\), then his solution removes \(O(k\log t)\) vertices and takes the same time as exactly solving \(O(\log n)\) subproblems of size \(O(t\log t)\).

Sign in to participate in the conversation
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.