Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2014) | last year (2013) | two years ago (2012) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Boros, Endre Elbassioni, Khaled M. Khachiyan, Leonid Gurvich, Vladimir dblp dblp dblp dblp Not MPG Author(s): Boros, Endre Gurvich, Vladimir Khachiyan, Leonid
 BibTeX cite key*: Elbassioni2003b

 Title
 Title*: Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices

 Journal
 Journal Title*: Mathematical Programming, Ser. B Journal's URL: Download URL for the article: Language: English

 Publisher
 Publisher's Name: Springer Publisher's URL: Publisher's Address: ISSN:

 Vol, No, pp, Date
 Volume*: 98 Number: 1-3 Publishing Date: 2003 Pages*: 14 Number of VG Pages: Page Start: 355 Page End: 368 Sequence Number: DOI:

 Note: (LaTeX) 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 $\delta^{p} + 1$, where $\delta$ 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\times\cdots\times\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 $\gamma=\gamma(\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 $\alpha=|\cI(\cB)|$ and $\beta=|\cB|$. We show that $\alpha \le\max\{Q,\beta^{\log \gamma/c(2Q,\beta)}\}$, where $c(\rho,\theta)$ is the unique positive root of the equation $2^c(\rho^{c/\log \theta}-1)=1$, and $Q=\sum_{i=1}^n|\cL_i|$. In particular, our bound implies that $\alpha \le (2Q\beta)^{\log \gamma}$. We also give examples of hypergraphs with arbitrarily large $n$, $\alpha$ and $\beta$ for which $\alpha \ge \beta^{(1-o(1)) \log \gamma/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) \ge t_1,\ldots,f_m(X) \geq t_m$ with quasi-polynomially bounded right hand sides $t_1,\ldots,t_m$. URL for the Abstract: Categories, Keywords: Hypergraphs, lattices, polymatroid functions, enumeration algorithms HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Intranet

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Elbassioni2003b,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
TITLE = {Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices},
JOURNAL = {Mathematical Programming, Ser. B},
PUBLISHER = {Springer},
YEAR = {2003},
NUMBER = {1-3},
VOLUME = {98},
PAGES = {14},
}