Has anyone seen a NP graph problem like this before?

Question

I have a following graph-based problem:

1. Input: positive integers K and L, undirected graph G
2. I have to choose K vertices from this graph
3. In the path between each pair of chosen K vertices there has to be at least L vertices, i. e. there has to be a "space between" each two of chosen vertices made of at least L vertices.

The above of course may not be possible for a given instance of a problem, then I have to check that. I'm quite sure that this problem is NP or even NP-complete, since it has to do with paths with length constraint. Have you ever met a similar problem? Do you have an idea how to reduce it to some more well-known problem, possibly NP, e. g. vertex cover or graph coloring?

Also, note that my graph is a grid graph, which might not be "full" but a subgraph of a full rectangular grid.

Answer 1

This is known as the distance-$d$ independent set, i.e., you are looking for an independent set of size $k$ where the distance between every two elements in the solution is at least $d$.

The problem is NP-complete even on planar graphs according to [1], but I don't know about its complexity on partial grids.

Regarding reductions, you can probably take the $d$'th power of the graph and find a (distance-1) independent set in that. The claim is that any solution here is a distance-$d$ independent set in the original, but you need to verify this.

---

[1] Eto, Hiroshi, Fengrui Guo, and Eiji Miyano. "Distance-$d$ independent set problems for bipartite and chordal graphs." Journal of Combinatorial Optimization 27, no. 1 (2014): 88-99.

Answer 2

In the special case where $L=1$, this is the maximum independent set problem, which is NP-hard on general graphs. Therefore, your problem is NP-hard on general graphs as well.

You could try to hope for an algorithm that is specific to the class of graphs you have (I think the maximum independent set can be computed efficiently in bipartite graphs, and grid graphs are bipartite, so you could try to generalize that algorithm), or you could try using a standard algorithm for maximum independent set / clique, or you could try using a SAT solver. It should be easy to formulate this as a MaxSAT instance: you have a clause for each pair of vertices that are within distance $L+1$ (or less), and you ask the SAT solver to minimize the number of variables set to true.

Answer 3

Seems like checking if there is a K-vertices subgraph of G that is L- colorable using the rules of the graph coloring problem. I mean if all the K vertices are colored with the same color they satisfy ur condition.

Since Graph coloring in NP-Complete u can verify a given solution in polynomial time.

So maybe, just maybe this a first sight answer, u have to

1-check if ur Graph is L-colorable

2-search for a color with a set of K vertices