For a undirected graph $G$, is there a algorithm that found all sets of nodes that satisfies the rule that: in such a set, any pair of nodes have a distance larger than $N$, where $N$ is a positive number larger than 2.

For a short example, if we have a graph like this:

| | |
| | |

which has nine nodes that are denoted by 1-9. The algorithm should then find such sets:[1,3,5,7,9], [2,4,6,8], [1,6,7], [3,4,9]...,[7,2,9],[1,8,3].


My original description is a bit unclear.

The set must be 'greeding' or 'complete', so that any node that is not in that set must at least be the neighbor (distance = 1) of one node in the set.


For a bit about the problem background. I am generating a lattice model for a material. The base structure I used is a bond network containing 46 atoms that each has 4 neighbours (so the degree of each node is 4). I then substitute some atoms (16 in this case) with another type of atoms. Unfortunately, the new atoms do not like to 'stay together' (distance = 1) as the energy increase would be too high in this case. You can see that this is a special case of the asked question.

Currently, i have my problem partly solved by using a greed search algorithm in together with some random search. However, i still do not know what is the maximum number of atoms we can substitute in this case. My computer program show that this number might be 17 but i am not sure if larger number would be possible.

  • $\begingroup$ Your explanation isn't exactly clear. For example, wouldn't each set that contains exactly one node also satisfy your criterion? ("any pair of nodes has a distance larger than N") $\endgroup$ – Mike Pierce Jan 16 '15 at 2:59
  • $\begingroup$ Edited my question, @mapierce271. $\endgroup$ – Rui Su Jan 16 '15 at 4:53
  • $\begingroup$ By this new description, wouldn't $[1,6,8]$ also be valid set for $N = 2$? $\endgroup$ – Mike Pierce Jan 16 '15 at 5:41
  • $\begingroup$ Yes,what i have given is not complete yet.@mapierce271 $\endgroup$ – Rui Su Jan 16 '15 at 6:12
  • $\begingroup$ For your completeness requirement, must the distance always equal $1$, or should it equal $N-1$? $\endgroup$ – Mike Pierce Jan 16 '15 at 6:56

This is not an answer but an really extended comment.

Seemed interesting to me so worked and discussed a bit on it.

This following question that I describe is at least a part of your question. On first sight looks like an extension (pairwise $N$ distance apart) of the clique problem (N=1). So seemed to be NP Complete but was unable to come up with a proof.

By using subdivisions, for odd $N$ we can prove that it is the maximum clique of the original graph. So NP-Complete by restriction. (Take the graph with a clique with red vertices, now subdivide appropriately by adding $N-1$ blue vertices in each edge. Then you can eliminate cases where your maximal set has red and blue vertices. If you consider only blue vertices then they will be maximal if this properly chosen set is on the edges of the original clique, and of course if you consider only red vertices then the original clique vertices are still in your maximal set.)

But for even $N$ the size of the set is greater than or equal to the maximum degree of the original graph. So my attempt to prove NP-Completeness for all $N$ got foiled.

But I really feel it is NP-Complete, but I don't have a complete proof. Will let you know if something comes up.

| cite | improve this answer | |
  • $\begingroup$ I also feel it like a NPC problem. Would there be some approximate algorithm or at least an method to estimate the lower or upper boundary of the set size? $\endgroup$ – Rui Su Jan 16 '15 at 16:48
  • $\begingroup$ I'm also pretty sure this is NP-Complete, but rather because of the largest independent set problem. When $N = 1$, all sets in the solution are actually independent sets. And the solution includes the largest independent set. So if you could solve this problem in polynomial time, you'd be able to find a largest independent set in polynomial time. $\endgroup$ – Manuel Lafond Jan 16 '15 at 17:52
  • $\begingroup$ @RuiSu I have no idea on approximate algorithms, but something might be done if you add some specifics about the graph. $\endgroup$ – user67773 Jan 17 '15 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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