Back to Search
Start Over
Approximating Max-Cut under Graph-MSO Constraints
- Publication Year :
- 2018
-
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.<br />Comment: arXiv admin note: text overlap with arXiv:1511.08152
- Subjects :
- Computer Science - Computational Complexity
68W25, 68W05, 68R10
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1803.05718
- Document Type :
- Working Paper