On the Effectiveness of Dynamic Programming to Speed up Algorithms Computing the Stability Number of a Graph

J.M. Robson

LaBRI, Université Bordeaux 1, F-33405, Talence France

Abstract

The runtime of straightforward recursive algorithms to compute the stability number of a graph can be improved by a dynamic programming approach which avoids recomputation on small induced subgraphs. The analysis of this improvement depends on the number of such subgraphs which might arise and which require recursive branching. We give lower and upper bounds on the number of these good subgraphs.

On the Effectiveness of Dynamic Programming to Speed up Algorithms Computing the Stability Number of a Graph

On the Effectiveness of Dynamic Programming to Speed up Algorithms Computing the Stability Number of a Graph

1  Introduction

1.1  The problem and history and basic algorithm

We consider the problem of computing the stability number of a graph, that is the size of a maximum independent set. It is well known that the related decision problem is NP-complete and the best known algorithms run in time exponential in n the size of the graph.

Various papers have presented recursive algorithms with proven upper bounds on the worst case behaviour substantially better than the 2n time of the simplistic algorithm which considers all subsets of the vertices. (In all discussion of run times we ignore polynomial factors.) Previously proved bounds have often been expressed as O(2cn), first for c < 1/3 [4] and then c » 0.304 [1] and c » 0.276 [2] and most recently c » 0.265 [3].

Essentially these algorithms explore a tree of possible partially chosen independent sets with, at each node of the tree, a recursive call of the algorithm on an induced subgraph of the original graph. [2] introduced the idea of improving the run time of such algorithms at the expense of using exponential space by dynamic programming or memorisation: if the same induced subgraph turns up more than once (as is bound to happen near the leaves of the tree), the algorithm is not run a second time but the result of the first call is looked up.

To analyse the usefulness of this idea it is convenient to consider a variant of the method which would not be used in practice but gives an upper bound on the time of the practical method: we suppose that the stability number is first calculated for all induced subgraphs in increasing order of size up to a certain size (m) which might be needed (assuming an oracle to generate them) and the normal recursive algorithm is then run with the difference that whenever a call occurs on a graph of order m or less the result is looked up. The size m is chosen so as to balance the time spent on the precomputation and (the upper bound on) the recursive computation. So the analysis depends critically on the number of subgraphs to be considered as a function of m. This paper investigates the maximum possible value of this number.

Following sections will define precisely which subgraphs need to be considered and give upper and lower bounds on their number in the worst case.

1.2  Which subgraphs need to be considered?

1.2.1  Connected

A first simple observation made in [2] is that we need only precompute the stability number of connected induced subgraphs. This is because the stability number of a general graph is the sum of those of all its connected components and looking up these component stability numbers and adding them takes polynomial bounded time.

1.2.2  Bounded degree

Next we observe that the bound claimed for the algorithms follows easily by induction for graphs having a vertex of high degree (typically at least 8 or 9) without using dynamic programming. So we are only interested in the number of subgraphs when the basic graph G has degree bounded by a constant d and our bounds will be esentially functions of m and d multiplied by a polynomial in n.

1.2.3  Without degree 1 vertices

Another simple observation is that when there exists a vertex v of degree 1, the stability number is found without branching by adding 1 to that of G¢ where G¢ is formed from G by removing v and its neighbour. Repeating this as often as possible gives us a polynomial computation of the stability number without precomputation on subgraphs having a vertex of degree 1.

1.3  Statement of Problem and summary of results

So our problem becomes: Given a graph G of order n and maximum degree at most d and an integer m < n, how many induced connected subgraphs can G possess having order at most m and no vertex of degree 1? From now on we will refer to these subgraphs as good.

We will give upper bounds of the form cm poly(n). The case that interests us is where d=9 and m » n/16 and we will use the numerical values of c in this case to compare our bounds. We give a lower bound which is also approximately of the form cm for a fixed ratio m/n so that we can make a similar numerical comparison.

2  Upper Bounds

A simple upper bound is given by considering all subsets of at most m vertices. Up to a polynomial factor this gives a bound of (
n
m
) or numerically 42.126059m for our example case of d=9 and m = n/16.

2.1  Using Connectivity

To restrict the subgraphs counted to connected ones, we consider spanning trees. By choosing a root whose degree in the subgraph is less than d, we can find a spanning tree in which each node has out degree less than d. Accordingly we define (d-1)-trees in the same way as binary trees; a (d-1)-tree is empty or consists of a root and (d-1) sub(d-1)-trees. The number of (d-1)-trees with m vertices is given by (
(d-1)m
m-1
)/m, the obvious generalisation of the formula for the number of binary trees. We choose an arbitrary ordering on the at most d neighbours of each vertex in the original graph G and we can specify a connected subgraph of size m by giving:

The (d-1)-tree is mapped onto a spanning tree of a subgraph in the obvious way: the root is mapped onto v and, recursively if the root of a tree T is mapped onto u and T has a non-empty ith subtree, the root of that subtree is mapped onto the ith neighbour of u other than the father of u in the spanning tree (or other than v¢ in the initial case with u=v). Note that this process can fail if either there is no such ith neighbour or it is already present in the spanning tree.

Thus, to a polynomial factor, the number of connected induced subgraphs is at most (
(d-1)m
m-1
)/m or numerically 20.371998m for our example case.

2.2  Why this gives a crude upper bound

This upper bound is still very far from tight for at least four reasons:

  1. the process of mapping the (d-1)-tree to a spanning tree can fail because it reaches the same vertex more than once
  2. the subgraph found may have vertices of degree 1
  3. a subgraph can have many spanning trees
  4. the mapping process may fail because a vertex u does not have i remaining neighbours when the tree has a non-empty i-th subtree

Of these, the last is not interesting since we are interested in the maximum number of subgraphs which is clearly given by a graph G with very few vertices of degree less than d. We will exploit the other three in the following sections.

3  Weighted Spanning Trees

3.1  Minimal leaf spanning trees and their local property

For every (d-1)-tree we consider its number of leaves l and for every subgraph we consider the minimum of l over all its spanning trees. (We do not consider the root to be a leaf even if its degree is 1.) These minimum-l spanning trees have a local property which will be useful: two leaves (in the tree) cannot be mapped to neighbours (in the graph). This is because, if they were, we could create a new spanning tree by adding the edge between them and break the resulting cycle either adjacent to a vertex of degree greater than 2 or at the root. In either case we have removed two leaves and added at most one new one so the initial tree cannot have been minimum-l.

3.2  The number of minimum leaf spanning trees

Lemma 1 Let G be a connected graph with no vertex of degree 1. If the minimum number of leaves of spanning trees of G is l, then G has at least 2l spanning trees with exactly l leaves.

Proof: We consider one l-leaf spanning tree and show how to construct 2l distinct spanning trees each with l leaves. We take each leaf ui in turn and decide either to carry out the following process of reversal (see Figure 1) or not:

Figure
Figure 1: A reversal process

connect ui to a neighbour vi such that (ui,vi) is not already a tree edge (choosing vi the first such neighbour in some arbitrary predefined ordering of the vertices) and break the resulting cycle at the vertex v¢i closest to vi in the tree and having degree greater than 2 in the tree or being the root. The edge to be removed to break the cycle is the first on the path from v¢i to ui and we call the neighbour of v¢i u¢i; u¢i may be the same as ui or not.

The reversal process has taken the chain from ui to u¢i and attached it to vi instead of v¢i. Since the spanning tree was minimum-leaf, vi was not a leaf beforehand.

Clearly we have 2l processes each producing a new l-leaf spanning tree; it only remains to show that these trees are distinct.

We claim

Now it follows that the new spanning trees are distinct since given the initial and final spanning trees we can reproduce iteratively the chain of decisions which must have occurred. For a given ui, knowing the decisions made for previous uj, we know what vertices vi, u¢i and v¢i are; If the reversal is not performed, the edge (vi,ui) will never be added to the spanning tree and the edge (v¢i,u¢i) will never be broken; conversely, if the reversal is performed, (vi,ui) will never be broken and (v¢i,u¢i) will never be added; hence by examining the final tree we can determine whether the reversal was performed or not.

We now define a weight w(T) for every (d-1)-tree by w(T)=2-l(T) where l(T) is the number of leaves of T and we claim that for any graph G of n vertices and maximum degree d, the number of good induced subgraphs of size m is at most ndåTw(T) where the sum is taken over all (d-1)-trees of m vertices. This is because ndåTw(T) is at least equal to the sum over all triples (root, omitted neighbour, (d-1)-tree) of the weight of the tree and for a good induced subgraph G¢ with a minimum of l leaves in its spanning trees, at least 2l of these triples generate G¢ and have weight 2-l.

3.3  Bounding the weighted sum

A (d-1)-tree with m vertices of which mi have out degree i (i=0,¼,d-1) where åi mi=m-1 can be specified by giving a list of m Boolean vectors of length d-1 specifying for all vertices (say in pre-order) which of their d-1 subtrees are non empty, subject to the conditions that exactly mi of the vectors have i true elements. Moreover a proportion 1/m of such lists of vectors actually specify a tree since there is the usual condition that the first j vectors (j < m) must contain at least j true elements and exactly one cyclic rearrangement of a list with m-1 true elements has this property.

Hence the number of such trees is given by
æ
ç
è
m
m0,¼,md-1
ö
÷
ø
/m
Õ
i 
æ
ç
è
d-1
i
ö
÷
ø
mi

 
and the weighted sum over these trees is
æ
ç
è
m
m0,¼,md-1
ö
÷
ø
/m
Õ
i 
æ
ç
è
d-1
i
ö
÷
ø
mi

 
2-m0
The weighted sum over all trees is given by the sum of a polynomial number of terms of this form and so is bounded by a polynomial times the maximum of this term as the mi vary.

Writing xi for mi/m and using Stirling's approximation, we obtain that to within a polynomial the sum is given by the maximum of
æ
ç
è

Õ
i 
æ
ç
è
æ
ç
è
d-1
i
ö
÷
ø
/xi ö
÷
ø
xi

 
2-x0 ö
÷
ø
m

 
subject to åi xi=1 and åi ixi=1.

The second derivative of the logarithm of this expression with respect to any variable is negative (for xi non-negative) so there is a simple maximum. Differentiating the logarithm of the expression with respect to xi along a line x1=k-ixi, x0=k¢+(i+1)xi we find that the maximum occurs when
xi= æ
ç
è
d-1
i
ö
÷
ø
x1i(2x0)-(i+1)/(d-1)i
Numerically finding the values of x0 and x1 for which these xi satisfy the constraints gives the required upper bound. For our example case of d=9, the values of the xi are found to be (0.282189, 0.487715, 0.184391, 0.039836, 0.005379,  0.000465, 0.000025, 0.000001, 0.000000) reducing our upper bound to 16.403m ×poly(n).

4  The Probability of Failure

We now show that whatever the graph G, the process of mapping a (d-1)-tree onto a spanning tree of an induced subgraph of G has a large probability of either failing or producing a subgraph which has vertices of degree 1 or producing a spanning tree which is not minimal-leaf. We consider a stage during the mapping process where there are m¢ tree vertices still to consider.

First we consider an alternative way of constructing a random (d-1)-tree of m vertices:

  1. initialise: Create a root vertex; place it in a list of pending vertices
  2. expand: m times do:
    if the pending list is empty abort; otherwise choose the next vertex p in the pending list;
    for i from 1 to d-1, with probability 1/(d-1) add an i-th son to p and place it in the pending list;
    remove p from the pending list
  3. terminate: If the pending list is non empty abort.

Lemma 2 The probability of success is O(m-2d-1).

Proof: The probability that exactly m-1 sons are chosen non-empty is O(m-1d-1) since the mode of the number chosen is m and the range of possible numbers is m(d-1); if exactly m-1 are chosen, the process succeeds provided the pending list remains non-empty until termination which happens with probability m-1 (since exactly one of the m cyclic re-arrangements of the d-1-tuples of choices has this proprerty).

Lemma 3 Every (d-1)-tree of m vertices has the same probability of being constructed.

Proof: Each one is given by a unique sequence of m(d-1) choices containing exactly m-1 positive choices; such a sequence has probability (d-2)m(d-1)-(m-1)×(d-1)-m(d-1).

We now define the weight w¢(T) of a tree T with respect to a given root to be zero if its embedding in the graph fails and otherwise to be the same weight w(T) as previously (2-number of leaves).

Lemma 4 For any root vertex R and any neighbour v of R in any graph of maximum degree d, the average weight of the tree produced by the construction is O(cm) if c ³ (d-2)/(d-1)(1-((d-2)/(d-1))d-2/2) and there exists c¢ > 0 such that c ³ 1+(c¢/2-1)((d-2)/(d-1))d-1 and for every i (1 £ i £ d-2) c ³ ((d-2)/(d-1))i ( 1-((d-2)/(d-1))i ) c¢-i.

Proof: When a vertex p is considered and no sons are constructed, it becomes a leaf of the tree and while there is no vertex in the tree other than its father which is a neighbour of p (in the graph) and has degree at least two (in the tree), p is a potential vertex of degree 1 in the subgraph; if it remains so then the process fails. We call the set of all such leaves L. At any stage in the process when there remain m¢ vertices to consider and l elements in L, the expected value of the quantity which is 0 if the construction fails and 2-number of remaining leaves otherwise is at most cm¢c¢l. We will show this by induction on m¢. If m¢=0, then either l=0 and the process has succeeded or l > 0 and it has failed; in either case the weight is at most c¢l as claimed.

We write E[m¢,l] for the claimed upper bound cm¢c¢l and miss for the probability that a tree vertex has no sons, namely ((d-2)/(d-1))d-1. Consider the process of treating a vertex p from the pending list; one of the following cases must occur:

This completes the proof.

In our example case d=9, we find that the conditions of Lemma 4 are satisfied for c=0.784631 and c¢=0.746431.

Theorem 1 In a graph of n vertices and maximum degree d, the number of good subgraphs of order m is O((c(d-1)d-1/(d-2)d-2)mpoly(m,n)) where c is as in Lemma 4.

Proof: Lemma 4 holds for a particular root vertex (R) and neighbour (v) of R. To be sure of having a possibility of obtaining a spanning tree of an unknown good subgraph we must apply the construction to every (R,v) pair. Writing T(m,d) for (
m(d-1)
m-1
)/m the number of (d-1)-trees of m vertices,
ndcm  ³   å(R,v)cm
W(1) å(R,v)åtrees TPr[T is chosen]w¢(T) (lemma 4)
=   W(1) å(R,v)åtrees T with successful embeddingPr[T is chosen]w(T)
=   å(R,v)(O(mn×T(m,d)))-1åtrees T with successful embeddingw(T) (lemmas 2 and 3)
³  (O(mn×T(m,d)))-1ågood subgraphs Gåspanning trees T of Gw(T)
³  (O(mn×T(m,d)))-1ågood subgraphs G1 (lemma 1)
=  (O(mn×T(m,d)))-1Number of good subgraphs.

In our example case this achieves a further small reduction to O(15.984507)m ×poly(n)

5  A Lower Bound

We will now show an exponential lower bound on the number of good subgraphs. We will do so, not by exhibiting a graph for each m guaranteed to have this number of good subgraphs, but by giving a set of graphs which have at least this number on average, so that some graphs in the set must do so. We define the set by giving a random process which constructs all members of the set with uniform probability. ``Exponential'' here means exponential in m for any fixed d; for small m the bound is close to (d-1)m.

5.1  Description of the graphs

Given an integer m, we construct a graph as follows:

These graphs clearly have maximum degree d. We show a lower bound on their average number of good subgraphs by considering a process of randomly choosing a subgraph; this process may fail but it will succeed often enough.

5.2  The process of constructing a subgraph

Finally we consider the two endpoints of the chain in turn and starting from each we add the shortest chain which terminates adjacent to a vertex either already in the subgraph or earlier in the chain (other than its immediate predecessor in the chain). (In the event of multiple possible chains of the same length, choose the lexicographically first.) This gives us a connected subgraph of at most m vertices where no vertex has degree 1. To see how many distinct subgraphs are constructed, we need to consider the probability that the process succeeds and in how many ways the same subgraph might be constructed.

5.3  Probability of Success

Rather than consider a graph and the probability that a random sequence of colour choices succeeds, we consider a colour sequence and the probability that it succeeds on a random graph.

After c colours have been chosen we expect about 2c/(d(d+1)) successive pairs to have been either (i,j) or (j,i). We call a sequence of colours smooth if for every c and every pair (i < j) we have that the actual number is at most 2c/(d(d+1))+m3/4. The probability that a randomly chosen sequence is smooth is 1-o(1); in what follows we consider only smooth sequences.

As we construct the chain, we reveal the numbers of all vertices on the chain and adjacent to it; each chain vertex is adjacent to d-2 non chain vertices except the first and last which are adjacent to d-1. Thus, considering the first c vertices in the chain and their off chain neighbours, we have c(d-1) edges, each of which tells us one element of one of the permutations; since the sequence is smooth this information is evenly distributed over the d(d+1)/2 permutations.

Consider adding an edge from vertex Vi[k] to colour j as the c-th in the chain and suppose for simplicity that i < j. First we reveal the number of the element of Vj, that is we reveal one new value of pi,j, namely pi,jk; the number of possible choices is ë n/(d+1) û -2c(d-1)/(d(d+1)) +O(m3/4). Of these some will cause the process to abort if they are chosen; these are the off chain elements of Vj whose numbers are already known but an off chain Vj which was adjacent to an on chain Vi[k¢] cannot be chosen since pi,jk¢ is already known and so cannot be chosen as pi,jk. Hence the number of choices causing an abort is the number of chain vertices which are neither of colour i or j nor adjacent in the chain to a vertex of colour j, namely c(d-1)(d-2)/(d(d+1))+O(m3/4). Then we reveal the numbers of the remaining d-2 neighbours of Vi[k]. Hence the probability of failure at this step c is c(d-1)(d-2)/(n d -2c(d-1))+ o(1).

We want the probability of success at every step up to c=m-2logd n, namely Õc=1m-2logdn(1-c(d-1)(d-2)/(nd-2c(d-1))+o(1)). Writing x for m/n, taking logarithms and approximating the resulting sum by an integral we obtain a probability of success of
exp( ó
õ
x

0 
log(1- x(d-1)(d-2)/(d-2x(d-1)) )dx×m/x)
or
æ
è
exp( ó
õ
x

0 
log(1- x(d-1)(d-2)/(d-2x(d-1)) )dx/x) ö
ø
m
 
This probability multiplied by the number of colour sequence choices, namely d(d-1)m-2logdn) gives the number of successful subgraph constructions from the chosen initial vertex.

For our example of d=9, m/n=1/16 this gives (8×.779489+o(1))m so that the number of good subgraphs would be at least this except for the fact that the same good subgraph might be produced by several choices of colour sequence.

Lemma 5 A good subgraph can be produced by only O(1) colour sequence choices with a given initial vertex.

Proof: A subgraph chosen has O(d) vertices of degree greater than 2 and these vertices have degree at most d. Hence there are d(O(d)) possible paths of the specified length in the subgraph from the given initial vertex. Hence for any fixed d the number is O(1).

So the conclusion that the number of good subgraphs is (8*.779489+o(1))m, that is 6.235910 m, still holds. This lower bound is much lower than our best upper bound but is slightly better than we have been able to establish by analysis of any particular graphs. For instance a graph consisting of layers of sizes 4, 4, 5 and 5 depending on the number of the layer mod 4 with a complete bipartite graph between every pair of adjacent layers has maximum degree 9 and about 5.977144m good subgraphs.

6  Conclusions

6.1  Numerical results for the algorithm

The upper and lower bounds on the number of good subgraphs enable us to give bounds on the improvement possible in algorithms of this type by dynamic programming. If the non dynamic programming version of one of these algorithms generates O(an) induced subgraphs and runs in time an  poly(n), and the number of good induced subgraphs of size m is O(cm  poly(n)), we will choose m so as to balance the precomputation on all good subgraphs up to size m (O(cm  poly(n)) and the recursive part of the algorithm O(an-mpoly(n)). That is we take mlogc » (n-m)loga or m » nloga/(logc + loga). In the cases which interest us we have loga » 0.27 (taking logarithms to base 2) and our upper and lower bounds on logc are 3.998602 and 2.64060. This tells us that we can take m/n as 0.063253 and that improvements in the analysis cannot increase this ratio beyond 0.092764 by using our argument about good subgraphs. This ratio m/n is also the proportional reduction in loga which is proved possible. In particular in conjunction with the algorithm of [3] this give an algorithm running in time O(2n/4).

6.2  Other possibilities

Of course there remains the possibility that not all our good subgraphs need to be generated by the algorithm. The argument apparently most likely to demonstrate this so as to further usefully reduce the upper bound is obtained by considering the ``border'' between the induced subgraph and the rest of G. Writing U for the vertices of the induced subgraph, V for the vertices not in U but adjacent to a vertex of U and W for the remaining vertices, we can see by an argument first used in [4] that we can assume that any vertex in V is adjacent to a vertex of W or three vertices of U. On probabilistic grounds we would expect most good subgraphs to fail this test; proving this in the worst case seems harder.

References

[1]
Jian, T., An O(20.304n) algorithm for solving maximum independent set problem, IEEE Trans. Comput. C-35 (1986), 847-851.
[2]
Robson, J. M., Algorithms for maximum independent sets, J. Algorithms 7 (1986), 425-440.
[3]
Robson, J. M., Finding a maximum independent set in time O(2n/4)?, Technical report RR-1251-01, LaBRI, (2001),
[4]
Tarjan, R. E. and Trojanowski, A. E., Finding a maximum independent set, SIAM J. Comput. 6 (1977), 537-546.




File translated from TEX by TTH, version 3.05.
On 10 Sep 2002, 15:31.