Local Optimality and Its Application on Independent Sets for k-claw Free Graphs

Given a graph G = (V,E), we define the locally optimal independent sets asfollows. Let S be an independent set and T be a subset of V such that S ∩ T = ∅ and Γ(S) $$ \subseteq $$ T, where Γ(S) is defined as the neighbor set of S. A minimum dominating set of S in T is defined as TD(S) $$ \subseteq $$ T such that every vertex of S is adjacent to a vertex inTD(S) and TD(S) has minimum cardinality. An independent setI is called r-locally optimal if it is maximal and there exists noindependent set S $$ \subseteq $$ V\I with |ID (S)| ≤ r such that|S| >|I ∩ Γ(S)|.In this paper, we demonstrate that for k-claw free graphs ther-locally optimal independent sets is found in polynomial timeand the worst case is bounded by $$\left| {I*} \right| \leqslant \frac{1}{2}\left[ {\frac{1}{{\sum _{i = 1}^r (k - 2)^{i - 1} }} + k - 1} \right]\left| I \right|$$ , where I and I* are a locally optimal and an optimal independent set,respectively. This improves the best published bound by Hochbaum (1983) bynearly a factor of two. The bound is proved by LP duality and complementaryslackness. We provide an efficientO(|V|r+3) algorithm to find an independent set which is notnecessarily r-locally optimal but is guarantteed with the above bound. Wealso present an algorithm to find a r-locally optimal independent set inO(|V|r(k-1)+3) time.