Given is an undirected graph with $n$ nodes and their $n \times n$ adjacency matrix $A$. How to find all connected subgraphs with $m$ nodes either by brute force or by an effective algorithm?
In case the solution depends strongly on the parameters, the special case of interest is for $n=10000, m=4$.
$\\$
Example for $\bf{n=6, m=4}$
For the graph below with 6 nodes the adjacency matrix is
$A=\begin{pmatrix}
0&1&0&0&0&0\\
1&0&1&0&0&0\\
0&1&0&1&0&1\\
0&0&1&0&1&1\\
0&0&0&1&0&0\\
0&0&1&1&0&0\\
\end{pmatrix}$
In total 5 subgraphs of 4 nodes can be found:
$[1,2,3,4]; [2,3,4,5]; [3,4,5,6]; [2,3,4,6]; [1,2,3,6]$.
Edit
A very fast solution for this problem was given in this post.
Best Answer
Since you can convert an adjacency matrix to adjacency list in $O(n^{2})$ time. We can consider the adjacency list data-structure..
If you want a brute force solution:
Just go over all possible $n\choose m$ cases and check if the sub-graph on those $m$ vertices is connected or not (using BFS/DFS). This would take ${n \choose m} \cdot O(m)$ time.
If you want an efficient solution: Pick a vertex and do the following:
-(assume it is included), After deleting the vertex, recursively solve the problem on its neighbors with $m \gets m-1$ and so on till $m = 0$.
-(assume it is not included), simply delete this vertex.
The complexity actually depends on the type of graph (especially, the degrees of the vertices). For a complete graph, $n \choose m$ is the lower bound, whatever the algorithm may be. Even for a tree, $\Omega(n^{m-1})$ is the lower bound whatever the algorithm may be (consider a star graph).