Approximating clique-width and branch-width

Sang il Oum, Paul Seymour

Research output: Contribution to journalArticle

272 Scopus citations

Abstract

We construct a polynomial-time algorithm to approximate the branch-width of certain symmetric submodular functions, and give two applications. The first is to graph "clique-width." Clique-width is a measure of the difficulty of decomposing a graph in a kind of tree-structure, and if a graph has clique-width at most k then the corresponding decomposition of the graph is called a "k-expression." We find (for fixed k) an O ( n9 log n )-time algorithm that, with input an n-vertex graph, outputs either a ( 23 k + 2 - 1 )-expression for the graph, or a witness that the graph has clique-width at least k + 1. (The best earlier algorithm, by Johansson [Ö. Johansson, log n-approximative NLCk-decomposition in O ( n2 k + 1 ) time (extended abstract), in: Graph-Theoretic Concepts in Computer Science, Boltenhagen, 2001, in: Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, 2001, pp. 229-240], constructs a 2 k log n-expression for graphs of clique-width at most k.) It was already known that several graph problems, NP-hard on general graphs, are solvable in polynomial time if the input graph comes equipped with a k-expression (for fixed k). As a consequence of our algorithm, the same conclusion follows under the weaker hypothesis that the input graph has clique-width at most k (thus, we no longer need to be provided with an explicit k-expression). Another application is to the area of matroid branch-width. For fixed k, we find an O ( n3.5 )-time algorithm that, with input an n-element matroid in terms of its rank oracle, either outputs a branch-decomposition of width at most 3 k - 1 or a witness that the matroid has branch-width at least k + 1. The previous algorithm by Hliněný [P. Hliněný, A parametrized algorithm for matroid branch-width, SIAM J. Comput. 35 (2) (2005) 259-277] works only for matroids represented over a finite field.

Original languageEnglish (US)
Pages (from-to)514-528
Number of pages15
JournalJournal of Combinatorial Theory. Series B
Volume96
Issue number4
DOIs
StatePublished - Jul 1 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Branch-width
  • Clique-width
  • Matroid
  • Rank-width
  • Submodular functions

Fingerprint Dive into the research topics of 'Approximating clique-width and branch-width'. Together they form a unique fingerprint.

  • Cite this