MAXIMUM r-REGULAR INDUCED SUBGRAPH PROBLEM: FAST EXPONENTIAL ALGORITHMS AND COMBINATORIAL BOUNDS

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(c(n)), 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 3(n/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 O(c(n)n(O(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 subset of V, such that the induced subgraph on R is r-regular. As a by-product of the enumeration algorithm, we get a O(c(n)) 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 delta-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem.