An inequality for polymatroid functions and its applications

An integral-valued set function f:2^V → ℤ is called polymatroid if it is submodular, non-decreasing, and f(ø) = 0. Given a polymatroid function f and an integer threshold t ≥ 1, let α = α(f,t) denote the number of maximal sets X ⊆ V satisfying f(X) < t, let β = β(f,t) be the number of minimal sets X ⊆ V for which f(X) ≥ t, and let n = |V|. We show that if β ≥ 2 then α ≤ β^(logt)/c, where c = c(n,β) is the unique positive root of the equation 1 = 2^c(n^c/logβ-1). In particular, our bound implies that α ≤ (nβ)^logt for all β ≥ 1. We also give examples of polymatroid functions with arbitrarily large t, n, α and β for which α ≥ β^{(0.551logt)/c}. More generally, given a polymatroid function f : 2^V → ℤ and an integral threshold t ≥ 1, consider an arbitrary hypergraph ℋ such that |ℋ| ≥ 2 and f(H) ≥ t for all H ∈ ℋ. Let ℒ be the family of all maximal independent sets X of ℋ for which f(X) < t. Then |ℒ| ≤ |ℋ|^{(logt)/c(n,|ℋ|)}. As an application, we show that given a system of polymatroid inequalities f₁(X) ≥ t₁,..., f_m(X) ≥ t_m with quasi-polynomially bounded right-hand sides t₁,...,t_m, all minimal feasible solutions to this system can be generated in incremental quasi-polynomial time. In contrast to this result, the generation of all maximal infeasible sets is an NP-hard problem for many polymatroid inequalities of small range.