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.