Approximating Max-Cut under Graph-MSO Constraints

2018/03/15 by Martin Koutecký, Jon Lee, Koutecký, Martin +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Formal Methods in Verification

paper · pdf · doi:10.48550/arxiv.1803.05718

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 (1)/(2)-approximation algorithm for this class of problems.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

Related

• A Max-Cut approximation using a graph based MBO scheme
• Max-Cut with Multiple Cardinality Constraints
• Parameterized Algorithms for Maximum Cut with Connectivity Constraints
• Exact Algorithms for MaxCut on Split Graphs
• Near-optimal approximation algorithm for simultaneous Max-Cut