n=9 solved (again)!

The graph HCrb‘rk is now solved. Patrick added the efficiently computable  lower bound max_odd_minus_odd_horizontal, which correctly predicted the independence number and matched the best computed upper bound.

Then Patrick ran INP to find the next difficult graph – which has 10 vertices. So, n=9 is solved (it was solved before using my branch of the code – and a more costly version recursive version of max_even_minus_even_horizontal – but now we’ve switched exclusively to Patrick’s code). This means that every graph with fewer than 10 vertices can either be reduced in polynomial time – or the independence number can be predicted from efficiently computable lower and upper bounds which match. On to n=10!

The next difficult graph is I?b@fd}^_ Here’s a picture:

 

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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