×

Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3. (English) Zbl 1167.68060

Let \(G=(V,E)\) be a graph. Then a partition \(\mathcal V=(V_1,V_2)\) of \( V\) is a cut of \(G\) and the number of edges \(\{v_1,v_2\}\in E\) with \(v_i\in V_i\) for \(i=1,2\) is the size of \(\mathcal V\). Let \(mc(G)\) be the maximum size over cuts of \(G\). It is well known that it is NP-hard to construct a cut of size \(mc(G)\) also for subcubic graphs (a graph is subcubic if every vertex has degree at most \(3\)). The paper presents an algorithm constructing, for a given subcubic graph \(G\), a cut of \(G\) of size greater than \(\frac 56\,mc(G)\). The algorithm is based on a special decomposition of a graph into subgraphs depending on cycles. The authors give an example of a non-subcubic graph which has no such decomposition. A comparison of this algorithm with similar algorithms is presented.

MSC:

68W25 Approximation algorithms
05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
90C27 Combinatorial optimization
Full Text: DOI

References:

[1] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM Journal on Optimization, 5, 1, 13-51 (1995) · Zbl 0833.90087
[2] Berman, P.; Karpinski, M., On some tighter inapproximability results, (Proceedings of the 26th International Colloquium on Automata, Languages and Programming. Proceedings of the 26th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 1644 (1999), Springer), 200-209
[3] Bodlaender, H. L., On disjoint cycles, International Journal of Foundations of Computer Science, 5, 1, 59-68 (1994) · Zbl 0803.05030
[4] Bondy, J. A.; Locke, S. C., Largest bipartite subgraphs in triangle-free graphs with maximum degree three, Journal of Graph Theory, 10, 477-504 (1986) · Zbl 0609.05046
[5] Deza, M.; Laurent, M., Applications of cut polyhedra. I, II, Journal of Computational and Applied Mathematics, 55, 2, 191-216 (1994), 217-247 · Zbl 0826.52012
[6] Erdős, P.; Pósa, L., On the maximal number of disjoint circuits of a graph, Publicationes Mathematicae Debrecen, 9, 3-12 (1962), MR0150756 (27#743) · Zbl 0133.16701
[7] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 1115-1145 (1995) · Zbl 0885.68088
[8] Halperin, E.; Livnat, D.; Zwick, U., MAX CUT in cubic graphs, Journal of Algorithms, 53, 169-185 (2004), Preliminary version in: Proceedings of SODA 2002, pp. 506-513 · Zbl 1089.68077
[9] Hopkins, G.; Staton, W., Extremal bipartite subgraphs of cubic triangle-free graphs, Journal of Graph Theory, 6, 115-121 (1982) · Zbl 0486.05036
[10] Ngoc, N. V.; Tuza, Zs., Linear-time approximation algorithms for the max-cut problem, Combinatorics, Probability and Computing, 2, 2, 201-210 (1993) · Zbl 0803.68086
[11] Poljak, S.; Tuza, Zs., Maximum cuts and large bipartite subgraphs, (Cook, W.; etal., Combinatorial Optimization. Combinatorial Optimization, DIMACS series in Discrete Mathematics and Theoretical Computer Science, vol. 20 (1995), American Mathematical Society), 181-244 · Zbl 0834.05001
[12] M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proceedings of the 10th ACM Symposium on the Theory of Computing, 1978, pp. 253-264; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proceedings of the 10th ACM Symposium on the Theory of Computing, 1978, pp. 253-264 · Zbl 1282.68131
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.