A $d$-claw in a graph is a set of $d+1$ vertices, one of which (the "center") is connected to the other $d$, but the other $d$ are not connected to each other. A graph is called $d$-claw free if it has no $d$-claw, that is: if one vertex is connected to $d$ other vertices, then at least two of these vertices are connected. One advantage of $d$-claw-free graphs is that they allow efficient approximation algorithms for the Maximum Independent Set problem. For example, this algorithm by Meike Neuwohner provides an approximation of about $d/2$.

Let us call a graph $G$ subgraph $d$-claw free if in every subgraph of $G$, there is at least one vertex that is "$d$-claw-free", that is, not the center of a $d$-claw. This property is weaker than $d$-claw-free.

In a subgraph $d$-claw free graph, one can start with an empty set, add a $d$-claw-free vertex, remove this vertex and all its neighbors, and repeat. Every added vertex invalidates at most $d-1$ vertices from the maximum independent set, so this algorithm achieves a $(d-1)$-approximation.

Question: is there a better approximation for the maximum independent set in subgraph $d$-claw free graphs?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.