Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices |
| |
Authors: | Endre Boros Khaled Elbassioni Vladimir Gurvich Leonid Khachiyan |
| |
Institution: | (1) RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ, 08854-8003;(2) Department of Computer Science, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ, 08854-8003 |
| |
Abstract: | A result of Balas and Yu (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 in the product of n lattices = 1× × 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 . 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 = 1× × n for a system of polymatroid inequalities does not exceed max{Q, logt/c(2Q, )}, where is the number of minimal feasible vectors for the system, , , and c( , ) is the unique positive root of the equation 2c( c/log –1)=1. This bound is nearly sharp for the Boolean case ={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 .
This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000): 20E28, 20G40, 20C20 |
| |
Keywords: | dualization hypergraph incremental algorithm maximal independent set lattice polymatroid function system of polymatroid inequalities proper mapping |
本文献已被 SpringerLink 等数据库收录! |
|