hide
Free keywords:
-
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.
