# 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:

1. 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).
2. 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).
3. Calculate $$G^L$$ (graph power) with BFS - $$O(V*E)$$ (complexity explanation)
4. Solve independent set problem.

The last one has at least a few solutions:

1. Find independent set with brute force - $$O(2^V * V^2)$$
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)$$
3. 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):

1. Am I missing something here altogether and should I go other route, without calculating $$G^L$$, e. g. vertex coloring?
2. Is there a simple direct independent set algorithm better than brute force?
3. Am I right that VC is straight up better than brute force clique here?
4. 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?
• The kth power of a degenerate graph of maximum degree Δ is itself <Δ^k degenerate. Hence you can look for independent set in degenerate graphs. I believe this problem admits a linear kernel in d-degenerate graphs, so you could look into FPT algorithms. Apr 21 '20 at 12:08

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