Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Journal Article

Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices


Elbassioni,  Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Boros, E., Elbassioni, K. M., Khachiyan, L., & Gurvich, V. (2003). Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices. Mathematical Programming, Ser. B, 98(1-3), 14. doi:10.1007/s10107-003-0408-4.

Cite as:
A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G=(V,E) is upper-bounded by δ^p} + 1, where δ is the number of pairs of vertices in V at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an extension of this result for hypergraphs, or more generally for subsets of vectors \cB in a product of n lattices \cL=\cL_1×⋅s×\cL_n, where the notion of an induced matching in G is replaced by a certain mapping of elements of \cB to the nodes of a binary tree \bT in some special way. Precisely, for \cB\subseteq\cL, let γ=γ(\cB) be the number of leaves in the largest tree for which such a mapping exists, denote by \cI(\cB) the set of maximal independent elements of \cB, and let α=|\cI(\cB)| and β=|\cB|. We show that α ≤\max{Q,β^{\log γ/c(2Q,β)}}, where c(ρ,θ) is the unique positive root of the equation 2^c(ρ^{c/\log θ}-1)=1, and Q=\sum_{i=1}^n|\cL_i|. In particular, our bound implies that α ≤ (2Qβ)^{\log γ}. We also give examples of hypergraphs with arbitrarily large n, α and β for which α ≥ β^{(1-o(1)) \log γ/c. As an application, we get an upper bound on the number of maximal infeasible sets for a polymatroid inequality in terms of the number of feasible sets. We further show that such a bound allows for the incrementally efficient generation of all minimal feasible solutions to a given system of polymatroid inequalities f_1(X) ≥ t_1,\ldots,f_m(X) ≥q t_m with quasi-polynomially bounded right hand sides t_1,\ldots,t_m.