93-03 k-Neighborhood Covering and Independence Problems

DIMACS TR: 93-03

k-Neighborhood Covering and Independence Problems

Authors: Shiow-Fen Hwang and Gerard J. Chang

ABSTRACT
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 chordal graph.

Keywords: k-neighborhood covering, k-neighborhood independence, chordal graph, strongly chordal graph, strong elimination order.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-03.ps

DIMACS Home Page