Inquiry Regarding Implementation of Parameterized Algorithms

[NEERAJ KRISHNA N]

Dear NetworkX Team,

I hope this message finds you well.

I am writing to seek clarification on the absence of exponential time algorithms within the NetworkX library. Specifically, we are interested in understanding why such algorithms have not been incorporated, given their potential importance for certain types of graph problems.

If the primary reason for the exclusion of exponential time algorithms is their inefficiency, we are keen to explore ways to contribute to NetworkX. Our intention is to either:

1. Implement approximate algorithms that operate in polynomial (or parameterized) time. We are considering several options, including:

   • Feedback Vertex Set in Undirected Graphs:

     • 4-Approximation Polynomial Time Algorithm

     • 3-Approximation Polynomial Time Algorithm

     • 2-Approximation Polynomial Time Algorithm

     • FPT Algorithms with 5k * poly(n) Time

     • FPT Algorithms with 4k * poly(n) Time

2. Implement accurate exponential algorithms where polynomial-time solutions are not feasible. For example:

   • Vertex Cover with 1.47k * k3 n * sqrt(m) Time Complexity

We believe that these contributions could significantly enhance the library’s functionality and offer users additional methods for tackling complex graph-related problems.

Could you please provide insights into the current stance on the inclusion of exponential time algorithms in NetworkX? Additionally, we would appreciate any guidance on how best to contribute to NetworkX in this context.

Thank you for your time and consideration. We look forward to your response.

Best regards, Neeraj Krishna N

[Dan Schult]

We do include exponential time algorithms in networkx. Why do you claim we don't? I hope we don't state anything like that in our docs somewhere. In some sense the exponential problems are precisely where algorithm development (via heuristics or whatever) has the biggest payoff.

One aspect of the examples you give is that papers often prove some asymptotic dependence without consideration of the constants involved. I recall "almost linear time" algorithms that have never been implemented in a software library because they are so slow the size has to be bigger than what large computer systems can hold in memory before any speedup is seen.  Theoretical proofs of asymptotic time dependence don't always translate into usable algorithms.

(Also, "exponential time algorithms" is probably a poor term to use as a criteria for inclusion. Most algorithms are likely to be exponential in **some** parameter -- usually not the one the paper is written to consider.) 

In general, inclusion of algorithms to NetworkX requires that someone write the algorithm (in Python) and be sufficiently motivated to include documentation, tests and put it into the form of a pull request on https://github.com/networkx/networkx .   We will help with that process if needed. And partially complete PRs are fine. It gives you feedback during the process of putting it together. You can also open an "Issue" to discuss aspects of the problems and/or to track progress across multiple PRs.

I have not looked at the problems you refer to, but Feedback Vertex Set has a similar goal of identifying cycles (by removing nodes instead of removing edges).  A vertex cover algorithm is as easy as `{u for (u, v) in G.edges}`. But I suspect you are looking for minimum (or maybe minimal?) FVS and VC.  There is nothing blocking inclusion of algorithms such as these from NetworkX. :)

[EVANS SAMUEL BIJU]

Dear NetworkX Team,

I hope this message finds you well! We wanted to kindly follow up on our second pull request for the k_vertex_cover addition to NetworkX (discussion link: #7850). We submitted it with incorporating some of the requested changes- removing inline typing, renaming helper functions with underscores, using nx.bipartite.sets(G), consolidating tests into a single module, and instead of assert we have used NetworkXError where needed.                                                                                                                                                        We have not merged all functions into a single module, to maintain readability.The bipartite-specific function has not been placed in the bipartite subpackage because it primarily checks whether the graph is bipartite and then delegates to built-in methods. Given its minimal scope, we kept it within the main module.
The non-bipartite functions have not been added to covering.py, as that module focuses on edge covering, while our implementation deals with vertex covering. Keeping them separate avoids potential confusion.

We haven’t heard back yet and  if there’s anything we can tweak to improve the implementation, please let us know—we’re happy to iterate.

Thanks again for your time

Best regards,

Neeraj and Evans