Abstract
An integral-valued set function
f
:
2
V↦
Z
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
α⩽β
(
log
t)/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β)
log
t
for all
β⩾1. We also give examples of polymatroid functions with arbitrarily large
t,
n,
α
and
β for which
α⩾β
(0.551
log
t)/c
. More generally, given a polymatroid function
f:2
V↦
Z
and an integral threshold
t⩾1, consider an arbitrary hypergraph
H
such that
|
H|⩾2
and
f(
H)⩾
t for all
H∈
H
. Let
S
be the family of all maximal independent sets
X of
H
for which
f(
X)<
t. Then
|
S|⩽|
H|
(
log
t)/c(n,|
H|)
. As an application, we show that given a system of polymatroid inequalities
f
1(
X)⩾
t
1,…,
f
m
(
X)⩾
t
m
with quasi-polynomially bounded right-hand sides
t
1,…,
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.