LaBRI, Université Bordeaux 1, F-33405, Talence France
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.
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.
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.
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 (
| |
|
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 (
| |
|
Thus, to a polynomial factor, the number of connected induced subgraphs is at most (
| |
|
This upper bound is still very far from tight for at least four reasons:
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.
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.
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.
|
|
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. |
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.
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
|
|
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
|
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
|
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:
Lemma 2
The probability of success is O(m-2d-1).
Lemma 3
Every (d-1)-tree of m vertices has the same probability of being
constructed.
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.
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:
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.
| |
|
In our example case this achieves a further small reduction to O(15.984507)m ×poly(n)
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.
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.
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.
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
|
|
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.
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.