The difficult graph I?b@fd}^_ has a number of stable blocks. These suggest the possibility of finding new graph reductions. Let G be a graph, V=V(G) be its vertex set, I be an independent set, and . We call X a stable block if . Non-empty critical independent sets in non-Konig-Egervary graphs have this property. Their significance is that if X is a stable block and it can identified efficiently then it leads to a reduction. This is because .
No previous difficult graph had a stable block – while I?b@fd}^_ has several. Each of the following sets is independent and generates a stable block: [0, 1, 2], [0, 1, 3], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [2, 4, 5], [3, 4, 5]. These sets are not critical independent sets. We don’t know what’s special about them. We would like to find some property that they have – that will lead us to new alpha-reductions.