×

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.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Johansson, Ö., \(\log n\)-approximative \(\operatorname{NLC}_k\)-decomposition in \(O(n^{2 k + 1})\) time (extended abstract), (), 229-240
[2] Hliněný, P., A parametrized algorithm for matroid branch-width, SIAM J. comput., 35, 2, 259-277, (2005) · Zbl 1088.05023
[3] Downey, R.G.; Fellows, M.R., Parameterized complexity, Monogr. comput. sci., (1999), Springer New York · Zbl 0914.68076
[4] 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
[5] Courcelle, B.; Olariu, S., Upper bounds to the clique width of graphs, Discrete appl. math., 101, 1-3, 77-114, (2000) · Zbl 0958.05105
[6] 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
[7] Gurski, F.; Wanke, E., The tree-width of clique-width bounded graphs without \(K_{n, n}\), (), 196-205 · Zbl 0988.68131
[8] Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, (), 313-400
[9] Robertson, N.; Seymour, P., Graph minors. XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 1, 65-110, (1995) · Zbl 0823.05038
[10] Wanke, E., k-NLC graphs and polynomial algorithms, Discrete appl. math., 54, 2-3, 251-266, (1994) · Zbl 0812.68106
[11] 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
[12] 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
[13] 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
[14] Robertson, N.; Seymour, P., Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 2, 153-190, (1991) · Zbl 0764.05069
[15] Oxley, J.G., Matroid theory, (1992), Oxford Univ. Press New York · Zbl 0784.05002
[16] 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
[17] 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
[18] Reed, B.A., Tree width and tangles: A new connectivity measure and some applications, (), 87-162 · Zbl 0895.05034
[19] 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
[20] Murota, K., Matrices and matroids for systems analysis, Algorithms combin., vol. 20, (2000), Springer Berlin · Zbl 0948.05001
[21] Truemper, K., Matroid decomposition, (1992), Academic Press Boston, MA · Zbl 0760.05001
[22] Truemper, K., A decomposition theory for matroids. I. general results, J. combin. theory ser. B, 39, 1, 43-76, (1985) · Zbl 0551.05033
[23] Schrijver, A., Combinatorial optimization. polyhedra and efficiency, vol. B, Algorithms combin., vol. 24, (2003), Springer Berlin
[24] 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.