Approximating Max-Cut under Graph-MSO Constraints
classification
💻 cs.CC
keywords
constraintsmax-cutproblemsunderalgorithmapproachapproximatingapproximation
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.