Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
复制标题
将图中最大独立集数量的 Balas-Yu 界限扩展到超图和格
DOI：
10.1007/s10107-003-0408-4
复制
发表时间：
2003
影响因子：
2.7
通讯作者：
L. Khachiyan
中科院分区：
文献类型：
--
作者：
E. Boros;Khaled M. Elbassioni;V. Gurvich;L. Khachiyan
Balas和Yu(1989)的一个结果指出，图G的极大独立集的个数至多为δp+1，其中δ是Gat距离为2的顶点对的个数，p是最大诱导匹配环的基数。在这篇文章中，我们给出了超图的这一结果的一个类似结果，更一般地，对于向量的子集ℬ在格ℒ=ℒ1×⋯×ℒn的乘积中，其中诱导匹配ℬ的概念被一种二叉树代替，它的每个内部节点被映射到ING。我们证明了对于任意大的超图和格，我们的界可能几乎是尖锐的。作为应用，我们证明了多项式不等式组的最大不可行向量xℒ=ℒ1×⋯×ℒN不超过max{q，βlogt/c(2q，β)}，其中β是系统的最小可行向量数，c(ρ，β)是方程2c(ρc/LOGβ−1)=1的唯一正根。对于布尔情形ℒ={0，1}n，这个界几乎是尖锐的，并且它允许有效地生成给定的具有拟多项式有界的右端有界的多项式不等式组的所有最小可行集。
A result of Balas and Yu (1989) states that the number of maximal independent sets of a graphGis at most δp+1, where δ is the number of pairs of vertices inGat distance 2, andpis the cardinality of a maximum induced matching inG. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors ℬ in the product ofnlattices ℒ=ℒ1×⋯×ℒn, where the notion of an induced matching inGis 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 vectorsxℒ=ℒ1×⋯×ℒnfor a system of polymatroid inequalitiesdoes not exceed max{Q,βlogt/c(2Q,β)}, where β is the number of minimal feasible vectors for the system,,, andc(ρ,β) 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.