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 se ts as follows. Let S be an independent set and T be a subset of V such that S boolean AND T = 0 and Gamma(S) subset of or equal to T, where Gamma(S) is defined as the neighbor set of S. A minimum dominating set of S in T is defined as T-D(S) subset of or equal to T such that ever y vertex of S is adjacent to a vertex in T-D(S) and T-D(S) has minimum cardinality. An independent set I is called r-locally optimal if it i s maximal and there exists no independent set S subset of or equal to V\I with \I-D(S)\ less than or equal to r such that \S\ > \I boolean A ND Gamma(S)\. In this paper, we demonstrate that for k-claw free graph s the r-locally optimal independent sets is found in polynomial time a nd the worst case is bounded by \I\ less than or equal to 1/2[1/Sigma (l=1)(r)(k - 2)(i-1) + k - 1] \I\, where I and I are a locally optima l and an optimal independent set, respectively. This improves the best published bound by Hochbaum (1983) by nearly a factor of two. The bou nd is proved by LP duality and complementary slackness. We provide an efficient O(\V\(r+3)) algorithm to find an independent set which is no t necessarily r-locally optimal but is guarantteed with the above boun d. We also present an algorithm to find a r-locally optimal independen t set in O(\V\(r(k-1)+3)) time.