Stable Blocks

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, X=I\cup N(I) and X^c=V\setminus X\neq \emptyset. We call X a stable block  if \alpha(G[X])=|I|. 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 \alpha(G)=\alpha(G[X])+\alpha(G[X^c]).

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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s