Maximum r-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds

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(cⁿ), 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 O(cⁿ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 ⊆ V , such that the induced subgraph on R is r-regular. As a by-product of the enumeration algorithm, we get a O(cⁿ) 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.