I need helping solving a reduction problem:

Given a Graph G and a number k, Is there a set V' in V(G) such that |V'| >= k and the dist(u,v) > 2 for all u, v in V'?

Now at first glance this looks like the Independent Set Problem but the distance between 2 nodes should be at least 3, and not 2. Any advice how I would reduce this problem to prove that it is in NPC?

CodePudding user response：

Suppose you're given a regular independent set problem (that is, a graph G and a number k, and asked whether there's a subset of the vertices of G such that all are distance 2 or more apart).

First, if k or k 1 is |V|, just check every possible subgraph. So assume that k 1 < |V|.

If you are given an independent set problem, start by adding a vertex in the middle of every edge. Add one extra vertex *, and join * to each of the other new vertices.

Claim: There's a solution of the problem in the question of size k 1 in this new graph if and only if there's an independent set of size k in the original graph.

For the forwards direction, suppose there's a set of vertices of size k 1 in this new graph such that every pair of vertices is at distance at least 3. Then there can be at most 1 of the new vertices in that set (because they are all distance 1 or 2 from each other), so you have an independent set of size k in the original graph.

For the backwards direction, if there's an independent set of size k in the original graph, then there's a solution of size k 1 in the new graph -- the vertices of the independent set of size k, plus the added vertex of an edge that's not incident to any of the vertices in the independent set (this is why we need k 1 < |V|).

Thus we've shown that if you have a polynomial-time solution to the problem in the question, you can solve the independent set problem also in polynomial time.

That the problem is NP is easy to see -- it's obviously possible to check a subgraph to see if it's a solution in polynomial time.

Thus the problem in the question is NP-complete.