I have a following graph-based problem:
- Input: positive integers K and L, undirected graph G
- I have to choose K vertices from this graph
- 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.