de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

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

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

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: http://hdl.handle.net/11858/00-001M-0000-0019-EC03-B
Abstract
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.