MAXIMUM r-REGULAR INDUCED SUBGRAPH PROBLEM: FAST EXPONENTIAL ALGORITHMS AND COMBINATORIAL BOUNDS - Danish National Research Database-Den Danske Forskningsdatabase

^{1} Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{2} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{3} unknown^{4} Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU

DOI:

10.1137/09077850x

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(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.

Type:

Journal article

Language:

English

Published in:

S I a M Journal on Discrete Mathematics, 2012, Vol 26, Issue 4, p. 1758-1780