### zoro_2278's blog

By zoro_2278, history, 2 months ago,

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.

UPD There was a mistake from my side. There was a typo in the question. I have corrected it now.

• +2

 » 2 months ago, # |   +5 We can do something like making a spanning tree for the graph and then removing points who have become leaves in the spanning tree
•  » » 2 months ago, # ^ |   +1 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.
 » 2 months ago, # | ← Rev. 2 →   0 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 doneThis solution works in a pretty good order I don't know why 0 < N < 50Maybe I didn't completely understand the problem
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 The question you have linked seems to be asking for number of ways to choose a connected subgraph of size $k$.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 Auto comment: topic has been updated by zoro_2278 (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   +3 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.
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 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. Code... int dfs(vector adj[],int i,int j,int par){ // dp[i][j] tells number of ways of geting substree of size j rooted at i // sz[i] tells the size of subtree root at i if(dp[i][j]!=-1) return dp[i][j]; int no_of_child=adj[i].size(); int temp_dp[no_of_child][j]; // temp_dp[x][y] stores number // of ways of getting y+1 nodes //with only x children of i taken into considiration. for(int ch=0;ch=cur){ temp_dp[ch][s]=temp_dp[ch-1][s-cur]*dfs(adj,child,cur,i); } } } } } return dp[i][j]=temp_dp[ch][j]; } 
•  » » » » » 2 months ago, # ^ |   +3 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$.
•  » » » » » » 2 months ago, # ^ |   0 Got it thanks!
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 2 months ago, # ^ |   0 I think O(N^4) is fast enough for N = 50.
•  » » 2 months ago, # ^ |   0 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
 » 5 weeks ago, # |   0 has anyone found a solution yet?