Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Max-Cut Above Spanning Tree is Fixed-Parameter Tractable
verfasst von : Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi
Erschienen in: Computer Science – Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \(\mathcal {O}(8^kn^{\mathcal {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 \(\mathcal {O}(k^5)\).