  We study the Neighbor Aided Network Installation Problem (NANIP) introduced
previously which asks for a minimal cost ordering of the vertices of a graph,
where the cost of visiting a node is a function of the number of neighbors that
have already been visited. This problem has applications in resource management
and disaster recovery. In this paper we analyze the computational hardness of
NANIP. In particular we show that this problem is NP-hard even when restricted
to convex decreasing cost functions, give a linear approximation lower bound
for the greedy algorithm, and prove a general sub-constant approximation lower
bound. Then we give a new integer programming formulation of NANIP and
empirically observe its speedup over the original integer program.
