Approximating max-cut under graph-MSO constraints

DOI10.1016/J.ORL.2018.10.004MaRDI QIDQ2294245zbMATH OpenOpenAlexWikidataFDO

Authors Martin Koutecký, Jon Lee, Viswanath Nagarajan, Xiangkun Shen

Publication date 10 February 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.05718

zbMATH Keywords

approximation algorithmtreewidthmonadic second-order logicdynamic programmax cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39)

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

Recommendations

• Max-cut under graph constraints
• Approximating graph-constrained max-cut
• Max-Cut and containment relations in graphs
• \textsc{max-cut} and containment relations in graphs
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION

Cites work

• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• scientific article; zbMATH DE number 1059243 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Approximating graph-constrained max-cut
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Submodular function maximization via the multilinear relaxation and contention resolution schemes

Cited in

(3)

• Approximating graph-constrained max-cut
• Max-Cut and containment relations in graphs
• Max-cut under graph constraints

This page was built for publication: Approximating max-cut under graph-MSO constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294245)