Name
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 2V 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 2V 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 2V 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1109557.1109646 | SODA |
Keywords | Field | DocType |
fixed field,arbitrary symmetric submodular function,integer-valued symmetric submodular function,constant k,connectivity function,symmetric submodular function,large branch-width,finite set,polynomial size,computational complexity,fixed k,facet,graph,linear inequalities,face,vertex,polyhedron,polytope,cycle | Matroid,Discrete mathematics,Combinatorics,Finite set,Polynomial,Vertex (geometry),Polyhedron,Submodular set function,Polytope,Linear inequality,Mathematics | Conference |
ISBN | Citations | PageRank |
0-89871-605-5 | 2 | 0.38 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sang-il Oum | 1 | 668 | 37.80 |
| Paul Seymour | 2 | 4 | 0.89 |