Should I Contribute an Implementation of Parameterized Vertex Cover?

[autumn-traveller]

Hello stdgraph team,

I am looking for interesting project ideas to work on in my free time and think it could be useful for you as well as interesting for me to add an implementation of parameterized vertex cover.

I saw that your algorithms section does not include Vertex Cover, so I would offer to make a PR with an implementation of parameterized vertex cover.

The Vertex Cover problem (VC) is of course NP-complete but when you parameterize it by the maximum size of your desired solution, k nodes, you are able to control the run time, independent of you input size N, through the parameter k.

My proposal:

1. First we use basic kernelization techniques to either reduce the size of the input graph or return failure
2. Then we brute-force a result on the remaining kernel (which has at most k^2 nodes), using basic branching: for each vertex u, either take u into your solution and recurse on k-1, or take the neighbourhood of u (N(u)) into your solution and recurse for k-|N(u)|

This leaves a runtime of O( 2^(2k^2) + V + E )

links:

https://en.wikipedia.org/wiki/Kernelization#Example:_vertex_cover
https://en.wikipedia.org/wiki/Parameterized_complexity

Please let me know what you think- if you would be interested in this, and what level of interest there would be (i.e. "take your time", or "we want it soon").

Best regards,
Nic

[pratzl]

We're trying to keep the number of algorithms constrained at the moment to reflect what we have in the proposal. The API is going through changes and it helps is keep the impact of changes to a minimum.
That doesn't mean in might not be useful in the future. Thanks for your offer.