zoro_2278's blog

By zoro_2278, history, 4 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

We can do something like making a spanning tree for the graph and then removing points who have become leaves in the spanning tree

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The question you have linked seems to be asking for number of ways to choose a connected subgraph of size $$$k$$$.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zoro_2278 (previous revision, new revision, compare).

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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$$$.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Got it thanks!

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think O(N^4) is fast enough for N = 50.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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