Testing branch-width

Sang il Oum, Paul Seymour

Research output: Contribution to journalArticle

32 Scopus citations

Abstract

An integer-valued function f on the set 2V of all subsets of a finite set V is a connectivity function if it satisfies the following conditions: (1) f (X) + f (Y) ≥ f (X ∩ Y) + f (X ∪ Y) for all subsets X, Y of V, (2) f (X) = f (V {set minus} X) for all X ⊆ V, and (3) f (∅) = 0. Branch-width is defined for graphs, matroids, and more generally, connectivity functions. We show that for each constant k, there is a polynomial-time (in | V |) algorithm to decide whether the branch-width of a connectivity function f is at most k, if f is given by an oracle. This algorithm can be applied to branch-width, carving-width, and rank-width of graphs. In particular, we can recognize matroids M of branch-width at most k in polynomial (in | E (M) |) time if the matroid is given by an independence oracle.

Original languageEnglish (US)
Pages (from-to)385-393
Number of pages9
JournalJournal of Combinatorial Theory. Series B
Volume97
Issue number3
DOIs
StatePublished - May 1 2007

All Science Journal Classification (ASJC) codes

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

Keywords

  • Branch-width
  • Carving-width
  • Connectivity function
  • Rank-width
  • Symmetric submodular function
  • Tangle

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

  • Cite this