Approximating max-cut under graph-MSO constraints. (English) Zbl 1476.90340
Summary: 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.
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 90C39 | Dynamic programming |
References:
| [1] | Ageev, A. A.; Hassin, R.; Sviridenko, M., A 0.5-approximation algorithm for MAX DICUT with Given Sizes of Parts, SIAM J. Discrete Math., 14, 2, 246-255 (2001) · Zbl 0968.68198 |
| [2] | Ageev, A. A.; Sviridenko, M., Approximation algorithms for maximum coverage and max cut with given sizes of parts, (Cornuéjols, G.; Burkard, R. E.; Woeginger, G. J., Integer Programming and Combinatorial Optimization, IPCO 1999. Integer Programming and Combinatorial Optimization, IPCO 1999, Lec. Notes in Comp. Sci., vol. 1610 (1999)), 17-30 · Zbl 0948.90122 |
| [3] | Barahona, F.; Grötschel, M.; Jünger, M.; Reinelt, G., An application of combinatorial optimization to statistical physics and circuit layout, Oper. Res., 36, 493-513 (1988) · Zbl 0646.90084 |
| [4] | Bodlaender, H. L., NC-algorithms for graphs with small treewidth, (van Leeuwen, J., Graph-Theoretic Concepts in Computer Science, WG 1988, Amsterdam, the Netherlands, June 15-17, 1988. Graph-Theoretic Concepts in Computer Science, WG 1988, Amsterdam, the Netherlands, June 15-17, 1988, Lec. Notes in Comp. Sci., vol. 344 (1988)), 1-10 · Zbl 1533.68211 |
| [5] | Chang, K. C.; Du, D. H., Efficient algorithms for layer assignment problem, IEEE Trans. CAD Integr. Circuits Syst., 6, 1, 67-78 (1987) |
| [6] | Chekuri, C.; Vondrák, J.; Zenklusen, R., Submodular function maximization via the multilinear relaxation and contention resolution schemes, SIAM J. Comp., 43, 1831-1879 (2014) · Zbl 1437.90135 |
| [7] | Courcelle, B., On the expression of graph properties in some fragments of monadic second-order logic, (Immerman, N.; Kolaitis, P., Descriptive Complexity and Finite Models, Vol. 31 (1997), DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences), 33-62 · Zbl 0883.03004 |
| [8] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (2012), Springer Science & Business Media · Zbl 0914.68076 |
| [9] | Feldman, M.; Naor, J.; Schwartz, R., A unified continuous greedy algorithm for submodular maximization, (Ostrovsky, R., IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011 (2011), IEEE Computer Society), 570-579 · Zbl 1292.90248 |
| [10] | Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145 (1995) · Zbl 0885.68088 |
| [11] | Hajiaghayi, M. T.; Kortsarz, G.; MacDavid, R.; Purohit, M.; Sarpatwar, K. K., Approximation algorithms for connected maximum cut and related problems, (Bansal, N.; Finocchi, I., Algorithms - ESA 2015, Patras, Greece, September 14-16, 2015. Algorithms - ESA 2015, Patras, Greece, September 14-16, 2015, Lec. Notes in Comp. Sci., vol, 9294 (2015)), 693-704 · Zbl 1420.68237 |
| [12] | Jalali, A.; Srebro, N., Clustering using max-norm constrained optimization, (ICML 2012, Edinburgh, Scotland, June 26 - July 1, 2012 (2012), Omnipress) |
| [13] | Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R., Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comp., 37, 1, 319-357 (2007) · Zbl 1135.68019 |
| [14] | Knop, D.; Koutecký, M.; Masařík, T.; Toufar, T., Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, (Bodlaender, H. L.; Woeginger, G. J., Graph-Theoretic Concepts in Computer Science, WG 2017, Eindhoven, the Netherlands, June 21-23, 2017. Graph-Theoretic Concepts in Computer Science, WG 2017, Eindhoven, the Netherlands, June 21-23, 2017, Lec. Notes in Comp. Sci., vol. 10520 (2017)), 344-357, Full version available at https://arxiv.org/abs/1703.00544 · Zbl 1484.68072 |
| [15] | Lee, J. D.; Recht, B.; Salakhutdinov, R.; Srebro, N.; Tropp, J. A., Practical large-scale optimization for max-norm regularization, (Lafferty, J. D.; Williams, C. K.I.; Shawe-Taylor, J.; Zemel, R. S.; Culotta, A., Advances in Neural Information Processing Systems, NIPS 2010 (2010), Curran Assoc.), 1297-1305 |
| [16] | Shen, X.; Lee, J.; Nagarajan, V., Approximating graph-constrained max-cut, Math. Prog. Ser. B, 172, 1, 35-58 (2018) · Zbl 1406.90106 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
