MumukshTayal
commented
5 months ago @dcoudert I have been preparing the PR for this issue, however, @SandwichGouda seems to have raised a PR in place. However, the code implementation he has added seems very similar to mine with just some very minute modifications (mostly, method names changed). I had also already provided the link to the code implementation github gist (https://gist.github.com/MumukshTayal/279d02dc1188dea55cdad8dfd6335c0e) in the above issue itself (which was added last week). Moreover, I do have some resources which provide the intuition/ high level description for the implemented algorithm.
Besides, based on your provided inputs in the comments to the PR #37806 by @SandwichGouda, there are certain modifications that I have been considering and working on. Allow me some time for that.
dcoudert
dimpase
Problem Description
The goal is to implement a function that determines whether a given graph has a vertex cover of size less than or equal to a user-provided parameter k. This approach utilizes a Fixed Parameter Tractable (FPT) algorithm, which provides better performance compared to finding the exact minimum vertex cover size, especially for smaller values of k.
Proposed Solution
The proposed solution is an implementation of an FPT algorithm for the Vertex Cover problem. The algorithm checks if a graph has a vertex cover of size less than or equal to the user-provided parameter k. It does not return the exact size of the minimum vertex cover. The time complexity of this implementation is O(n^2 * 1.71^k), where n represents the size of the graph. The implementation of the proposed FPT algorithm is available in the following GitHub Gist
Alternatives Considered
Minimum Vertex Cover: The SageMath library already implements an algorithm for finding the minimum vertex cover size. However, this implementation uses Cython, which may outperform the proposed Python implementation in certain cases, particularly when the size of the minimum vertex cover is close to the parameter k.
Additional Information
The FPT approach is generally applicable for relatively smaller values of k, as it converts the problem from an exponential time complexity to a polynomial time complexity by handling the exponential part of the algorithm with the parameter k as O(c^k), where O represents a polynomial multiplied by c^k, and c is a constant.
If the user provides a small value of k and the size of the graph increases from n to 2n vertices, the time complexity of the proposed FPT implementation remains O(c^k), with a slight performance hit due to the polynomial time impact. In contrast, a precise solution providing algorithm may grow from O(c^n) to O*(c^(2n)), an exponential increase.
The proposed FPT implementation may be useful for smaller values of k, as it offers better performance compared to the brute-force solution, while sacrificing the exactness of the minimum vertex cover size.
Is there an existing issue for this?