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.



Making a graph claw-free by adding as few edges as possible
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.


