PROBLEM LINK:Author: Kanstantsin Sokal DIFFICULTY:MediumHard PREREQUISITES:DP on trees, graphs PROBLEM:You are given an undirected graph $G$ of $N$ nodes and $M$ edges. It's guaranteed that no multiple edges or selfloops appear in the graph as well as that the graph is connected. There's one more restriction on the graph: any node of $G$ belongs to at most one simple cycle in $G$. Your task is to count the subsets of nodes in $G$, such that the nodes in the subset are connected (you can reach any node of the subset from any other node of the subset only by moving to adjacent nodes that belong to the subset) and contain no more than $K$ nodes. QUICK EXPLANATION:================ For each cycle main node $v$, we define $\text{f}(v, k)$ as the number of subgraphs rooted at node $v$ and having $k$ nodes in it. This $k$ also includes nonmain nodes and not just the nodes in compressed tree. For each nonmain node, we define we define $\text{g}(v, k)$ as the number of subgraphs rooted at node $v$ and having $k$ nodes in it and these subgraphs don't have any of the nodes of $\text{cycle}[v]$. That means, it only depends on the main nodes that come out of node $v$. So, we can recursively define $\text{g}(v, k)$ based on values of $f$. Now, for recursively calculating values of $f$, we consider each subsegment of cycle of main node $v$ and, then for all subsegments, for all nodes in current subsegment calculate number of subgraphs using values of $g$. If such a subsegment has node $v$ in it, then we add the value calculated to $f(v)$. Add to answer the values calculated by considering each subsegment. EXPLANATION:================ To do this, we create one more DP here $\text{dp1}(i, j)$ as number of ways to choose a total of $j$ nodes from subtrees defined by $u_1, u_2, ..., u_i$. The recurrence can be defined as $\text{dp1}(i, j) = \sum_{k=0}^{K} \text{dp1}(i1,jk)*\text{dp}(i, k)$. So, in terms of pseudo code we can write something like:
Hence, our problem is solved. We do something similar in our given graph, but since cycles are involved, we need to do something improvised. You should here notice that if we compress all cycles to form a single node, then our graph is a tree, say $T$. You should also note that nonbridge edges in $G$ are the edges which will be the edges of tree $T$. First, a definitions I'll be using: All other nodes can be called as nonmain nodes. Now, first we parse cycles in graph $G$, which means compressing each cycle to a cycle main node and for each cycle store the vertices in it. Let's denote by $\text{cycle}[v]$ as the cycle id of node $v$. Now, we are going to compute DP on this compressed tree and at the same time also maintain data about the cycles in it. So, we define $\text{f}(v, k)$ for all main nodes $v$, the number of subgraphs rooted at node $v$ and having $k$ nodes in it. This $k$ also includes nonmain nodes and not just the nodes in compressed tree. Now, we cannot just calculate function $f$ recursively using its own definition, we need to also include the fact that main node $v$ is not just a single node but a cycle. So, for nonmain nodes $v$, we define $\text{g}(v, k)$ as the number of subgraphs rooted at node $v$ and having $k$ nodes in it and these subgraphs don't have any of the nodes of $\text{cycle}[v]$. That means, it only depends on the main nodes that come out of node $v$. So, we can recursively define $\text{g}(v, k)$ based on values of $f$. This DP is quite similar to what we discussed in the easier problem. So, in terms of pseudo code we can write:
Now, that we have calculated $g$ array at current main node, lets see how we will calculate $f$ for the current main node again, based on recursive definition. Now, you should notice how we can make subgraphs at a main node. For example, in the following image, the six different color curves denote which nonmain nodes are we going to include in our subgraph at node $v$. So, the different subgraphs we have made are:
You should notice that we are considering all subsegments in cycle of node $v$(because we need subgraph connected) and then for each subsegment we can use $g$ to calculate number of subgraphs which include subtrees of all these nodes. Also, if for a subsegment main node lies in that segment we can use it to calculate $f$ for main node $v$. Lets formalise things a bit. Let's say you are considering subsegment of nodes formed by nodes $u_1, u_2, ..., u_n$. We already have calculated $g(u_i, k)$ for all $i$ and $k$. Now, at this step we'll also be adding the subgraphs caused by this subsegment to our final answer. We define $h(k)$ as number of such subgraphs with $k$ nodes. So, the subgraph we are considering is formed by $S(u_1), S(u_2), ..., S(u_n)$. So, for calculating $h(k+n)$ we assume that we have choosen $a_1, a_2, ..., a_n$ from each of these subtrees, where $a_1 + a_2 + ... + a_n = k$, so to $h(k+n)$, we add $g(u_1, a_1) * g(u_2, a_2) * ... * g(u_n, a_n)$. Now, we should do this for all possible sets of $a_i$. Again, for calculating this we can do very similar to what we did in the easier problem in beginning.
We do the above process for all possible $u_1$ i.e. all possible subsegment starts. You need to take care of a few things:
So, in this way we we'll have iterated over all possible subsegments which can possibly contribute to the answer. Now, we just have to take sum of $\text{ans}[i]$, for all $i \le K$. COMPLEXITY================ AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 Sep '15, 05:06

Comment regarding tester's(@shangjingbo) approach. "The key condition is that every node belongs to at most ONE simple cycle. Besides, the input graph is connected. Assume we are doing DFS on the graph, as it is an undirected graph, there are only several backedges except for the treeedges. Moreover, there will be no intersections between backedges (since the simple cycles have no intersections). Therefore, we can use (node $u$, total number of selected nodes, number of components in subtree $u$, whether $u$ is selected, whether there is a component has a backedge going beyond node $u$) to describe the states. Number of components <= 2, others are all binary indicators. Therefore, the total number of states is $O(N*K)$. There is another dynamic programming among all children of node $u$ for the transition part. Therefore, the total time complexity is $O(N*K^2)$. You can check the details in my submission."
link
This answer is marked "community wiki".
answered 22 Sep '15, 05:13

Admins, codes are not available, please, fix the problem!!! answered 29 Sep '15, 01:09
