# reduce independent Set into independent Set of distance 4 between all vertices

I want to prove the following problem is NP-complete:

4-Spaced-Set: Assume you have a undirected graph $$G=(V,E)$$, and a positive integer $$k$$. Let's say a set of vertices $$A \subseteq V$$ is $$4$$-spaced if the distance between any two distinct vertices in $$A$$ is at least $$4$$. There is also a vertex weight function $$w:V\to\mathbb{N}$$. The question is whether there exists a $$4$$-spaced subset of the vertices with total weight $$\sum_{u\in S}w(u)\geq k$$?

I want to prove this problem is NP-Complete. I was able to find a YES instance and a certificate which proves it can verified in polynomial time so it is NP. However I am having trouble trying to reduce Independent Set to this problem in order to prove that is NP-Hard as well. Here is my attempt, please let me know what I did wrong, and how to proceed?

Initiliaze a new graph $$G'$$ where you add edges to make sure that no two vertices at a distance less than 4 from each other can be in the same independent set. Start with the original graph G. Add edges between vertices at a distance 2 from each other: For any pair of vertices u,v at a distance 2 from each other, add an edge between u and v. Add edges between vertices at a distance 3 from each other such that for any pair of vertices u,v at a distance 3 from each other, add an edge between u and v. graph $$G′$$ will have an independent set of size k if and only if the original graph G has a 4-spaced set of size k therefore by transitivity of reduction, all problems $$A \in$$ NP reduce to this problem. Therefore this problem is NP-Hard.

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– D.W.
Jul 30 at 17:04