Proving NP hardness about graph creation

Question

I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors and number of neighbors of neighbors and so on. I want to create a graph that can satisfy all these constraints (# of constraints is polynomial in n).

I have formulated the problem as an integer programming wherein I am trying to create possible edges by assigning them random variables $z_{i,j} \in $ $\{0, 1\}$ and then trying to satisfy the constraints of # neighbors, # neighbors of neighbors and so on (k steps). However I am not sure if this is a NP complete problem because the constraints are non-linear.

Answer 1

If you are given just the degree sequence (the number of neighbors of each vertex), then the Havel–Hakimi algorithm is an efficient algorithm that constructs a graph conforming to the degree sequence, if possible, and alerts you otherwise. If you are given the second-order degree sequence (the number of vertices at distance 1 and at distance 2 from each vertex), then the problem of determining whether such a graph exists becomes NP-complete, as shown by Erdős and Miklós in their paper Not all simple looking degree sequence problems are easy.