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 0.5-approximation algorithm for this class of problems.

Keywords

• Max cut
• Approximation algorithm
• Monadic second-order logic
• Treewidth
• Dynamic program