Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The independence number of a graph is the cardinality of a maximum set of vertices which are pairwise non-adjacent. It is an NP-hard graph invariant.

There are a variety of ways to efficiently reduce the calculation of the independence number, for instance, if the graph has a simplicial vertex, there is a maximum independent set which contains it (these can be identified efficiently and then it and its neighbors can be removed). There are a variety of graph classes, for instance, claw-free graphs, where it is known that the independence number can be computed efficiently. There are a variety of efficiently computable upper and lower bounds for the independence number of a graph including, respectively, Lovasz's theta function and the residue.

The graph I?bbrr[ko (in B. McKays Graph-6 notation, picture below) has independence number 4. It is the smallest graph such that, using the theory of the independence number of a graph, can not be efficiently reduced, nor belongs to a class where the independence number can be efficiently computed, nor whose value can be predicted from known efficiently computable upper and lower bounds.

In this case, I know the independence number is 4. Lovasz's theta function upper bound gives the exact value of the independence number - but no lower bound that I know of gives the correct value of 4 - no lower bound that I am aware of gives a better value than 3. Would anyone know a lower bound for the independence number of a graph that gives the value 4 for graph I?bbrr[ko ?

I am trying to see how far the existing theory for the efficient computation of the independence number of a graph can be taken - and then find examples that will motivate new theory.

A drawing of the graph can be found here.

share|improve this question
How did you get 3? I can't even do better than 2 :( –  Felix Goldberg Jan 25 '13 at 22:09
Probably it won't fly, but the approach is worth looking at: tu-ilmenau.de/fileadmin/media/math/Preprints/2009/… –  Felix Goldberg Jan 25 '13 at 22:19
Try numerical order. I found such a set of 4 independent points. For such graphs, I find using the triangles helps. Gerhard "Ask Me About System Design" Paseman, 2013.01.25 –  Gerhard Paseman Jan 26 '13 at 0:49
@AnthonyQuas: I think the OP is asking for a "principled" derivation of the fact that $\alpha=4$, not just for the calculation. It's a very interesting project... –  Felix Goldberg Jan 26 '13 at 1:05
Towards your goal of furthering new theory, you might present ten such minimal graphs and ask what else they may have in common; that might spur the development of new and better lower bounds. Gerhard "Ask Me About System Design" Paseman, 2013.01.25 –  Gerhard Paseman Jan 26 '13 at 1:52
add comment

2 Answers

A simple method will be to run a greedy algorithm for finding an independent set: recursively choose a vertex of the least degree (and least index), add it to the set, and remove it and all its neighbors from the graph.

I'm not sure if that's what you mean by a method, but it works for the mentioned example.

share|improve this answer
Nice! I used to think that this procedure produces the Caro-Wei bound, which I checked straight away and got only 2. Turns out that its stronger - this paper (pirate.shu.edu/~kahlnath/indnum.pdf) attributes the procedure and the resultant bound to Murphy (section 3). –  Felix Goldberg Jan 26 '13 at 0:21
It only works here if you happen to pick the right vertex of lowest degree to start with -- if you start by picking $5$, you'll only end up with a set of size $3$. –  Kevin P. Costello Jan 26 '13 at 1:02
add comment

A greedy algorithm gives a lower bound, often useful, but isn't a graph invariant (to be an invariant the number must be independent of graph representation - any greedy algorithm is dependent on the choice of vertex order/labels). You could make it into an invariant by, for instance, defining it to equal the largest possible value of all possible ways the heuristic can be implemented. For a greedy choosing of vertices of minimum (or maximum, etc) degree vertices, there will generally be an exponential number of ways to proceed - this invariant won't be efficiently computable.

I get 2 when I calculate Murphy's bound. I wasn't previously aware of it. Thanks.

I get 3 when I use the following lower bound of Fajtlowicz. Choose any vertex v. Let O(v) be the set of vertices at odd distance from v. Let OH(v) be the set of edges in the graph induced on O(v). Then, it can be argued, that the independence number of the parent graph is at least |O(v)|-|OH(v)|. Then take the max over all the vertices. Each v calculation requires a calculation of the corresponding distances to the other vertices. This can be done efficiently. To get the max, repeat n times, which is still efficient.

The properties this graph I?bbrr[ko has includes that it is claw-free, any optimum of the relaxed vertex packing IP has only 1/2's in the solution, it has no simplicial vertices, no magnets, isn't perfect, and it is almost Konig-Egervary (it is possible to remove a single vertex so that the resulting graph has equal covering and matching numbers).

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.