sbrandhsn
commented
7 months ago I looked a bit into this and would like to go for the algorithm in https://www.uni-marburg.de/de/fb12/arbeitsgruppen/algorith/paper/enucon.pdf [1] instead. The work you referenced has a time and space complexity of at least O(d^{k-1}) for a graph with max degree d and a subgraph of size k, and appears to require some CSP routines to be implemented (yuck!). The work in [1] has delay complexity O(k^{2}*d). The delay complexity gives a notion of the runtime between the output of two connected subgraphs.
I also found that there seems to be a general framework for such enumeration problems called reverse search - if you think that qiskit/rustworkx would need to solve a lot of enumeration problems in the future, maybe it makes sense to look into reverse search at some point. Reverse search performs worse for the k subconnected subgraphs problem but might be better long-term as it is more general and might be therefore more maintainable.
mtreinish
What is the expected enhancement?
A feature I was wishing rustworkx exposed natively recently was a function that can return all connected subgraphs of a k nodes. It's simple enough to brute force a solution using
rx.is_connected()anditertools.combinations, but doing this natively in rust (and potential in parallel) would be more efficient.Also, I found this paper: https://consystlab.unl.edu/Documents/StudentReports/TR-UNL-CSE-2013-0005.pdf which provides an alternative algorithm for performing this search and we probably should implement for this function as at least an option, if not the sole approach, for solving this problem too.