Prof. Meirav Zehavi

Every connected graph on n vertices has a cut of size at least n − 1. We call this bound the spanning tree bound. In the Max-Cut Above Spanning Tree (Max-Cut-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least n − 1 + k. We show that Max-Cut-AST admits an algorithm that runs in time O(8 ^kn^{O ( 1 )}) , and hence it is fixed parameter tractable with respect to k. Furthermore, we show that Max-Cut-AST has a polynomial kernel of size O(k⁵).