Approximating Max-Cut under Graph-MSO Constraints

We consider the max-cut and max-\(k\)-cut problems under graph-based constraints. Our approach can handle any constraint specified using monadic second-order (MSO) logic on graphs of constant treewidth. We give a \(\frac{1}{2}\)-approximation algorithm for this class of problems.

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-10
Main Authors: Koutecký, Martin, Lee, Jon, Nagarajan, Viswanath, Shen, Xiangkun
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the max-cut and max-\(k\)-cut problems under graph-based constraints. Our approach can handle any constraint specified using monadic second-order (MSO) logic on graphs of constant treewidth. We give a \(\frac{1}{2}\)-approximation algorithm for this class of problems.
ISSN:2331-8422