A Unifying Framework for Characterizing and Computing Width Measures
summary
Paper defines F-branch width and proves any reasonable cut-function comes from a partner-hereditary family, shows only six size-identifiable families matter and further reduces to three primal families (matchings, anti-matchings, chains), so treewidth/clique-width/min-width become instances of one framework. Provides exact/FPT algorithms: F*-branch width is FPT parameterized by treewidth+maximum degree, by treedepth, and admits a linear kernel by feedback-edge-set. Computing min-width parameterized by the target remains open.
AI-written summary · about