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?