3
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
0
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. Do you think such extremal cases are common for the graphs of order $n$? $\endgroup$
    – joro
    Commented Feb 4, 2014 at 9:12
  • $\begingroup$ 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. $\endgroup$
    – Vinicius dos Santos
    Commented Feb 4, 2014 at 12:51
  • $\begingroup$ Are extremal examples easy for cubic graphs? $\endgroup$
    – joro
    Commented Feb 4, 2014 at 14:41
  • $\begingroup$ I have no clue, but it is definitely harder that the general case. $\endgroup$
    – Vinicius dos Santos
    Commented Feb 4, 2014 at 17:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .