Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3 (Q1018104)

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.