Independent Set Algorithms: Improved performance and improved analysis Preliminary Report

J.M. Robson LaBRI Université Bordeaux 1

1 Introduction

We are interested in algorithms with provable upper bounds for finding a maximum independent set of a graph. This is a maximum clique of the complementary graph or the complement of a minimum vertex cover of the original graph. We prefer to talk about independent sets rather than cliques, simply because in the interesting cases for our algorithms the graph is much sparser than its complement.

[2] showed an algorithm running in time O(2^{n/3}) where n is the size of the graph and finding the size of a maximum independent set. Given an algorithm for the size, one to find an example set of this size multiplies the time by only a polynomial in n. [1] described some minor modifications which reduced the constant c in the O(2^{cn}) time bound to about 0.276. In this paper we take this work a little further describing two modifications which reduce c to about 0.272. We discuss two further modifications (one to the algorithm and one to its analysis) which are, we believe, capable of reducing c to about 0.266. These last two modifications need further work to prove that they are valid and have the effect predicted.

1.1 Terminology and notation

We will abbreviate “maximum independent set” by “m.i.s.”.

If G = (V, E) is a graph and v a vertex of G, we write N(v) for the neighbourhood of v, namely {u ∈ V | (u, v) ∈ E} and N̄(v) for v + N(v). If X ⊂ V, we write G − X for the graph induced on V − X. d(v) is the degree of v in the graph currently under consideration.

2 Outline of the algorithm

We give here a very brief description of the algorithm in [1] which should be enough to make it possible to follow the suggested improvements.

2.1 Recursive structure

The algorithm returns the size of an m.i.s. of graph G by choosing a vertex A of G examining the structure of the graph around A and making recursive calls corresponding to a choice to include or exclude various vertices around A in the independent set. The result is obtained by maximising over an exhaustive set of apparently plausible choices of the value of the recursive call plus the number of vertices included in the independent set. The analysis inductively proves that the number of calls from a graph G is at most k_{G}2^{c|G|} where k_{G} depends on the local structure found. For many cases the choice of A is simply to minimize d(A) and maximize the degree of some neighbour B of A.

2.2 Dominance

One special case occurs when a vertex B is adjacent both to A and to all neighbours of A; in this case it is clear that an independent set containing B can be modified to one of the same size containing A and so B can be deleted from the graph, that is ms(G) = ms(G − B).

It will be useful to exploit this idea in the case of subdominance. If B is adjacent to A and all neighbours of A except one (C), then in a recursive call on the graph G − C, A does dominate B.

Another case similar to dominance concerns the existence of twins, that is pairs of vertices which are not connected but have exactly the same set of neighbours. In this case any m.i.s. contains both the twins or neither.

2.3 Connected non-regular graphs

If a graph is not connected, we simply call the function on each of its connected components. It can be argued that connected regular graphs occur rarely enough to be irrelevant to the asymptotic analysis so we will always assume that G is not regular. In particular the choice of A described above will always be assumed to yield a neighbour B with d(B) > d(A).

2.4 Special algorithms when the m.i.s. must contain a specified number of elements of a subset

We will use auxiliary functions ms^{1} and ms^{2} such that ms^{i}(G, G′) lies in the range between the largest m.i.s. of G containing at least i elements of G′ and the unconstrained largest m.i.s. [1] used ms^{1} only in the case that G′ contained exactly 2 elements; we will also need to consider cases with |G′| = 3. ms^{1} and ms^{2} are defined mutually recursively with ms and bounds on their run time are proved similarly to those on that of ms and by a process of mutual induction.

3 A simple improvement

3.1 The local structure

In the case of minimum degree 4, 5 or 6, the algorithm chooses a vertex A of minimum degree i and a neighbour B of A of maximum degree j > i. Since A does not dominate B, there is another neighbour B′ of A which is not a neighbour of B. We write j′ for the degree of B′. By the choice of A and B, we have i ≤ j′ ≤ j. The most interesting case is when j = i + 1 since this gives the worst case of the algorithm; in this case j′ has only two possible values. The algorithm proceeds by two recursive calls on the graphs G − B and G − N̄(B). In the first, we know that there is a vertex (A) of degree i − 1; in the second we have no special information to constrain the time.

3.2 Improvements depending on j′

If j′ = i, the recursive call on G − N̄(B) has a vertex (B′) of degree ≤ i − 1, a fact which reduces our upper bound on its time. But if j′ > i, the recursive call on G − B has a vertex of degree j′ adjacent to the vertex A of minimum degree, again reducing our bound. So we obtain a better upper bound for these cases by taking the maximum over all possible j′ of the sum of the bounds on these two recursive calls.

3.3 Analysis

For all i, j such that 4 ≤ i < j ≤ 8, we define a constant k_{i,j} such that we can prove inductively that when we choose vertices A and B with degrees i and j, the run time is bounded by k_{i,j}2^{cn} provided it is bounded by 2^{cn} in those recursive calls with minimum degree greater than 8. We also slightly improve the analysis in some cases of the neighbourhood of a vertex of degree 2. A simple calculation now gives the optimum values of the k_{i,j} for a given c. The table shows the k_{i,j} found for c = 0.293 . Since all k_{i,j} ≤ 1, we deduce that the algorithm runs in time O(2^{0.293n}).

\begin{matrix}i & j & k_{i,j} \\ 4 & 5 & 0.932995 \\ 4 & 6 & 0.895246 \\ 4 & 7 & 0.854043 \\ 4 & 8 & 0.817854 \\ 5 & 6 & 0.986661 \\ 5 & 7 & 0.945280 \\ 5 & 8 & 0.911504 \\ 6 & 7 & 0.999652 \\ 6 & 8 & 0.963933 \\ 7 & 8 & 0.976625 \end{matrix}

The time-space trade-off described in [1] then achieves a reduction to O(2^{0.273n})

4 Avoiding the worst case

4.1 The worst case

We now observe that the worst case of the algorithm (more precisely of our upper bound) comes when a vertex A of degree 6 has a neighbour B of degree 7 such that every vertex in N(A) − N(B) has degree 6 and in the subsequent recursive call on G − B, (where A is still the vertex of minimum degree), A has no neighbour of degree > 6 nor two non-adjacent neighbours each of degree 6. We will now show that if this would occur for every possible choice of A and B, we can always improve the performance of the algorithm.

4.2 Three conditions necessary for the worst case

First we show that if the basic algorithm will produce the worst case behaviour for every possible choice of A and B, one of three patterns must occur in the induced subgraph on N(A):

• a vertex v has degree ≥ 4,

• three vertices v_{1}, v_{2}, v_{3} form a triangle,

• or the vertex B of degree 7 (in the original G) is adjacent to three vertices v_{1}, v_{2}, v_{3} which have no edges between them and the remaining vertices v_{4}, v_{5} are not adjacent to B but do have an edge between them. moreover, v_{1} is adjacent (in G) to a vertex of degree 6 which is not v_{4} or v_{5}.

Proof: Suppose that the worst case does occur and that neither of conditions (a) or (b) holds. For the worst case to occur in G − B, A must not have two neighbours of degree 6 in G − B which are not adjacent. So any two neighbours of A (in G) with degree 7 must be adjacent and any pair of vertices in N(A) − N(B) must be connected. Thus, if any vertex of degree 7 has three non-neighbours, there is a triangle. If there are two vertices B_{1} and B_{2} of degree 7, no other vertex can be adjacent to both and there can be at most two vertices not adjacent to B_{i} since otherwise any three would form a triangle; so we must have two vertices adjacent to B_{1} but not to B_{2}. But then these two vertices together with B_{2} form a triangle. We conclude that there is a single vertex B of degree 7. We know that B cannot have three non-neighbours and it cannot have four neighbours; the only remaining possibility is that it has three neighbours and two non-neighbours. since its non-neighbours must be connected and its neighbours cannot form a triangle with it, we conclude that the induced graph must be as stated in condition (c). Finally if v_{1} is one of the neighbours of B, it has degree 6 and has a neighbour of degree 7 and so it is a candidate to be chosen as A; if that choice would also give the worst case, then v_{1} similarly has two non-connected neighbours of degree 6; only one of them can be v_{4} or v_{5} since (v_{4}, v_{5}) is an edge and (v_{1}, v_{4}, v_{5}) is not a triangle.

4.3 Improvements for these conditions

Subdominance If v has degree 4 in N(A), there is only one vertex, say u in N(A) − v. In the graph G − u, A dominates v; so we have ms(G) = max(1 + ms(G − N̄(u)), ms(G − u − v)). The two recursive calls are on graphs of sizes ≤ n − 6 and n − 2 giving significantly improved performance.

Triangles If v_{1}, v_{2} and v_{3} form a triangle and the remaining vertices of N(A) are v_{4}, v_{5} and v_{6}, knowing that there is a m.i.s. containing A or one containing two elements of N(A) gives time bound of 1 + max(ms(G − N̄(A)), ms(G − N̄(v_{4})), ms(G − N̄(v_{5}) − v_{4}), ms(G − N̄(v_{6}) − v_{4} − v_{5})) The recursive calls after the first are on graphs of size at most n − 7 which already reduces the upper bound on the time (and a little more detailed analysis would certainly reduce it further).

The special case The argument is similar to the case of a triangle except that in the cases where B or (v_{3} and not v_{1} or v_{2}) are put into the independent set the second element of N(A) to be in the set must be one of v_{4} and v_{5}. The time bound is 1 + max(ms(G − N̄(A)), ms^{1}(G − N̄(B), {v_{4}, v_{5}}), ms(G − N̄(v_{1})), ms(G − N̄(v_{2}) − v_{1}), ms^{1}(G − N̄(v_{3}) − v_{1} − v_{2}), {v_{4}, v_{5}}). Moreover in the three calls of ms (as opposed to ms^{1}), there is always a vertex of degree 5 or less, namely v_{4} or v_{5} or the anonymous vertex adjacent to v_{1} and having degree 6 in G. Hence these three calls have their time bounds reduced.

4.4 Extent of the improvement

Although the improvements described in the previous section are all fairly effective (around 4-5% at least), the improvement in the overall performance of the algorithm is slight because only a minor improvement is obtained in the cases where our conditions do not hold and the recursive call on G − B is not worst case because A has two non connected neighbours of degree 6. Nevertheless the constant c is reduced, to 0.292 or to 0.272 with the time-space trade-off.

5 Small subgraphs

A useful gain in time is obtained at the cost of using exponential space by remembering the result found for any induced subgraph already analysed and avoiding doing the same calculation several times. This gain is evaluated by observing that the number of calls of the algorithm on graphs of size greater than m is O(2^{c(n−m)}) so that if m is chosen so that the number of induced subgraphs of size ≤ m is also O(2^{c(n−m)}) then so is the overall time.

5.1 Connected induced subgraphs

In fact it suffices to consider connected induced subgraphs and to consider graphs with degree bounded by 8 since the performance bounds we will obtain are easily proved recursively for all graphs if they hold for degree ≤ 8 graphs. A bound on the number of small connected induced subgraphs is then obtained by considering the number of 7-ary trees of size m (where a 7-ary tree is either empty or has a root node and 7 subtrees; note that the order of the subtrees is important). Relative to a given root node and an ordering of the edges at each vertex, the tree is interpreted as a spanning tree of the subgraph.

This bound overestimates the number of subgraphs for three reasons:

• Where the tree indicates that an edge is to be followed, the graph may have no edge; this is not significant since we want an upper bound on the number of connected subgraphs and adding more edges can only increase the number.

• An edge may lead to a vertex which has already been visited.

• A connected subgraph may have many spanning trees.

We will estimate the effect that the last two phenomena have on the analysis of the performance of the algorithm.

5.2 Breadth first spanning trees

To obtain a tighter enumeration of the connected subgraphs, we multiply the number of 7-ary trees of size m by the probability that a randomly chosen such tree starting from a given root vertex is actually the breadth first spanning tree of a subgraph. For this to happen it is necessary that in a breadth first traversal of the tree, no edge leads to a vertex (in the graph) adjacent to another vertex visited earlier in the traversal.

5.3 A probabilistic analysis

We will be interested in the probability that an edge from the i-th node of the tree leads (in the graph) to a vertex adjacent to the j-th node (j < i) conditional on the first i − 1 nodes not having violated the breadth first condition. This probability is 1/7 times the probability that node i lies at a distance 2 from j in the graph. Given the length of the path from j to i (in the tree), this is essentially the probability that a random walk on the graph from j of this length which has not passed within distance 1 of j finishes at distance 2 from j; (our random walks may not leave a vertex by the same edge they entered by). We lower bound this by the probability that such a random walk from j arrives at a vertex distant 2 from j in the graph but not the father or a brother or grandson of j in the tree. A random 7-ary tree of size m is obtained by randomly selecting m − 1 links out of 7m to be non empty and then cyclically arranging the m nodes. To sufficient accuracy for our purposes we can ignore the cyclic rearrangement. Thus, again to sufficient accuracy, the i-th edge to a son encountered in the traversal of the tree lies in the i-th node traversed. We assume that the graph has no 4-cycles since it seems clear that a prevalence of short cycles will reduce the probability of a random subset of the vertices being connected.

In the graph there are 56 vertices distant 2 from j and of these on average 1 is a grandson in the tree and there is 6/7 of a brother. Hence there are on average 53 + 1/7 graph vertices at distance 2 from j in the graph but not in the tree. Hence except where the tree distance from j to i is o(n), the probability of failure produced by this pair is at least (53+1/7)/n×1/7. (In the event that the random walk is periodic, we must average over all (i, j) pairs; the conclusion will not be affected.) Multiplying over all pairs now gives a probability of success of e^{−(53+1/7)m^{2}/(14n)+o(n)}.

5.4 The improvement to be expected

This new estimate of the number of connected induced subgraphs raises the balance point from m ≈ 0.0667n to m ≈ 0.0767 reducing the time for the overall algorithm to 2^{0.2705n}.

6 Further work

6.1 A catalogue of neighbourhoods

In the same way that we used in the neighbourhood of a vertex of degree 6, we intend to examine all possible induced subgraphs in the neighbourhood of a vertex A of degree 5 and 4. The number of induced graphs needing to be considered is not as large as it might appear since many graphs can be treated similarly (for instance all graphs containing a triangle, all graphs where A subdominates another vertex). Giving a series of recursive calls tailored to each such graph rather than relying on the step by step analysis currently used seems capable of improving the treatment of every possible neighbourhood. It is likely that minor improvements of this type can reduce the value of c obtainable by the basic algorithm at least as far as c ≈ 0.288 where the inequality 2^{−3c} + 2^{−4c} < 1 ceases to hold and all the analysis of the simple cases needs to be reexamined. With the memorisation improvement (and provided our new analysis of it can be made rigorous), this will give an overall performance of O(2^{0.2661n}).

References

[1] Robson, J. M., Algorithms for maximum independent sets, J. Algorithms 7 (1986), 425-440.

[2] Tarjan, R. E. and Trojanowski, A. E., Finding a maximum independent set, SIAM J. Comput. 6 (1977), 537-546.