Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt





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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

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.

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.