Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3 (Q1018104)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3 |
scientific article |
Statements
Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3 (English)
0 references
13 May 2009
0 references
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.
0 references
maximum cut
0 references
cubic graph
0 references
approximation algorithm
0 references
unicyclic graph
0 references
vertex decomposition
0 references
0 references
0 references