DIMACS TR: 93-03
k-Neighborhood Covering and Independence Problems
Authors: Shiow-Fen Hwang and Gerard J. Chang
Suppose G=(V,E) is a simple graph and k is a fixed positive integer.
A vertex z k-neighborhood covers an edge (x,y) if d(z,x) <= k and
d(z,y) <= k. A k-neighborhood covering set is a set C of vertices
such that every edge in E is k-neighborhood covered by some vertex in C.
A k-neighborhood independent set is a set of edges in which no two
distinct edges can be k-neighborhood covered by the same vertex in V.
In this paper we first prove that the k-neighborhood covering and the
k-neighborhood independence problems are NP-complete for chordal graphs.
We then present a linear time algorithm for finding a minimum k-neighborhood
covering set and a maximum k-neighborhood independent set of a strongly
Keywords: k-neighborhood covering, k-neighborhood independence, chordal graph,
strongly chordal graph, strong elimination order.
Paper available at:
DIMACS Home Page