Tight Bounds for some Classical Problems Parameterized by Cutwidth

Narek Bojikian, Vera Chekan, Stefan Kratsch

Cutwidth is a widely studied parameter that quantifies how well a graph can be decomposed along small edge-cuts. It complements pathwidth, which captures decomposition by small ver…