0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jul 30, 2023 at 17:04

1 Answer 1

Reset to default
2
$\begingroup$

For an input to independent set, subdivide each edge twice, add a new vertex that is incident to every subdivision-vertex.

Now, the distance between two vertices in the new graph is 4 if and only if they correspond to two non-adjacent vertices in the input graph.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Not that it really matters, but isn't it enough to subdivide each edge once? $\endgroup$
    – Highheath
    Commented Jul 30, 2023 at 22:21
  • $\begingroup$ @Highheath indeed it is! Good observation. $\endgroup$
    – John Kemeny
    Commented Jul 31, 2023 at 7:41

Your Answer

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

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