Approximating Max-Cut under Graph-MSO Constraints

Abstract

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.

arXiv admin note: text overlap with arXiv:1511.08152