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, ….
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.
This order is most easily described as the lexicographic order on a string describing the subcase. This string contains the following information
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.
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)
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()
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()
The calls are of four types depending on the vertices chosen for the independent set:
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.
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.
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 B7Similarly, 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:
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.
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=valueBi 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=valueIn 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.)
Any questions or other feedback are very welcome.
Mike Robson
robson@labri.fr
25 August, 2006.