Neighborhood Removal (NR)

Input

An undirected graph $G = (V, E)$ with a numbering on the vertices in $V$, and two designated vertices $u$ and $v$.

Problem

Is vertex $u$ removed before vertex $v$ when the neighborhood removal algorithm is run on $G$?

Definitions

The neighborhood removal algorithm processes maximum degree vertices in the remaining subgraph of $G$ that have the lowest vertex numbers. It iterates through such vertices, deleting them as well as their neighborhoods from the remaining subgraph.

Status

$\P$-complete (Greenlaw [1]).

Remarks

The reduction to show hardness is from OHDVR.

The neighborhood removal algorithm (or a slight variant of it) is used as a subroutine in Wigderson’s heuristic algorithm for the Graph Coloring Problem [2] and also in a heuristic algorithm for the Minimum Vertex Cover Problem (Lingas [3]). In light of the fact that NR is $\P$-complete, it is unlikely that heuristic algorithms using the neighborhood removal algorithm as a subroutine will parallelize well.