Approximating clique-width and branch-width (Q2496203): Difference between revisions

The authors show that, for fixed \(k\), there is an algorithm that with input an \(n\)-vertex graph \(G\), either decides that \(G\) has clique-width at least \(k+1\) or outputs a decomposition of \(G\) with clique-width at most \(2^{3k+2}-1\). The running time of the algorithm is shown to be \(\mathbb{O}(n^9 \log{n})\). The main tool for this algorithm is branch-width, which was introduced by \textit{N. Robertson} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 52, 153-190 (1991; Zbl 0764.05069)]. The present authors develop a general algorithm to approximate the branch-width of certain symmetric submodular functions. Then the ``rank-width'' of a graph is defined and it is shown that bounded clique-width implies bounded rank-width and vice versa. Consequently clique-width can be approximated in polynomial time. Additionally the algorithm is applied to matroids: For fixed \(k\) there is an algorithm which, with input an \(n\)-element matroid \(M\) in terms of its rank oracle, either decides that \(M\) has branch-width at least \(k+1\), or outputs a branch-decomposition for \(M\) of width at most \(3k-1\). The running time of the algorithm is \(\mathbb{O}(n^{3.5})\).