Szabó Dániel Péter: Cut Varieties on Tree Varieties

EGERVÁRY SZEMINÁRIUM

Abstract:
The minimum cut problem asks to find a minimum weight subset of the edges of a graph that separates two given terminal nodes. There are multiple ways to generalize this to multiple terminals, such as k-way cut, multiway cut, multicut, multi-multiway cut, etc. I will define these and discuss their complexity, as well as show their tractability (or intractability) when the given input graph has bounded tree width, or equivalently bounded branch width.