Finding small separators in linear time via treewidth reduction

Dániel Marx, Barry O'Sullivan, Igor Razgon

We present a method for reducing the treewidth of a graph while preserving all of its minimal $s-t$ separators up to a certain fixed size $k$. This technique allows us to solve $s-…