Approximating weighted neighborhood independent sets

Abstract

A neighborhood independent set (NI-set) is a subset of edges in a graph such that the closed neighborhood of any vertex contains at most one edge of the subset. Finding a maximum cardinality NI-set is an NP-complete problem. We consider the weighted version of this problem. For general graphs we give an algorithm with approximation ratio Δ, and for diamond-free graphs we give a ratio , where Δ is the maximum degree of the input graph. Furthermore, we show that the problem is polynomially solvable on cographs. Finally, we give a tight upper bound on the cardinality of a NI-set on regular graphs.