DIMACS TR: 2002-27
Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices
Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan
ABSTRACT
A result of Balas and Yu (1989) states that
the number of maximal independent sets of a graph $G$ is
at most $\delta^{p} + 1$,
where $\delta$ is the number of pairs of vertices in $G$ at distance 2,
and $p$ is the cardinality of a maximum induced matching in $G$.
In this paper, we give an analogue of this result for hypergraphs
and, more generally, for subsets of vectors $\cB$
in the product of $n$ lattices $\cL=\cL_1\times\cdots\times\cL_n$,
where the notion of an induced matching in $G$
is replaced by a certain binary tree each internal node of which
is mapped into $\cB$.
We show that our bounds may be nearly sharp for arbitrarily large
hypergraphs and lattices.
As an application, we prove that the number of maximal infeasible
vectors $x \in \cL=\cL_1\times\cdots\times\cL_n$ for
a system of polymatroid inequalities $f_1(x) \ge t_1,\ldots,f_r(x) \ge
t_r$ does not exceed $\max\{Q,\beta^{\log t/c(2Q,\beta)}\}$, where
$\beta$ is the number of minimal feasible
vectors for the system, $Q=|\cL_1|+\ldots+|\cL_n|$,
$t=\max\{t_1,\ldots,t_r\}$, and
$c(\rho,\beta)$ is the unique positive root of
the equation $2^c(\rho^{c/\log \beta}-1)=1$.
This bound is nearly sharp for the Boolean case $\cL=\{0,1\}^n$,
and it allows for the efficient generation of all minimal feasible sets
to a given system of polymatroid inequalities with quasi-polynomially
bounded right-hand sides $t_1, \ldots, t_m$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-27.ps.gz
DIMACS Home Page