Max-Cut Problem Parameterized above Lower Bound on Special Graph Classes

Max-Cut is a problem of partitioning vertices of a graph into two sets with the maximal number of edges between them. Despite this problem being NP-complete, hence probably impossible to solve in polynomial time, parameterized algorithms framework can be employed to solve some of its instances efficiently. The most natural way to parameterize Max-Cut is parameterization above lower bounds. Formally Max-Cut parameterized above a lower bound LB(G) is defined as follows: given a graph G and a parameter k, check whether the graph admits a cut of size LB(G) + k. There is a known algorithm for Max-Cut above lower bound of |V|-1 with a running time of 2^(O(k))poly(|G|) cite(max-cut-ast). We develop this parameterization further by presenting a polynomial preprocessing algorithm that reduces graph size to O(k) and algorithms with running time of 2^(sqrt k)poly(|G|) for chordal and co-bipartite graphs. The algorithm for chordal graphs is asymptotically optimal even when restricted to split graphs. For tripartite graphs we prove asymptotical optimality of general case algorithm as well as provide a polynomial algorithm obtaining a tripartite-specific lower bound of 2|E|/3.