Solving distance-d independent set in a simple way I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). So far I have:


Input: undirected planar grid graph $G$, which might not be "full", but be  a subgraph of a full rectangular grid. Also, a natural numbers K (size of independent set) and L (distance).
Represent graph as a adjacency list (or dictionary of adjacency sets, it should be more efficient), since it's sparse (property of planar grid graphs).
Calculate $G^L$ (graph power) with BFS - $O(V*E)$ (complexity explanation)
Solve independent set problem.


The last one has at least a few solutions:


Find independent set with brute force - $O(2^V * V^2)$
Calculate complement of $G$ in polynomial time (I think $O(V+E)$, but I'm not sure) and check if it contains a clique of size $K$, e. g. with brute force, which for fixed K is polynomial - $O(V^K * K^2)$
Since Independent Set and Vertex Cover problems are complementary, find Vertex Cover of size $V - K$; there exists simple algorithm with complexity $O(1.47^{VC size}$) - $O(1.47^{V - K})$


My questions (simple = understandable and "code-able" in less than 1 day for an undergraduate student):


Am I missing something here altogether and should I go other route, without calculating $G^L$, e. g. vertex coloring?
Is there a simple direct independent set algorithm better than brute force?
Am I right that VC is straight up better than brute force clique here?
Wikipedia article on clique problem states that maximum clique can be found by simple enumeration in $O(1.4422^n)$. For my fixed size k, can this bound be tightened? If so, how should I modify the clique enumeration algorithm? Or is there a simpler way?
I'm sorry although I prefer to think of simple answers, ur Q triggers in my mind addressing other problems (a level of a research topic not an under graduate task)

Anyways, here is what popped up in my mind just incase u find something inspiring in them

-About the Kth Largest Subset problem http://dx.doi.org/10.1016/j.ipl.2015.09.015

-About Goemetric Set Packing problem 
(I myself didn't study it a lot, but read some papers about it when someone suggested it to me. I did not use it in my work, but the way u r trying to describe ur problem tells it has a Goemetric landscape nature so maybe it will be useful for u) 

https://www.sciencedirect.com/science/article/pii/S0925772112000740

https://slideplayer.com/slide/4514539/

I have more resources if u need so

. 

Finally, u may search for exact MWIS algorithms and u'll find a lot. Here is one paper
"Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs", Sebastian Lamm
, Christian Schulz, Darren Strash, Robert Williger, Huashuo Zhangk. 
arXiv:1810.10834v1 [cs.DS] 25 Oct 2018