An integral-valued set function $f:2^V \mapsto \ZZ$ is called polymatroid if it is submodular, non-decreasing, and $f(\emptyset)=0$. Given a polymatroid function $f$ and an integer threshold $t\geq 1$, let $\alpha=\alpha(f,t)$ denote the number of maximal sets $X \subseteq V$ satisfying $f(X) < t$, let $\beta=\beta(f,t)$ be the number of minimal sets $X \subseteq V $ for which $f(X) \ge t$, and let $n=|V|$. We show that if $\beta \ge 2$ then $\alpha \le \beta^{(\log t)/c}$, where $c=c(n,\beta)$ is the unique positive root of the equation $1=2^c(n^{c/\log\beta}-1)$. In particular, our bound implies that $\alpha \le (n\beta)^{\log t}$ for all $\beta \ge 1$. We also give examples of polymatroid functions with arbitrarily large $t, n, \alpha$ and $\beta$ for which $\alpha \ge \beta^{(.551 \log t)/c}$.
More generally, given a polymatroid function $f:2^V \mapsto \ZZ$
and an integral threshold $t \ge 1$, consider an arbitrary
hypergraph $\cH$ such that $|\cH| \ge 2$ and $f(H) \ge t$ for all
$H \in \cH$. Let $\cS$ be the family of all maximal independent
sets $X$ of $\cH$ for which $f(X) < t$. Then $|\cS| \leq
|\cH|^{(\log t)/c(n,|\cH|)}$. As an application, we show that
given a system of polymatroid inequalities $f_1(X) \ge
t_1,\ldots,f_m(X) \ge t_m$ with quasi-polynomially bounded right
hand sides $t_1,\ldots,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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-14.ps.gz
DIMACS Home Page