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


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