Given an undirected graph with N vertices and M edges. In how many ways we can choose K vertices, such that after removing them, the graph remains still remains connected? I know we can find Articulation points when k=1, but not able to understand what to do for k>1.
1<= N <=50 , N-1<= M <=(N*(N-1)/2) and 0<= k <=N.
Link to question Link
UPD There was a mistake from my side. There was a typo in the question. I have corrected it now.
We can do something like making a spanning tree for the graph and then removing points who have become leaves in the spanning tree
How we are going to find the number of ways of doing so???
I mean there can be more than 1 way of making a spanning tree.
Just get a subtree of this graph wich contains all vertex doesn't matter bfs tree or dfs tree and in some data structure always carry the leaves of this graph and remove one of them and subtract 1 from k while k > 0 it's obvious that the tree will always remains as a tree and we always have a leaf to delete from just every time you delete a leaf update if a new leaf appears and add it which can be easily done
This solution works in a pretty good order I don't know why 0 < N < 50
Maybe I didn't completely understand the problem
Since I can make different dfs trees with different vertices as roots, it might overshoot the time limit. Time complexity for single tree is O(2^n) as for each leaf node I have the choice of removing it or not.
The question you have linked seems to be asking for number of ways to choose a connected subgraph of size $$$k$$$.
Yeah, there was a typo in the post. I have corrected it now. Please see if you can solve it now.
Also I guess, finding number of ways in which we can get connected graph of size k is same as finding number of ways of removing N-k vertices. Suppose I have a connected graph of size 'N' and I want to find number of connected subgraph of size K, then I have to find number of ways to remove 'N-k' vertices such that after removing them the graph still remains connected?
Correct me if I am wrong. Also is it easier to find the other way round?
You are correct, I just wanted to say that you should state the problem as is. Maybe this direction is the way to think, but maybe it's not.
About the solution, I was thinking about some Meet in the Middle, because $$$N$$$ is upto $$$50$$$. Divide the vertices into two sets of $$$ \le 25 $$$ vertices each. Then, for each group, you can calculate all possibilities in $$$ O(25*2^{25}) $$$. The problem is, how to combine answers for the two groups. You can't directly multiply the ways, because you also need to check if there is an edge between any of the vertices from the left group to any of the vertices of the right group. I think we can do some subset dp for this, but I'm not too sure.
Auto comment: topic has been updated by zoro_2278 (previous revision, new revision, compare).
The statement you linked says that any city is reachable from any city by a unique sequence of cities, which means that the graph is a tree. On the tree the problem "count number of connected subgraphs of size $$$k$$$" can be solved in $$$\mathcal{O}(n^2)$$$ using a knapsack-like subtree dp.
Yeah you are right about the graph being the tree. I guess the question intentionally gave range of 0<=M<=(N*(N-1))/2 to confuse.
Can you explain a bit more about your approach — "count number of connected subgraphs of size n−k" which can be solved in O(n^2) using a knapsack-like subtree dp.
Root the tree arbitrary, then define $$$dp_{i, j} =$$$ number of connected subgraphs rooted at vertex $$$i$$$ of size $$$j$$$.
The transition is to consider children of $$$i$$$ one-by-one and then merge on how many vertices you take from the new child, and from the previous children. It seems like $$$\mathcal{O}(n^3)$$$, but as described in comments of this post, the actual total complexity is $$$\mathcal{O}(n^2)$$$ if you consider only valid values of dp.
I am not clear about the merging part you mentioned.
I tried to implement it but it is getting O(n^5). Please suggest what else I can do.
...
The problem in your code is that you are calculating all the dp values independently, rather than calculating them at once. Try implementing dfs, which at vertex $$$v$$$ computes the whole $$$dp_v$$$ layer, while updating it using all the values of children of $$$v$$$.
Got it thanks!
Hii. I still didn't got the part that how do you combine the answer.
Let's say tree has just 2 nodes.
and a single edge : 1 -> 2
dp[1][1] = 1, dp[1][2] = 1;
dp[2][1] = 1, dp[2][2] = 1;
Now if i say $$$k$$$ = 2. How do you compute the answer? Simply adding dp[i][k] (for 1 <= i <= n) will overcount the number of ways.
I think O(N^4) is fast enough for N = 50.
Wow, what a catch. zoro_2278 this is another reason why you should use the statement as is xD.
insert "you had me in the first half" meme