Fixed-Parameter Tractable Algorithm and Polynomial Kernel for Max-Cut Above Spanning Tree

摘要

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 (MAXCUT-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(8kn 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(k5).