BRICS RS-02-15 J. M. Nielsen: On the Number of Maximal Independent Sets in a Graph BRICS

Basic Research in Computer Science

On the Number of Maximal Independent Sets in a Graph

Jesper Makholm Nielsen BRICS Report Series RS-02-15 ISSN 0909-0878 April 2002 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2002, Jesper Makholm Nielsen.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/02/15/

On the Number of Maximal Independent Sets in a Graph

Jesper Makholm Nielsen

BRICS^{∗}

Department of Computer Science University of Aarhus

                   jespermn@brics.dk

April, 2002

Abstract

We show that the number of maximal independent sets of size exactly k in any graph of size n is at most ⌊n/k⌋^{k−(n mod k)}(⌊n/k⌋+ 1)^{n mod k}. For maximal independent sets of size at most k the same bound holds for k ≤ n/3. For k > n/3 a bound of approximately 3^{n/3} is given. All the bounds are exactly tight and improve Eppstein (2001) who give the bound 3^{4k−n}4^{n−3k} on the number of maximal independent sets of size at most k, which is the same for n/4 ≤ k ≤ n/3, but larger otherwise. We give an algorithm listing the maximal independent sets in a graph in time proportional to these bounds (ignoring a polynomial factor), and we use this algorithm to construct algorithms for 4- and 5- colouring running in time O(1.7504^{n}) and O(2.1593^{n}), respectively.

1 Introduction

In their 1965 paper Moon and Moser [6] show that the number of maximal independent sets in any graph is at most 3^{n/3} where n is the number of vertices in the graph. They use a carefully designed transformation on the extremal graphs to fully characterise these. Croitoru [1] uses the same technique to show that all graphs with independence number (the size of the largest independent set) no larger than k have at most ⌊n/k⌋^{k−(n mod k)}(⌊n/k⌋ + 1)^{n mod k} maximal independent sets.

∗ Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.

Eppstein [3] uses an algorithmic proof to show that the number of maximal independent sets of size at most k is no larger than 3^{4k−n}4^{n−3k}. His bound is both tight and equal to that of Croitoru for n/4 ≤ k ≤ n/3. Eppstein advocates the search for a tight bound, for all values of k.

In this paper we give such a tight bound for all values of k. This bound equals the bound of Croitoru without the restriction on the independence number. In the proof we use the same technique as Croitoru and Moon and Moser do, but we furthermore give an algorithmic proof similar to that of Eppstein, to show that the maximal independent sets can be listed with only polynomial overhead.

Eppstein uses his bound to improve the time bound for colouring graphs. Although we do not improve this time bound, our result is used to give better time bounds for 4- and 5-colouring than what was previously known.

2 Preliminaries

The graphs in this paper are all simple, undirected graphs G = (V, E). By “subgraphs” we mean vertex-induced subgraphs, and the subgraph induced by a subset of the vertices S ⊆ V is denoted G[S]. An edge (v, w) is adjacent to a vertex v′, if v′ equals v or w. The neighbourhood of a vertex is N (v) = {w ∈ V | (v, w) ∈ E}, and the neighbourhood of a set of vertices is the union of their neighbourhoods. Two vertices v and w are neighbours, if (v, w) ∈ E, or equivalently if w ∈ N (v). For neighbours v and w we let G_{v→w} denote the graph obtained from G by removing all edges adjacent to v, except (v, w), and adding edges from v to all neighbours of w except for v itself. Note that G_{v→w} is equal to the graph obtained by removing v from G, making a copy of w with the same neighbours as w and adding an edge between them.

A maximal independent set in a graph is an independent set contained in no other independent set in the graph. Let I^{=k} (G) (I^{≤k} (G)) denote the number of maximal independent sets of size exactly (at most) k in G. Similarly let I_{G}^{=k} (x) (I_{G}^{≤k} (x)) denote the number of maximal independent sets of size exactly (at most) k in G that contains x. Also let I^{=k} (n) (I^{≤k} (n)) denote the maximum number of maximal independent sets of size exactly (at most) k in any n-vertex graph.

In the rest of the paper, when we talk about the time complexity of an algorithm we will ignore polynomial factors, as all time complexities are exponential. We will use the notation O^{∗} (c^{n}) to denote a function within a polynomial factor of c^{n}.

3 Results

Theorem 1. Let 1 ≤ k ≤ n. If k ≤ n/3, then

I^{≤k} (n) = ⌊n/k⌋^{k−(n mod k)} (⌊n/k⌋ + 1)^{n mod k} .

If k > n/3, then

I^{≤k} (n) = \begin{cases}3^{n/3} & if n ≡ 0 (mod 3), \\ 4 · 3^{⌊n/3⌋−1} & if n ≡ 1 (mod 3), \\ 2 · 3^{⌊n/3⌋} & if n ≡ 2 (mod 3). \end{cases}

Moreover, there is an algorithm that takes a graph as input and outputs all maximal independent sets of size at most k in time O^{∗} (I^{≤k} (n)).

Theorem 2. Let 1 ≤ k ≤ n. Then

I^{=k} (n) = ⌊n/k⌋^{k−(n mod k)} (⌊n/k⌋ + 1)^{n mod k} .

Moreover, there is an algorithm that takes a graph as input and outputs all maximal independent sets of size exactly k in time O^{∗} (I^{=k} (n)).

Remark. The time needed to output all maximal independent sets is bounded by the maximum number of these in any n-vertex graphs, not the actual number in the graph given as input.

The proof of the bounds in the two theorems is essentially the same as that used by Moon and Moser [6].

Proof of Theorem 1 and 2. Let v and w be neighbours in a graph G, and look at the number of maximal independent sets of size at most k in G_{v→w}. None of these contain both v and w, since they are neighbours. All maximal independent sets of size at most k in G that neither contains v nor w are still maximal independent sets in G_{v→w}, since if v or w could be added in G_{v→w} so could w in G. Those maximal independent sets containing w also remains maximal in G_{v→w}, and in addition we get a new maximal independent set in G_{v→w}, with v replacing w. The maximal independent sets containing v are no longer maximal in G_{v→w}, except for those that are maximal independent sets in G[V \ {v}] when v is removed from them. Let M(v) denote the number of these. Thus I^{≤k} (G_{v→w}) = I^{≤k} (G) + I_{G}^{≤k} (w) − I_{G}^{≤k} (v) + M(v), and by the same argument I^{≤k} (G_{w→v}) = I^{≤k} (G) + I_{G}^{≤k} (v) − I_{G}^{≤k} (w) + M(w). Suppose G has the maximum number of maximal independent sets of size at most k among all graphs with n vertices. If v and w are neighbours in G, neither G_{v→w} nor G_{w→v} can have more maximal independent sets than G, but then I_{G}^{≤k} (v) = I_{G}^{≤k} (w) and M(v) = M(w) = 0 by the above equations. This implies that we can replace G by G_{v→w} for all neighbours v and w in G without changing I^{≤k} (G). Let w ∈ V and N (w) = {v_{1}, v_{2}, …, v_{k}}. By successively replacing G by G_{v_{i}→w} we end up with {w, v_{1}, v_{2}, …, v_{k}} being a connected component of the graph forming a clique. Doing this for all connected components we end up with a graph consisting of disconnected cliques. Let the number of vertices in these cliques be i_{1}, i_{2}, …, i_{l}, where i_{1} + i_{2} + ⋯ + i_{l} = n. Then the number of maximal independent sets of size at most k in G is

I^{≤k} (G) = \begin{cases}i_{1} · i_{2} · · · · · i_{l} & if l ≤ k, \\ 0 & otherwise. \end{cases}  (1)

We want to find those values of i_{j} maximising this expression.^{1} It is clear that none of the i_{j}’s can differ by more than one, since if a > b + 1, (a − 1)(b + 1) = ab + (a − b − 1) > ab. Also since a ≤ ⌊a/2⌋ · ⌈a/2⌉ for a ≥ 4, if l < k any i_{j} ≥ 4 can be split in two, namely ⌊i_{j}/2⌋ · ⌈i_{j}/2⌉ without lowering the value of the expression. Thus for k ≤ n/3 this is largest, if (k − (n mod k)) of the i_{j}’s are ⌊n/k⌋ and (n mod k) of them are ⌊n/k⌋ + 1, giving I^{≤k} (G) = ⌊n/k⌋^{k−(n mod k)}(⌊n/k⌋ + 1)^{n mod k}. For k > n/3, since 2^{3} < 3^{2} three two’s are replaced by two three’s. Thus the maximum is 3^{n/3}, if n ≡ 0 (mod 3), 4 · 3^{⌊n/3⌋−1}, if n ≡ 1 (mod 3) and 2 · 3^{⌊n/3⌋}, if n ≡ 2 (mod 3). As we started out from a graph with the maximum number of maximal independent sets this is an upper bound on I^{≤k} (n), and since we explicitly found the extremal graphs this is also a lower bound obtained for the graphs consisting of a union of (k − (n mod k)) K_{⌊n/k⌋}’s and (n mod k) K_{⌊n/k⌋+1}’s, for k ≤ n/3 and an appropriate number of K_{2} and K_{3}’s, for k > n/3.^{2} For I^{=k} (G) a similar expression to (1), except that there must be exactly k i_{j}’s, is found, and therefore the bound I^{=k} (G) = ⌊n/k⌋^{k−(n mod k)}(⌊n/k⌋ + 1)^{n mod k} is valid for all k ≥ 1.

1Moon and Moser [6] gave the above proof with I^{≤k} replaced by the total number of maximal independent sets, and thus got the upper bound 3^{n/3}.

2These graphs are the complement of the Turán graphs.

Remark. The extremal graphs are unique, as already Moon and Moser [6] noted using the following proof. Look at the second-to-last graph G in the above procedure s.t. G_{v→w} is the last. Then v and w must be neighbours, and G consists of v and a bunch of disconnected cliques. Now v is connected to all vertices in w’s component; otherwise, the maximal independent set consisting of v, a vertex from w’s component, except for w itself and a maximal independent set of the remaining graph is still a maximal independent set in G[V \ {v}] with v removed, contradicting M(v) = 0. Since I_{G}^{≤k} (v) = I_{G}^{≤k} (w), v is connected to no other vertices. But then G = G_{v→w}, and since the process started out with any extremal graph, these are unique.

Proof (continued). We now devise an algorithm for finding all maximal independent sets of size exactly k. Suppose a graph G = (V, E) has a maximal independent set I of size k. By maximality I ∪ N (I) = V; thus, I must have a vertex say v of degree ≥ ⌈n/k⌉ − 1. All maximal independent sets in G either consists of v and a maximal independent set in G [V \ ({v} ∪ N (v))], or a maximal independent set in G[V \ {v}] that intersects N (v). Our algorithm chooses the vertex with the highest degree and branches on the two cases of either including it in the maximal independent set, and removing it from the graph together with all its neighbours, or excluding it from the maximal independent set, and removing it from the graph. If k = n the algorithm just tests whether the remaining vertices form an independent set, and if k = 0, or k > n there are no appropriate maximal independent sets, and the branching stops. Let T (n, k) denote the maximum number of leaves in the recursion tree of the algorithm when finding all maximal independent sets of size exactly k in a graph with n vertices. We want to show that T (n, k) ≤ ⌊n/k⌋^{k−(n mod k)} (⌊n/k⌋ + 1)^{n mod k}. For k = 1 and k = n this is trivially so. We proceed by induction in k. Let 1 < k < n and suppose it holds for all smaller values of k. Then by the above discussion

T (n, k) ≤ T (n − ⌈n/k⌉, k − 1) + T (n − 1, k)

which by induction hypothesis is at most

⌊\frac{n − ⌈n/k⌉}{k − 1}⌋^{k−1−((n−⌈n/k⌉) mod (k−1))} (⌊\frac{n − ⌈n/k⌉}{k − 1}⌋ + 1)^{(n−⌈n/k⌉) mod (k−1)}

+ ⌊\frac{n − 1}{k}⌋^{k−((n−1) mod k)} (⌊\frac{n − 1}{k}⌋ + 1)^{(n−1) mod k} .

Using the fact that

n − ⌈n/k⌉ = \begin{cases}(k − 1)⌊n/k⌋ & if k | n, \\ (k − 1)⌊n/k⌋ + (n mod k) − 1 & if k ∤ n, \end{cases}

we get that, if k | n, T (n, k) is at most

⌊\frac{n}{k}⌋^{k−1} (⌊\frac{n}{k}⌋ + 1)^{0} + (⌊\frac{n}{k}⌋ − 1)^{1} ⌊\frac{n}{k}⌋^{k−1}

which is equal to I^{=k} (n), and if k ∤ n, T (n, k) is at most

⌊\frac{n}{k}⌋^{k−(n mod k)} (⌊\frac{n}{k}⌋ + 1)^{(n mod k)−1}

+ ⌊\frac{n}{k}⌋^{k−(n mod k)+1} (⌊\frac{n}{k}⌋ + 1)^{(n mod k)−1}

which again equals I^{=k} (n). Since the algorithm at every step takes at most polynomial time the total running time of the algorithm is O^{∗} (I^{=k} (n)).

Next we devise an algorithm for finding all maximal independent sets of size at most k rather than exactly k. If the maximum degree in the graph is at most two the graph consists of only paths and cycles. For each of these we can calculate all possible sizes of maximal independent sets. The algorithm branches as before on the cases of including or excluding a vertex, but keeps track of the possible sizes of maximal independent sets in the remaining graph, such that it only makes recursive calls that will find maximal independent sets. Then every leaf in the recursion tree corresponds to a maximal independent set of size at most k in the graph, and the running time is thus proportional to I^{≤k} (n).

If the maximum degree is larger than two an algorithm similar to the one for maximal independent sets of size exactly k is used, the only difference being that it no longer stops if k ≥ n, since we are looking for maximal independent sets of size at most k. We now prove by induction in k that the number of leaves in the recursion tree T (n, k) is at most I^{≤k} (n). For n = 1 and k = 1 this is trivially so. We want to show it for 1 < k ≤ n, so suppose it is true for all smaller values of k. If k < n/3 then k ≤ (n−1)/3 and the proof is similar to that for I^{=k} (n). If k = n/3 then

T (n, k) ≤ 3^{(n−3)/3} + 2 · 3^{⌊(n−1)/3⌋} = 3^{n/3}

which is equal to I^{≤k} (n). For k > n/3, if the maximum degree is at most two the running time is proportional to I^{≤k} (n) by the above. Suppose that the maximum degree is at least three. Then

T (n, k) ≤ T (n − 4, k − 1) + T (n − 1, k)

which is at most

2 · 3^{⌊(n−4)/3⌋} + 2 · 3^{⌊(n−1)/3⌋} = 8/9 · 3^{n/3}

if n ≡ 0 (mod 3),

3^{(n−4)/3} + 3^{(n−1)/3} = 4 · 3^{⌊n/3⌋−1}

if n ≡ 1 (mod 3) and

4 · 3^{⌊(n−4)/3⌋−1} + 4 · 3^{⌊(n−1)/3⌋−1} = 16/9 · 3^{⌊n/3⌋}

if n ≡ 2 (mod 3). In all cases this is at most I^{≤k} (n); thus, the algorithm runs in time O^{∗} (I^{≤k} (n)).

Hujter and Tuza [4] have shown that triangle-free graphs (i.e. graphs having no triangles as subgraphs) can have at most 2^{n/2} maximal independent sets. This we can show by an algorithmic proof similar to the above.

Proposition 1. If G is a triangle-free graph the number of maximal independent sets in G is at most 2^{n/2}, and the bound is tight. Moreover, there is an algorithm that takes a triangle-free graph as input and outputs all maximal independent sets in the graph in time O^{∗} (2^{n/2}).

Proof. Let G be a triangle-free graph. As long as the maximum degree of the graph is greater than two, we just branch on the maximum-degree vertex. Either it is in the maximal independent set, and thus none of it neighbours are, or it is not. This removes at least four vertices in one branch and one in the other; thus, the number of leaves in the recursion tree is at most T (n) ≤ T (n − 1) + T (n − 4), which has the solution T (n) = 2^{0.4650·n}. If at some point the maximum degree is at most two the remaining graph consists of only paths and cycles. Since there are no triangles the worst case is paths of length two, yielding 2^{n/2} maximal independent sets, which is worse than the above. The bound is tight since a graph consisting of n/2 disconnected K_{2}’s achieves the bound for even n.

4 Application to colouring

Consider a k-colouring of a graph. Each colour class is an independent set, and the largest has size at least n/k and can be extended to a maximal independent set. Thus to check whether a graph is k-colourable it suffices to check for all maximal independent sets of size at least n/k, whether the remaining graph is (k − 1)-colourable, which can be done by applying the method recursively and using a polynomial time algorithm for checking 2-colourability. For checking 3-colourability, Eppstein [2] has devised an algorithm running in time T_{3}(n) = O (1.3289^{n}) which is faster than the above. Using his algorithm for checking 3-colourability we get the following running times for 4- and 5-colourability.

Theorem 3. It can be checked in time O (1.7504^{n}), whether a graph is 4-colourable.

Proof. The running time of the above-mentioned algorithm is at most

∑_{k=⌈ \frac{n}{4} ⌉}^{n} I^{=k} (G) · T_{3}(n − k).

By Eppstein [3], 3^{4k−n}4^{n−3k} is an upper bound on the number of maximal independent sets for all k, and they can be generated in this time. Thus the sum is at most

∑_{k=⌈ \frac{n}{4} ⌉}^{n} 3^{4k−n}4^{n−3k} · T_{3}(n − k).

As the terms are decreasing as a function of k, this is at most

n · 4^{n/4} · T_{3}(3n/4).

Thus the algorithm runs in time O (1.7504^{n}), where we have dropped the factor of n since we have rounded up.

Theorem 4. It can be checked in time O (2.1593^{n}), whether a graph is 5-colourable.

Proof. Let T_{4} denote the running time of the above algorithm for checking 4-colourability. The running time for checking 5-colourability is at most

∑_{k=⌈ \frac{n}{5} ⌉}^{n} I^{=k} (G) · T_{4}(n − k)

which is no larger than

∑_{k=⌈ \frac{n}{5} ⌉}^{⌊ \frac{n}{4} ⌋} 4^{5k−n}5^{n−4k} · T_{4}(n − k) + ∑_{k=⌈ \frac{n}{4} ⌉}^{n} 3^{4k−n}4^{n−3k} · T_{4}(n − k).

Since the terms in both sums are decreasing as functions of k, and the largest is the first term in the first sum, this is at most

n · 5^{n/5} · T_{4}(4n/5),

which is equal to

n^{2} · 20^{n/5} · T_{3}(3n/5).

Thus the algorithm runs in time O (2.1593^{n}).

5 Conclusion

In this paper we give new bounds on the number of maximal independent sets of size k, and thus strengthening Eppstein’s [3] bound to be tight for all values of k. Eppstein uses his bound to prove better time bounds for colouring graphs with the minimum possible number of colours, but for our result to improve this, 4-colouring algorithms running in time o(1.4150^{n}) are needed (see [3]), which is far from the running time of O (1.7504^{n}) proven in this paper.

Our result is algorithmic in the sense that all maximal independent sets of size at most k can be listed, but only in time proportional to our bound, not their actual number. Algorithms for generating all maximal independent sets running in time proportional to their number exists; Johnson et al. [5] give an algorithm that in fact outputs all maximal independent sets with only polynomial delay. We would like to find such an algorithm for maximal independent sets of size k.

Our result gives no information about the distribution of sizes of maximal independent sets. It does not tell whether the existence of many maximal independent sets of one size limits the number of maximal independent sets of another size. Such bounds would be an interesting goal of further research.

Acknowledgements

I would like to thank my advisor, Peter Bro Miltersen, for many helpful comments and insights and also Bjarke Skjernaa for comments on and corrections to this paper.

References

[1] Cornelius Croitoru. On stables in graphs. In Proc. 3rd Coll. Operations Research (Cluj-Napoca, 1978), pages 55–60. Univ. “Babeş-Bolyai”, Cluj-Napoca, 1979.

[2] David Eppstein. Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In Proc. 12th Symp. Discrete Algorithms, pages 329–337. ACM and SIAM, 2001.

[3] David Eppstein. Small maximal independent sets and faster exact graph coloring. In Proc. 7th Worksh. Algorithms and Data Structures, volume 2125 of Lecture Notes in Computer Science, pages 462–470. Springer-Verlag, 2001.

[4] Mihály Hujter and Zsolt Tuza. The number of maximal independent sets in triangle-free graphs. SIAM Journal on Discrete Mathematics, 6(2):284–288, 1993.

[5] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123, 1988.

[6] J. W. Moon and L. Moser. On cliques in graphs. Israel Journal of Mathematics, 3:23–28, 1965.

Recent BRICS Report Series Publications

RS-02-15 Jesper Makholm Nielsen. On the Number of Maximal Independent Sets in a Graph. April 2002. 10 pp.

RS-02-14 Ulrich Berger and Paulo B. Oliva. Modified Bar Recursion. April 2002. 22 pp.

RS-02-13 Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin, and Christian N.S̃. Pedersen. Solving the String Statistics Problem in Time O(n log n). March 2002. To appear in ICALP ’02.

RS-02-12 Olivier Danvy and Mayer Goldberg. There and Back Again. March 2002. This report supersedes the earlier report BRICS RS-01-39.

RS-02-11 Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Extending Java for High-Level Web Service Construction. March 2002.

RS-02-10 Ulrich Kohlenbach. Uniform Asymptotic Regularity for Mann Iterates. March 2002. 17 pp.

RS-02-9 Anna Östlin and Rasmus Pagh. One-Probe Search. February 2002. 17 pp.

RS-02-8 Ronald Cramer and Serge Fehr. Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups. February 2002. 19 pp.

RS-02-7 Anna Ingólfsdóttir, Anders Lyhne Christensen, Jens Alsted Hansen, Jacob Johnsen, John Knudsen, and Jacob Illum Rasmussen. A Formalization of Linkage Analysis. February 2002. vi+109 pp.

RS-02-6 Luca Aceto, Zoltán Ésik, and Anna Ingólfsdóttir. Equational Axioms for Probabilistic Bisimilarity (Preliminary Report). February 2002. 22 pp.

RS-02-5 Federico Crazzolara and Glynn Winskel. Composing Strand Spaces. February 2002. 30 pp.

RS-02-4 Olivier Danvy and Lasse R. Nielsen. Syntactic Theories in Practice. January 2002. 34 pp. This revised report supersedes the earlier BRICS report RS-01-31.

RS-02-3 Olivier Danvy and Lasse R. Nielsen. On One-Pass CPS Transformations. January 2002. 18 pp.