Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


A result of Balas andYu (1989) states that the number of maximal independent sets of a graph G is at most δp + 1, where δ 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 B in the product of n lattices L = L1 ×... × Ln, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into B. 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 ⊂ L = L1 ×...× Ln for a system of polymatroid inequalities f 1(x) ≥ t1,.., fr (x) ≥ tr does not exceed max{Q, βlogt/c(2Q,β)}, where β is the number of minimal feasible vectors for the system, Q = |L1| +.. + |L n|, t = max{t1,.., tr}, and c(ρ, β) is the unique positive root of the equation 2cc/logβ-1) = 1. This bound is nearly sharp for the Boolean case L = {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 t1,.., tr.

Original languageBritish English
Pages (from-to)355-368
Number of pages14
JournalMathematical Programming
Issue number1-3
StatePublished - 2003


  • Dualization
  • Hypergraph
  • Incremental algorithm
  • Lattice
  • Maximal independent set
  • Polymatroid function
  • Proper mapping
  • System of polymatroid inequalities


Dive into the research topics of 'Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices'. Together they form a unique fingerprint.

Cite this