MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Independent set is polynomial in claw-free graphs, so I am wondering if this can approximate independent set.

By adding enough edges to $G$ and gets claw-free $G'$.

IS in $G'$ is IS in $G$, so this is a bound for the MIS.

If one adds very few edges, the bound is better.

Is it possible to efficiently find $G'$ with as few edges as possible?

One approach is to use integer programming, though in general this is NP hard. Limited experiments with this suggest the approximation of MIS is good.

Another approach is naive greedy algorithm, though this doesn't seem to approximate well.

The same question is for "claw-free" replaced by $X,Y$-free where IS for $X,Y$-free is polynomial.

share|cite|improve this question
up vote 8 down vote accepted

It's NP-complete, by a reduction from finding the largest triangle-free subgraph of a given graph $G$, which was proved NP-complete by M. Yannakakis, "Edge-deletion problems", SIAM J. Comput. 10(2):297–309, 1981.

Given a graph $G$ for which we want to find the largest triangle-free subgraph, let $H$ be the graph formed from the complement of $G$ (that is, it has an edge exactly when $G$ does not have an edge) together with one new vertex $v$ adjacent to everything else. Adding edges to $H$ corresponds to removing edges from $G$. If an augmentation of $H$ has a claw, it has one where $v$ is the central vertex. Sp in order for an augmentation of $H$ to be claw-free, it is necessary and sufficient that we add at least one edge to each independent triple of vertices other than $v$, which corresponds to removing at least one edge from each triangle of $G$. So removing $v$ from the minimum claw-free augmentation of $H$ and then complementing gives the maximum triangle-free subgraph of $G$, and vice versa.

share|cite|improve this answer
Thank you, interesting. – joro Feb 4 '14 at 9:12

I don't know whether it is possible to find a small set of edges to add in order to make a graph claw-free efficiently, but I think this is not a good approach for approximating MIS.

Consider the star on $n$ vertices, that is, an independent set of size $n-1$ together with a universal vertex. If you try to turn it into a claw-free graph you would have to make it complete. But note that the sizes of a MIS of the star on $n$ vertices and of the complete graph on $n$ vertices are $n-1$ and $1$, respectively.

share|cite|improve this answer
Thanks. Do you think such extremal cases are common for the graphs of order $n$? – joro Feb 4 '14 at 9:12
It is hard to know how common they are, but it is easy to find many graphs with a "hidden star" like the idea above, implying large gaps between the original graph and the augmentation. – Vinicius dos Santos Feb 4 '14 at 12:51
Are extremal examples easy for cubic graphs? – joro Feb 4 '14 at 14:41
I have no clue, but it is definitely harder that the general case. – Vinicius dos Santos Feb 4 '14 at 17:20

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.