Help Privacy Policy Disclaimer
  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;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
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: https://hdl.handle.net/11858/00-001M-0000-0019-EC03-B
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.