0
$\begingroup$

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?

$\endgroup$

0

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.