2
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.