Minimum Stable Cut and Treewidth

Michail Lampis (Lamsade) 

6 Jully 2021 at 14:00 via Teams

Title: Minimum Stable Cut and Treewidth

 

Abstract: In this talk we study the complexity of the Minimum Stable Cut problem, which consists of finding a partition of the vertices of a given graph where (i) each vertex has the majority of its incident edges going to the other side and despite this (ii) the total weight of cut edges is minimized. Minimum Stable Cut is related to the Local Max Cut problem (from local search algorithms) and the Cut game from Algorithmic Game Theory. Naturally, the problem is NP-hard.  In this talk we will analyze the complexity of Min Stable Cut from the point of view of parameterized complexity, using two of the most standard graph parameters (maximum degree and treewidth) and present upper and lower bounds that essentially match and precisely determine the complexity of the problem, under the ETH.