1  Generalities

I give here what I hope is sufficient information to check (by hand or automatically) the correctness of the lists of subcases and how to handle them generated by my C program. The alternative approach of trying to convince the reader of the correctness of the C program would be completely hopeless.

The lists of subcases should describe how to handle all of the following cases apart from those explicitly dealt with in the paper.

The two types are very similar since, in the first four, we use the fact that there is a maximum independent set containing either the given vertex or at least two of its neighbours. I always call the given vertex A and its neighbours or the listed vertices B1, B2, .

2  Subcases

A subcase is defined by the subgraph induced by B and partial information on N(B)\B\A the set of other vertices adjacent to elements of B. This extra information always includes the degree of each vertex of B; for each pair of vertices of B there is some information on their number of common neighbours (excluding A and any common neighbours in B). This information may be the exact number or a range of possible values. When it is a range, the upper limit will always be the maximum value possible given that certain cases are treated elsewhere in the paper; when it is an exact value, the maximum value which was possible is given in square brackets.

For example:

subcase number 3061:
Neighbourhood of vertex of degree 6:
6,5     6,4     6,4     6,4     6,4     7,4      ;
        0(0[3]) 0(0[3]) 0(0[3]) 0(0[3]) 0(0[3])
0(0[3])         0(1-2)  0(0-3)  0(0-3)  1(0-3)
0(0[3]) 0(1-2)          0(0-3)  0(0-3)  1(0-3)
0(0[3]) 0(0-3)  0(0-3)          1(0-3)  0(0-3)
0(0[3]) 0(0-3)  0(0-3)  1(0-3)          0(0-3)
0(0[3]) 1(0-3)  1(0-3)  0(0-3)  0(0-3)

Vertices B1 and B2 are not adjacent and have no common neighbours; B2 and B3 are not adjacent and have one or two common neighbours; B4 and B5 are adjacent and have between 0 and three common neighbours.

3  Ordering

An order is defined on totally defined subcases (that is those with an exact number of common neighbours for every pair of vertices in B) in such a way that every subcase contains all the totally defined subcases in an interval. The subcases in a file are listed in this order so that the first totally defined subcase in the interval for one subcase is the immediate successor of the last one in the interval of the preceding subcase.

This order is most easily described as the lexicographic order on a string describing the subcase. This string contains the following information

For any not totally defined subcase, the labels of the possible completions are all those with a given prefix. For example the label
000000001001100666667===== describes the subcase given above.

4  Subcases not treated

5  Recursive call lists

For every subcase except those mentioned in the previous section, a list of recursive calls is given which covers all possible independent sets containing either A or at least two vertices in B. Before the list, a permutation of the vertices B is given and their numbering in the calls is that of the permuted version (which is also given.)

The calls are of four types depending on the vertices chosen for the independent set:

  1. A is in the set
  2. one Bi is in the set
  3. two Bi,  Bj are in the set
  4. no vertex has been chosen to be in the set
Calls of types 2 and 3 are ordered first by i and then by j; a call of type 1 will either be the first or will follow only a call of type 2 (necessarily with B1); a call of type 4 will be the last.

In a call there may be rejected vertices. These are the vertices which were chosen in the previous calls. A call will be written as mis(G-C-N-R) where C is the set of chosen vertices, N is the set of neighbours of chosen vertices and R is the set of rejected vertices (excluding C and N).

For example in the example subcase given above the last call is
mis(G-{B4,B6}-{A,B5+5 neighbours of B4+ 4 neighbours of B6}-{B1,B2,B3}).
B4 and B6 are the chosen vertices, A, B5 and the external neighbours of B4 and B6 are neighbours (note that the external neighbours of B4 and B6 are known to be distinct) and B1, B2 and B3 are rejected. B5 is also a rejected vertex (the choice of (B4,B5) having been already considered) but is not listed among the rejected vertices because it is also a neighbour.

Occasionally other vertices can be excluded from the recursive call; they will be listed after the R.

5.1  Forcibly included vertices

In all cases, we are only interested in independent sets containing at least two neighbours of every rejected vertex. If, after excluding the vertices C, N and R, the number of neighbours left for some vertex is exactly the number of neighbours required to reach two, then all remaining neighbours must be included. A simple example is:
subcase number 9552:
Neighbourhood of vertex of degree 7:
8,7     8,5     7,2     7,2     7,2     7,2     7,2     ;
        0(0-5)  0(0-2)  0(0-2)  0(0-2)  0(0-2)  0(0-2)
0(0-5)          0(0-2)  0(0-2)  0(0-2)  1(0-2)  1(0-2)
0(0-2)  0(0-2)          1(0-1)  1(0-1)  1(0-2)  1(0-2)
0(0-2)  0(0-2)  1(0-1)          1(0-1)  1(0-2)  1(0-2)
0(0-2)  0(0-2)  1(0-1)  1(0-1)          1(0-2)  1(0-2)
0(0-2)  1(0-2)  1(0-2)  1(0-2)  1(0-2)          0(0[0])
0(0-2)  1(0-2)  1(0-2)  1(0-2)  1(0-2)  0(0[0])

Recursive calls are
...
mis(G-{B1,B7}-{A,B2,B3,B4,B5+7 neighbours of B1}-{B6}
     - 2 neighbours of vertex (B6) reduced to degree 2)

(For vertices B3, B4 and B5, it is equally true that an independent set to be considered will contain two of their neighbours but, since B7 is a neighbour already chosen for the set, this only implies that one of their external neighbours should be in the independent sets considered by the recursive call.

5.2  Forcibly excluded vertices

In a call of type 2, one Bj (j > i) must also be in the independent set. If there remain only two candidates Bj and they are known to have common neighbours, then all these common neighbours can be removed from the graph. For instance:
subcase number 10739:
Neighbourhood of vertex of degree 7:
7,5     8,6     7,5     7,5     7,5     7,5     7,4     ;
        0(1-3)  0(0[4]) 0(0[4]) 0(1-4)  0(1-4)  1(0[4])
0(1-3)          0(0[4]) 0(0[4]) 0(1-4)  0(1-4)  1(1-4)
0(0[4]) 0(0[4])         0(0-4)  0(0-4)  1(0-4)  0(0-4)
0(0[4]) 0(0[4]) 0(0-4)          1(0-4)  0(0-4)  0(0-4)
0(1-4)  0(1-4)  0(0-4)  1(0-4)          0(0-4)  0(0-4)
0(1-4)  0(1-4)  1(0-4)  0(0-4)  0(0-4)          0(0-4)
1(0[4]) 1(1-4)  0(0-4)  0(0-4)  0(0-4)  0(0-4)

Permutation:  1-->4 2-->6 3-->5 4-->1 5-->2 6-->3 7-->7 gives
Neighbourhood of vertex of degree 7:
7,5     7,5     7,5     7,5     7,5     8,6     7,4     ;
        1(0-4)  0(0-4)  0(0[4]) 0(0-4)  0(0[4]) 0(0-4)
1(0-4)          0(0-4)  0(1-4)  0(0-4)  0(1-4)  0(0-4)
0(0-4)  0(0-4)          0(1-4)  1(0-4)  0(1-4)  0(0-4)
0(0[4]) 0(1-4)  0(1-4)          0(0[4]) 0(1-3)  1(0[4])
0(0-4)  0(0-4)  1(0-4)  0(0[4])         0(0[4]) 0(0-4)
0(0[4]) 0(1-4)  0(1-4)  0(1-3)  0(0[4])         1(1-4)
0(0-4)  0(0-4)  0(0-4)  1(0[4]) 0(0-4)  1(1-4)

Recursive calls are
...
 mis(G-B5-{A,B3+5 neighbours of B5}-{B1,B2,B4}- 1 common neighbour of B6 and B7

Similarly, in a call of type 4, two of the last three vertices will be in the independent set and any known common neighbours of any pair of them can be removed (taking care to avoid counting the same vertex twice.) Example:
a set of five vertices from which two are to be chosen
4,2     4,2     4,2     4,2     4,2     ;
        0(2[2]) 0(1-2)  1(0[2]) 1(0[2])
0(2[2])         1(0[2]) 0(1-2)  1(0[2])
0(1-2)  1(0[2])         1(0[2]) 0(1-2)
1(0[2]) 0(1-2)  1(0[2])         0(1-2)
1(0[2]) 1(0[2]) 0(1-2)  0(1-2)

After two calls with B1 and B2 chosen, the third call is of type 4:
mis(G-{}-{}-{B1,B2}-2 common neighbours of B5 with the two other remaining vertices):

No vertices are chosen or neighbours, B1 and B2 are rejected so that the common neighbours of B5 with B3 and with B4 are excluded; B5 has at least one common neighbour with each of the other two and these two cannot be the same vertex since B3 and B4 have no common neighbour.

6  Coefficients

We have an upper bound on the time for each recursive call of the form C αn-x where n is the number of vertices in the graph G, x is the number of vertices removed from the graph in the recursive call and C is a constant depending on any special information we have about this graph. This time (without the n) is listed after the call itself with justification of the constant C claimed. The possible forms of constant and justification are listed here with further explanation where it appears necessary.
  a1 (1 out of 2 :  Bi and Bj)*power=value
  a1 (1 out of 2 : neighbours of Bi)*power=value
  a1 (1 out of 2 : union of neighbours of Bi and Bj)*power=value

Bi and Bj are both rejected and are not adjacent. If none of their neighbours (after removing neighbours of chosen vertices) was in the independent set, we could replace the two chosen vertices by Bi and Bj. An example:
subcase number 11875:
Choose two vertices out of  5:
4,2     4,1     4,1     4,1     5,2     ;
        0(0-1)  0(0-1)  1(0-1)  1(0-2)
0(0-1)          1(0-1)  1(0-1)  1(0-1)
0(0-1)  1(0-1)          1(0-1)  1(0-1)
1(0-1)  1(0-1)  1(0-1)          0(0-1)
1(0-2)  1(0-1)  1(0-1)  0(0-1)

Recursive calls are
(1): mis(G-B1-{B4,B5+2 neighbours of B1}-{}):
   alpha^-1 (a vertex has degree<=2 : B2)*alpha^-5=0.331108
(2): mis(G-{B4,B5}-{B1,B2,B3+2 neighbours of B5}-{}):
   a2 (1 out of 3 : union of neighbours of B1 and B2)*alpha^-7=0.260655

(Note that B2 is a rejected vertex although there have been no calls where it was chosen; it has been considered and no calls were necessary since no independent set can contain it and a later Bi.)


  a1y (two disjoint 1 out of 2 : neighbours of Bi and {Bj,Bk})*power=value
  a1y (two disjoint 1 out of 2 : neighbours of each of Bi and Bj)*power=value
  a2 (1 out of 3 : Bi, Bj and Bk)*power=value
  a2 (1 out of 3 : neighbours of Bi)*power=value
  a2 (1 out of 3 : union of neighbours of Bi and Bj)*power=value
  a2x (two disjoint 1 out of 3 : neighbours of each of Bi and Bj)*power=value
  a2y (1 out of 3 not a triangle : Bi, Bj and Bk)*power=value
  a3 (2 out of 3 : Bi, Bj and Bk)*power=value
  a3 (2 out of 3 : neighbours of Bi)*power=value
  a3z (two disjoint 2 out of 3 : neighbours of each of Bi and Bj)*power=value
  a4 (2 out of 4 : neighbours of Bi)*power=value
  a4x (two disjoint 2 out of 4 : neighbours of each of Bi and Bj)*power=value
  a4y (disjoint 2 out of 4 and 2 out of 5 : neighbours of each of Bi and Bj)*power=value
  a5 (2 out of 5 : neighbours of Bi)*power=value
  alpha^-1 (a vertex has degree<=2 : Bi)*power=value
  alpha^-2 (a vertex has degree=1 : Bi)*power=value
  c2 (degree 2 : Bi)*power=value
  c3 (degree 3 : a neighbour of Bi)*power=value
  c3 (degree 3 : Bi)*power=value
  c3x (degree 3 twice not adjacent :  Bi and Bj)*power=value
  c4 (degree 4 : a neighbour of Bi)*power=value
  c4 (degree 4 : Bi)*power=value
  c5 (degree 5 : a common neighbour of Bi and Bj)*power=value
  c5 (degree 5 : a neighbour of Bi)*power=value
  c5 (degree 5 : Bi)*power=value
  c6 (degree 6 : a neighbour of Bi)*power=value

In some cases where we say there is a vertex of degree d, we really mean degree d. This is harmless when every degree d implies a better (smaller) constant than degree=d. The only exceptions are that degree 1 or 2 give better constants than degree 0. This is why we distinguish between degree 2 and degree <=2.

The sum of all the time bounds is given after the list of recursive calls and should be at most the value claimed in the paper for the appropriate constant (for instance a7 for the list of neighbourhoods of a vertex of degree 7.)

7  A YACC grammar

A YACC grammar for correctly formed subcase files is available and can be used to check that the six compressed files are correctly formed. One version (contextfree.y) checks only syntactic well-formedness. In the other version (file.y), YACC statements to check semantic correctness are included and I now hope that these checks are comprehensive. I have added comments to the grammar and the various files it uses to try and make it clear that the tests carried out are really sufficient to guarantee correctness of the analysis. Meanwhile anybody can add more tests to the grammar, if it appears necessary, or can try making small changes in the files and observe whether the grammar detects any incorrectness introduced.

8  Update

I am posting new versions of all the files today (August 25) including a more comprehensive checking. The compressed files have been produced by a slightly different version of the program, so the subcase numbers of the examples given here will no longer correspond to those in the subcase files.
A new version of the program reduces the constant slightly and its files and grammar will be posted as soon as they are thoroughly checked.

Any questions or other feedback are very welcome.
Mike Robson
robson@labri.fr
25 August, 2006.


File translated from TEX by TTH, version 3.05.
On 25 Aug 2006, 11:35.