# zbMATH — the first resource for mathematics

Approximating clique-width and branch-width. (English) Zbl 1114.05022
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 N. Robertson and 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})$$.

##### MSC:
 05B35 Combinatorial aspects of matroids and geometric lattices 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
algorithm; rank-width; submodular function; matroid
Full Text:
##### References:
  Johansson, Ö., $$\log n$$-approximative $$\operatorname{NLC}_k$$-decomposition in $$O(n^{2 k + 1})$$ time (extended abstract), (), 229-240  Hliněný, P., A parametrized algorithm for matroid branch-width, SIAM J. comput., 35, 2, 259-277, (2005) · Zbl 1088.05023  Downey, R.G.; Fellows, M.R., Parameterized complexity, Monogr. comput. sci., (1999), Springer New York · Zbl 0914.68076  Corneil, D.G.; Rotics, U., On the relationship between clique-width and tree-width, SIAM J. comput., 34, 4, 825-847, (2005), (electronic) · Zbl 1069.05067  Courcelle, B.; Olariu, S., Upper bounds to the clique width of graphs, Discrete appl. math., 101, 1-3, 77-114, (2000) · Zbl 0958.05105  Espelage, W.; Gurski, F.; Wanke, E., Deciding clique-width for graphs of bounded tree-width, J. graph algorithms appl., 7, 2, 141-180, (2003) · Zbl 1027.05093  Gurski, F.; Wanke, E., The tree-width of clique-width bounded graphs without $$K_{n, n}$$, (), 196-205 · Zbl 0988.68131  Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, (), 313-400  Robertson, N.; Seymour, P., Graph minors. XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 1, 65-110, (1995) · Zbl 0823.05038  Wanke, E., k-NLC graphs and polynomial algorithms, Discrete appl. math., 54, 2-3, 251-266, (1994) · Zbl 0812.68106  Kobler, D.; Rotics, U., Edge dominating set and colorings on graphs with fixed clique-width, Discrete appl. math., 126, 2-3, 197-221, (2003) · Zbl 1009.05103  Espelage, W.; Gurski, F.; Wanke, E., How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time, (), 117-128 · Zbl 1042.68626  Courcelle, B.; Makowsky, J.A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory comput. syst., 33, 2, 125-150, (2000) · Zbl 1009.68102  Robertson, N.; Seymour, P., Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 2, 153-190, (1991) · Zbl 0764.05069  Oxley, J.G., Matroid theory, (1992), Oxford Univ. Press New York · Zbl 0784.05002  Corneil, D.G.; Perl, Y.; Stewart, L.K., A linear recognition algorithm for cographs, SIAM J. comput., 14, 4, 926-934, (1985) · Zbl 0575.68065  Corneil, D.G.; Habib, M.; Lanlignel, J.-M.; Reed, B.; Rotics, U., Polynomial time recognition of clique-width ⩽3 graphs (extended abstract), (), 126-134 · Zbl 0961.05062  Reed, B.A., Tree width and tangles: A new connectivity measure and some applications, (), 87-162 · Zbl 0895.05034  Iwata, S.; Fleischer, L.; Fujishige, S., A combinatorial strongly polynomial algorithm for minimizing submodular functions, J. ACM, 48, 4, 761-777, (2001) · Zbl 1127.90402  Murota, K., Matrices and matroids for systems analysis, Algorithms combin., vol. 20, (2000), Springer Berlin · Zbl 0948.05001  Truemper, K., Matroid decomposition, (1992), Academic Press Boston, MA · Zbl 0760.05001  Truemper, K., A decomposition theory for matroids. I. general results, J. combin. theory ser. B, 39, 1, 43-76, (1985) · Zbl 0551.05033  Schrijver, A., Combinatorial optimization. polyhedra and efficiency, vol. B, Algorithms combin., vol. 24, (2003), Springer Berlin  Cunningham, W.H., Improved bounds for matroid partition and intersection algorithms, SIAM J. comput., 15, 4, 948-957, (1986) · Zbl 0619.68040
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.