3
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Can you share the context where you encountered this? Have you tried solving this for special cases of K=1 and K=2? for L=1 and L=2? I think that might give you some hints. See also cs.stackexchange.com/q/11209/755 and cs.stackexchange.com/q/1240/755. $\endgroup$
    – D.W. ♦
    Commented Apr 18, 2020 at 21:14
  • $\begingroup$ @D.W. the graph is a 2D grid graph representing city map with some path constraints (roads, so not all grid is "usable"), where the locations chosen (tiles of the grid are vertices, I place K objects on tiles) have minimal length L between them for business reasons. I'll try the above cases. $\endgroup$
    – qalis
    Commented Apr 18, 2020 at 21:18
  • 1
    $\begingroup$ If you fix $L$ and maximize $K$ then this problem will look like generalized maximal independent set $\endgroup$
    – HEKTO
    Commented Apr 18, 2020 at 21:26
  • $\begingroup$ @HEKTO I'm given fixed L, yes. K is also given, though. This problem is more about deciding whether it's possible for fixed (L, K) rather than maximizing K, although of course maximizing K and checking it with my given K would also give me the answer. It would be more costly though computationally, wouldn't it? $\endgroup$
    – qalis
    Commented Apr 18, 2020 at 21:28
  • $\begingroup$ It's unusual to look for independent set with predefined number of vertices - because it might not exist. However the maximal independent set exists for sure $\endgroup$
    – HEKTO
    Commented Apr 18, 2020 at 21:38

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm sorry, I forgot to state that my graph is not a "full" grid, I've edited the question (I think not all of my graphs will be bipartite in the general case). For L=1 it's an excellent observation, I can really go somewhere with that. I just have to figure how to introduce a minimal length between vertices from the independent set. $\endgroup$
    – qalis
    Commented Apr 18, 2020 at 21:45
  • $\begingroup$ @qalis, a subgraph of a grid should still be bipartite. (You can use a checkerboard pattern.) $\endgroup$
    – D.W. ♦
    Commented Apr 18, 2020 at 23:36
  • $\begingroup$ Yes, of course you're right $\endgroup$
    – qalis
    Commented Apr 19, 2020 at 7:20
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well, it sounds quite reasonable, I'll try it! I have also had another thought: my graph may have disconnected components. How would you go about ensuring that I get one color "most popular" across all components? I mean, for 2 components for example for simple greedy heuristic one component may get mostly one of the L colors (good candidate for color for those K vertices), on the second component other one gets most color and I get no solution. Is there a way I can save from that? $\endgroup$
    – qalis
    Commented Apr 18, 2020 at 21:21
  • $\begingroup$ In ur problem, do u consider independent vertices included in "at least L distance"? I mean maybe it depends on the original practical problem u r solving, does completely not reachable means distance=infinity and thus included in at least L???? $\endgroup$
    – ShAr
    Commented Apr 19, 2020 at 4:27

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.