Certifying large branch-width

Research output: Contribution to conferencePaper

4 Scopus citations

Abstract

Branch-width is defined for graphs, matroids, and, more generally, arbitrary symmetric submodular functions. For a finite set V, a function f on the set of subsets 2 V of V is submodular if f(X) + f(Y) ≥ f(X ∩ Y) + f(X ∪ Y), and symmetric if f(X) = f(V \ X). We discuss the computational complexity of recognizing that symmetric submodular functions have branch-width at most k for fixed k. An integer-valued symmetric submodular function f on 2 V is a connectivity function if f(ø) = 0 and f({v}) ≤ 1 for all v ∈ V. We show that for each constant k, if a connectivity function f on 2 V is presented by an oracle and the branch-width of f is larger than k, then there is a certificate of polynomial size (in |V|) such that a polynomial-time algorithm can verify the claim that branch-width of f is larger than k. In particular it is in coNP to recognize matroids represented over a fixed field with branch-width at most k for fixed k.

Original languageEnglish (US)
Pages810-813
Number of pages4
DOIs
StatePublished - Feb 28 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityMiami, FL
Period1/22/061/24/06

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

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

  • Cite this

    Oum, S. I., & Seymour, P. D. (2006). Certifying large branch-width. 810-813. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States. https://doi.org/10.1145/1109557.1109646