Back to Search
Start Over
MAXIMUM r-REGULAR INDUCED SUBGRAPH PROBLEM: FAST EXPONENTIAL ALGORITHMS AND COMBINATORIAL BOUNDS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2012, Vol. 26 Issue 4, p1758-1780. 23p. - Publication Year :
- 2012
-
Abstract
- We show that for a fixed r, the number of maximal r-regular induced subgraphs in any graph with n vertices is upper bounded by O(cn), where c is a positive constant strictly less than 2. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of 3n/3 on the number of maximal independent sets of a graph on n vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal r-regular induced subgraphs possible in a graph on n vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal r-regular induced subgraphs in time (cnnO(1)). A related question is that of finding a maximum-sized r-regular induced subgraph. Given a graph G =(V,E) on n vertices, the Maximum r-Regular Induced Subgraph (M-r-RIS) problem asks for a maximum-sized subset of vertices, R ⊆ V, such that the induced subgraph on R is r-regular. As a by-product of the enumeration algorithm, we get a O (cn) time algorithm for this problem for any fixed constant r, where c is a positive constant strictly less than 2. Furthermore, we use the techniques and results obtained in the paper to obtain improved exact algorithms for a special case of the Induced Subgraph Isomorphism problem, namely, the Induced r-Regular Subgraph Isomorphism problem, where r is a constant, the δ-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 26
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 89039514
- Full Text :
- https://doi.org/10.1137/09077850X