We just learned about the magnet reduction in a new paper by Leveque and de Werra, “Graph transformations preserving the stability number” in DAM 160 (2012). If, for adjacent vertices a and b, every vertex of N(a)\N(b) is adjacent to every vertex of N(b)\N(a) then this pair of vertices is called a magnet. If G is the original graph and G’ is the graph formed by removing both vertex a together with every edge adjacent to vertex b then, it can be argued, alpha(G)=alpha(G’). Since identifying whether a graph has a magnet requires inspection of at most e edges and then finding the neighborhoods of the endpoints, this property can be checked efficiently.
In fact, the last difficult graph I?b@fd}^_ has a magnet – and is efficiently reducible. After Patrick added the property “has_magnet” to INP, he ran the program and discovered the next difficult graph I?bbrr[ko.
This graph has order 10, and independence number 4. Lovasz theta correctly predicts alpha, but the best lower bound is 3 – so we need a better lower bound that will predict the independence number of this graph – or we need a new reduction that works for this graph. Intriguingly, this graph has stable blocks: for each of the following non-maximum independent sets I, it is the case that . These sets are [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4].