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⁵).