## Abstract

A result of Balas andYu (1989) states that the number of maximal independent sets of a graph G is at most δ^{p} + 1, where δ is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors B in the product of n lattices L = L_{1} ×... × L_{n}, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into B. We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x ⊂ L = L_{1} ×...× L_{n} for a system of polymatroid inequalities f _{1}(x) ≥ t_{1},.., f_{r} (x) ≥ tr does not exceed max{Q, β^{logt/c(2Q,β)}}, where β is the number of minimal feasible vectors for the system, Q = |L_{1}| +.. + |L _{n}|, t = max{t_{1},.., t_{r}}, and c(ρ, β) is the unique positive root of the equation 2^{c}(ρ ^{c/logβ}-1) = 1. This bound is nearly sharp for the Boolean case L = {0, 1}^{n}, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides t_{1},.., t_{r}.

Original language | British English |
---|---|

Pages (from-to) | 355-368 |

Number of pages | 14 |

Journal | Mathematical Programming |

Volume | 98 |

Issue number | 1-3 |

DOIs | |

State | Published - 2003 |

## Keywords

- Dualization
- Hypergraph
- Incremental algorithm
- Lattice
- Maximal independent set
- Polymatroid function
- Proper mapping
- System of polymatroid inequalities