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.

• a vertex of degree 4 (which is the minimum degree)

• a vertex of degree 5 (which is the minimum degree)

• a vertex of degree 6 (which is the minimum degree)

• a vertex of degree 7 (which is the minimum degree)

• the independent set is to include at least two vertices out of a list of 4

• the independent set is to include at least two vertices out of a list of 5

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 B_{1}, B_{2}, · · ·.

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 B_{1} and B_{2} are not adjacent and have no common neighbours; B_{2} and B_{3} are not adjacent and have one or two common neighbours; B_{4} and B_{5} 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 each vertex pair {B_{i}, B_{j}} (in the obvious order and with i < j), whether {B_{i}, B_{j}} is an edge,

• for each vertex, its degree

• for each possible number of possible common neighbours, for each vertex pair, whether this pair has exactly this number of common neighbours.

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

• Not canonical A particular subcase may be represented by many labels depending on the order of the vertices. The order giving the minimum label in lexicographic order is considered the canonical representation and the algorithm need only specify how to treat these canonical versions. If all the labels in an interval are non-canonical, the subcase can be ignored. A prefix which does not even include all the information about the edges between the vertices B may be recognised as non-canonical.

subcase number 3057:
Neighbourhood of vertex of degree 6:
not analysed because not in canonical order (based only on
edges)
permutation: 1->1  2->2  3->3  4->5  5->4  6->6
any     any     any     any     any     any      ;
        0()     0()     0()     0()     0()
0()             0()     0()     0()     1()
0()     0()             0()     0()     1()

0()     0()     0()             0()     1()
0()     0()     0()     0()             0()
0()     1()     1()     1()     0()

a permutation demonstrating non-canonicity is given in an obvious format. Or the degree information may produce non-canonicity:

subcase number 3078:
Neighbourhood of vertex of degree 6:
not analysed because not in canonical order (based only on
edges and degrees)
permutation: 1->1  2->2  3->3  4->5  5->4  6->6
6,5     6,4     6,4     7,5     6,4     any      ;
        0()     0()     0()     0()     0()
0()             0()     0()     0()     1()
0()     0()             0()     0()     1()
0()     0()     0()             1()     0()
0()     0()     0()     1()             0()
0()     1()     1()     0()     0()

or the common neighbour information may do so:

subcase number 10646:
Neighbourhood of vertex of degree 6: not analysed because not in canonical order
permutation: 1->1  2->2  3->4  4->3  5->5  6->6
6,4     6,4     6,4     6,4     6,4     7,5      ;
        0(0[3]) 0(0[3]) 0(0[3]) 0(0[3]) 1(0[3])
0(0[3])         0(1-3)  0(0[3]) 1(0-3)  0(0-3)
0(0[3]) 0(1-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)
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)

• dominance and subdominance A vertex B adjacent to all or all but one of the others produces a case of dominance or subdominance which is treated separately in the paper so that these subcases are not analysed here:

subcase number 12325:
Neighbourhood of vertex of degree 6: not analysed because of (sub)dominance
any     any     any     any     any     any
        0()     0()     0()     0()     1()
0()             0()     0()     1()     0()
0()     0()             1()     0()     1()
0()     0()     1()             0()     1()
0()     1()     0()     0()             1()
1()     0()     1()     1()     1()

• only possible in regular graphs The paper explains why regular connected graphs can be ignored in the timing analysis. In all other cases, the choice of the vertex A will ensure that at least one B has degree greater than A. Thus we ignore cases such as:

     subcase number 12326:
     Neighbourhood of vertex of degree 6: not analysed because can be avoided in non-regular graph
     6,4     6,4     6,3     6,3     6,3     6,3
             0()     0()     0()     0()     1()
     0()             0()     0()     1()     0()
     0()     0()             1()     0()     1()
     0()     0()     1()             1()     0()
     0()     1()     0()     1()             0()
     1()     0()     1()     0()     0()

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 B_{i} is in the set

3. two B_{i}, B_{j} 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 B_{1}); 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}).

B_{4} and B_{6} are the chosen vertices, A, B_{5} and the external neighbours of B_{4} and B_{6} are neighbours (note that the external neighbours of B_{4} and B_{6} are known to be distinct) and B_{1}, B_{2} and B_{3} are rejected. B_{5} is also a rejected vertex (the choice of (B_{4}, B_{5}) 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 B_{3}, B_{4} and B_{5}, it is equally true that an independent set to be considered will contain two of their neighbours but, since B_{7} 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 B_{j} (j > i) must also be in the independent set. If there remain only two candidates B_{j} 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 B_{1} and B_{2} 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, B_{1} and B_{2} are rejected so that the common neighbours of B_{5} with B_{3} and with B_{4} are excluded; B_{5} has at least one common neighbour with each of the other two and these two cannot be the same vertex since B_{3} and B_{4} 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

B_{i} and B_{j} 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 B_{i} and B_{j}. 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 B_{2} 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 B_{i}.)

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.

• Is the list of recursive calls for each subcase complete?

• Are the neighbour, rejected, forcibly included and forcibly excluded vertices correctly listed and counted?

• Is there correct justification for the constant claimed?

• Is the arithmetic correct and is the total less than or equal to the relevant constant?

• Are all subcases covered?

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.