0
$\begingroup$

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?
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Apr 21, 2020 at 12:08

1 Answer 1

-1
$\begingroup$

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

$\endgroup$

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.