Improved Algorithms for Maximum

Independent Sets J.M. Robson LaBRI Université Bordeaux 1 Maximum Independent Set Algorithms

in time O(2^{cn})

Tarjan and Trojanowski [1977]: c < 1/3 (to find size of a maximum independent set) Robson [1984]: c < 0.296 (polynomial space) or c < 0.276 (space same order as time) target c < 1/4?

Improvements (still a long way above 1/4)

One slight improvement in the analysis: reduces c by 0.003

Modification of the algorithm in the critical cases: analysis incomplete

Better analysis of the Time-space trade off: similar reduction appears likely

Basic Ideas of the algorithms Choose a vertex and either include it in the set or exclude it from the graph: 2 recursive calls on smaller graphs Good if node has high degree Special treatment of vertices of very low degree Choose neighbour of vertex of low degree: in one of the recursive calls it remains and has lower degree Dominance Special algorithms to find m.i.s. of graph on condition that it includes one or two of a small set of vertices Ignore regular and non-connected graphs

Improvement 1: better local analysis The critical case involves a vertex A of degree i with a neighbour B of degree j > i; B is the “chosen” vertex. Larger j gives better performance (...) A has another neighbour B′ which is not a neighbour of B (otherwise A dominates B) d(B) = j′ with i ≤ j′ ≤ j Large j′ gives a larger degree neighbour of A in the recursive call on (G − B) Small j′ gives a low degree vertex in the recursive call on (G − N̄(B)) Take worst case among all j′ in the range More detailed analysis in the critical cases

(i = 5, 6) The worst case is impossible

For i = 5, 6, the worst case occurs when the two neighbours B and B′ of A have degrees i + 1 and i.

We can show improvements unless in N(A)

every vertex of degree i + 1 has every nonneighbour of degree i B has two non-neighbours there is no triangle (i = 6): any two vertices of degree 6 not adjacent to B are connected (i = 6): B is the only vertex of degree 7 (i = 6): there are exactly two vertices of degree 6 not adjacent to B.

Improving the algorithm in this case

So the worst case occurs when B has two connected non-neighbours B′ and B′′ and three non-connected neighbours C_{1}, C_{2} and C_{3}. Moreover the C_{i} are candidates to be an A and so each have two connected neighbours of degree 6 which cannot be both B′ and B′′. Hence we can replace the sequence of calls starting at B by: ms(G − N̄(A)), ms^{1}(G − N̄(B), {B′, B′′}), ms(G − N̄(C_{1})), ms(G − N̄(C_{2}) − C_{1}), ms^{1}(G − N̄(C_{3}) − C_{1} − C_{2}, {B′, B′′}) where the first four calls all have a vertex of degree at most 5. Hence the time is less than the supposed worst case by ≈ 5%.

Producing a reduction in c of a little over 0.001.

Time-space trade-off

Principle: don’t repeat the computation on a subgraph for which it has already been done

Cut off point m = αn such that the number of subgraphs of size ≤ m is less than the work done on subgraphs ≥ m

multiplies the constant c by 1 − α

Upper bound the number of connected subgraphs of size m by the number of 7-ary trees of size m. (7 Because cruder analysis suffices for graphs of degree > 8; × poly(n))

This is a very crude upper bound for two reasons: some trees are not the spanning tree of a subgraph; some subgraphs have many spanning trees

Attempted tighter enumeration

Multiply number of trees by probability that a random tree is the (breadth first) spanning tree of a subgraph

Want the worst case; don’t know which graphs are worst case: Approximate by probabilistic model ...

Any long sequence of edges followed in (breadth first) traversal of the tree leads to a random vertex of the graph!

A newly encountered son must not be a neighbour of a vertex encountered earlier in the tree; The i-th son visited lies in the ith vertex traversed (to o(n)) for an earlier vertex v there are ≈ 53 graph vertices at distance 2 from v in the graph and not adjacent to v in the tree (conditional on ok so far) vertex i has probability > 53/n of being one of these vertices and its son has probability 1/7 of being at distance 1 from v Hence probability of success ≈ e^{−53i/7n} Hence probability of success for size m tree (e^{−53α/14} )^{m} Break even point at α ≈ 0.0766 should reduce c to below 0.27

Continuing work

• Complete the analysis of the neighbourhood of critical vertices of degree 4, 5 and 6 (by steam?) Relatively easy for degree 4 because very few possible induced graphs Does the sequence of recursive calls generated around a vertex of degree 5 or 6 necessarily include subgraphs where a vertex whose degree has been reduced is adjacent to one further out which is still of high degree?

• Rigorous enumeration of number of connected induced subgraphs in the worst case (has this been done before?)