## PROBLEM LINK:
## DIFFICULTY:HARD ## PREREQUISITES:Biconnected component, Dijkstra's algorithm ## PROBLEM:Given a weighted undirected graph whose largest biconnected component has at most 9 vertices, find how many degree three subtrees of maximum weight exist, also find this maximum weight. ## QUICK EXPLANATION:First partition the graph into biconnected components. Based on the constraints specified in the problem we can deduce that each component will have 9 or fewer vertices. For each component we can find the number of maximum weight subtrees satisfying a particular degree distribution using an exponential algorithm (more details in the next section). Using this degree distribution, we can combine the subtrees of two components. ## EXPLANATION:We are given a connected weighted undirected graph with some property, and the task is to find its degree three subtree (i.e., each vertex in the induced subtree has degree 3 or less) of maximum weight. Moreover, the problem also requires to find the number of such maximum weighted subtrees. ## Solving the problem for general graphs:Let us first try to solve the problem for general graphs without having any special property. One possibility could be to enumerate all degree three subtrees of the graph and then pick the ones having maximum weight. This approach is however extremely inefficient as the number of degree three subtrees can be as many as O (2 Instead, we categorize the subtrees based on the degree distributions of the nodes, and for each category compute the maximum weight of the subtrees having that fixed degree distribution as well as the number of subtrees with maximum weight. For example, consider the following graph with 5 vertices: The degree distribution of the graph is Now consider the following two subtrees: It can be seen that the degree distribution of both subgraphs is (1, 1, 1, 2, 1, 0). Hence, both subtrees will be in the same category with signature distribution of (1, 1, 1, 2, 1, 0). Note that, we are including all vertices in the degree distribution irrespective of the fact whether it is in the subtree or not. Hence, the degree distribution will always be a N-tuple irrespective of the size of the subtree. (N = number of nodes in the original graph). We can create a directed hyper graph where nodes correspond to the signature degree distribution of the subtrees. There is an edge between from node u to v, if the signature distribution of u and v satisfy the following property: Informally, we can realize it like this: we take a subtree of the original graph and extend it by adding some new nodes into it. All the new nodes are connected to a single node of the original subtree. In this case there will be an hyper edge from the hyper node containing the old subtree to the hyper node containing the new subtree. For example, if we have a subtree Along with the signature degree distribution, each hyper node also contains the maximum weight of all subtrees in it, and the number of subtrees with maximum weight. We can call this maximum weight as the cost of hyper node. The advantage of defining this hyper graph is that now we can iterate through the nodes of this hyper graph in increasing order of cost using Dijkstra's algorithm. The starting hyper nodes in the dijkstra's algorithm will be the ones which contain a single subtree corresponding to an edge of the graph. However, there is one issue: how do we really generate the outgoing edges of a hyper node. If we use the method of expanding subtrees as described above, then we need to know all the subtrees contained in a hyper node, which are too many. In order to avoid this, we split a single hyper node into multiple smaller hyper nodes in such a way that the outgoing edges of a smaller hyper node can be generated without considering all its subtrees. We call these smaller hyper nodes as "mini hyper node". A mini hyper node inherits the signature degree distribution from its originator hyper node. However, it also contains a binary vector of size N, which contains the information that which nodes of the underlying subtrees are still free to connect to outside nodes, and which nodes are already saturated. More formally, if the binary vector of mini hyper node is (1, 0, 1, 1, 0, 0, 0), that means we can expand the subtrees of this mini hyper node only by adding some new nodes and connecting them to any of the nodes 2, 5, 6 or 7, but not to nodes 1, 3 and 4, which are already saturated. It can be observed that using this extra information we can generate the outgoing edges of a mini hyper node without considering all its subtrees. We only need to look at its free vertices (using the binary vector), and the edges which connect these nodes to the nodes not yet in the subtree (the outside nodes are the ones whose entry in the signature distribution is 0). In order to find an outgoing edge of the mini hyper node, one should pick a free vertex, and choose any subset of edges which connect this vertex to the vertices not in the subtree. The signature of the mini hyper node containing this extended subtree can be computed easily. Its binary vector should be the same as the binary vector of source mini hyper node with the exception that the picked vertex of subtree should be now marked as saturated. We can use a specific order in which the free nodes should be picked in order to avoid multiple edges between mini hyper nodes. One strategy could be to always pick the free vertex with smallest index. Since we are interested only in degree 3 subtrees, we will consider only those mini hyper nodes whose signature distributions have all entries smaller than 4.
Number of such mini hyper nodes will be at most (4 However, still this algorithm will not work for the original graph where N can be as large as 100. In the next section, we show how to make use of the property specified in the problem to improve the complexity. Note that, even though this algorithm is exponential, it is much better compared to the naive version of enumerating all degree three subtrees. The following tables shows the number of subtrees and the number of hyper nodes of the graph as N varies (all these numbers are for the worst case scenario, when the underlying graph is a complete graph). -------------------------------------------------------------------------------- | N | Number of subtrees | Number of degree | 4^N | Number of | 8^N | | | | sequences | | hyper nodes | --------------------------------------------------------------------------------- | 2 | 1 | 1 | 16 | 2 | 64 | --------------------------------------------------------------------------------- | 3 | 6 | 6 | 64 | 13 | 512 | --------------------------------------------------------------------------------- | 4 | 34 | 28 | 256 | 68 | 4096 | --------------------------------------------------------------------------------- | 5 | 240 | 120 | 1024 | 331 | 32768 | --------------------------------------------------------------------------------- | 6 | 2205 | 495 | 4096 | 1577 | 262144 | --------------------------------------------------------------------------------- | 7 | 25466 | 2002 | 16384 | 7486 | 2097152 | --------------------------------------------------------------------------------- | 8 | 354956 | 8008 | 65536 | 355 | 16777216 | --------------------------------------------------------------------------------- | 9 | 5793264 | 31824 | 262144 | 169128 | 134217728| --------------------------------------------------------------------------------- ## How to use the property to improve the complexity:The problem has a very specific constraint which says that any subset of 10 or more vertices can be made disconnected by removing a single vertex from the graph. This means that the maximum size of a biconnected component (a subgraph which cannot be disconnected by removing a single vertex) in the graph is 9. There is a fairly standard algorithm which partitions the graph into maximal biconnected components. The biconnected components are connected together by vertices known as articulation points or cut vertices. These cut vertices are the ones whose removal makes the graph disconnected. Two maximal biconnected components can share at most a single vertex, which should be a cut vertex. Hence, if we choose a subtree that contains nodes from two different biconnected components, it must contain all the cut vertices lysing in the path from the nodes of first biconnected component to the nodes of the second biconnected component. This is an important observation because using this we can compute the maximal subtrees of each biconnected component locally and then merge them together. However, we can merge the subtrees of two components only if the two components are connected by a cut vertex and this cut vertex is the part of both subtrees. This is where the algorithm explained in the previous section comes handy, as it tells the maximum weight of a subtree having a fixed degree distribution. During the merging step We can use this degree distribution to ensure that only those subtrees are considered which contain the common cut vertex, i.e., the degree distributions have a nonzero entry for cut vertex node. More formally, we can describe the process like this (which is taken verbatim from Mugurel Ionut Andreica's comments): We will now perform dynamic programming on the block-cut vertex tree. To unify biconnected components and cut vertices we use the term "bag". A biconnected component has multiple vertices in its "bag", while a cut vertex forms a bag with just 1 vertex. Thus, the block-cut vertex tree becomes a tree of bags in which the bags with just 1 node in them are the cut vertices and the other bags are the biconnected components. We will root the tree at a bag corresponding to a cut vertex (for simplicity, in order to avoid the special cases in which no cut vertex exists, we also define node number 1 to be a cut vertex, even if it may not actually be one). For each bag we use the algorithm described in the previous section to compute the following tables: Since size of each biconnected component is at most 9, the exponential algorithm of previous section will fit in time. Once these tables are computed, we can reduce the entries in the table by merging some of them, as we are only interested in the degree distribution of cut vertices. If two entries have the same degree distribution of cut vertices, we can combine them together. After the reduction step we run a knapsack-like dynamic programming for the current bag considering each of its children. Note that for each child we only maintained information for each possible degree values of the cut vertex which it has in common with the current bag (thus, only 4 states per child are needed). We consider each child at a time and combine its 4 states with the states for the current bag, making sure that the total degree of the common cut vertex (which is the sum of its degree in the child and in the current bag) never exceeds 3. The optimal solution is not necessarily found at the root,
as we might expect. Actually, a potential optimal solution needs
to be considered whenever a state may not be extended further up
in the tree: ## Time Complexity:O (N * 8^K), where K is the size of the largest biconnected component. ## AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked
djdolls anton_lunyov ♦♦ |

The most time-intensive part of my algorithm is finding the number of subtrees of maximal cost for every degree distribution, for every biconnected component (of size Let Now let We add one node at a time, in increasing order of ID. For the current node i: 2. Calculate dp[S] for all degree distributions S such that S[i] > 1:This involves selecting two disjoint degree distributions A, B from [0,i), and setting `dp[S] = max(dp[S], dp[A+{i:1}]+dp[B+{i:d-1}])` , where `S=A+B+{i:d}` and 2≤d≤3.This runs in time O(7.^{i})We also track the number of times such maximum-cost trees can be created, as part of the DP. Care must be taken to ensure that every subtree is counted exactly once. For speedups, a degree distribution The overall runtime of all cases 1 and 2 is O(7, respectively. Therefore, worst-case complexity is ^{K})O(7 (can be triggered by a K-clique with edges of cost 0). Among all components, the overall running time of this DP is ^{K})O(C·7 where ^{K})C is the number of biconnected components.The rest of the program (calculating biconnected components, dynamic programming on components, and adding "children" subtrees from different components) runs asymptotically faster (at most O(C·7.^{K})
answered
kevinsogo |

The maximum subtrees for all degree distributions can be found in P.S.)At first we can find all degree distributions as 4-base numbers by iterating over number of vertexes of degree 2 (let it be Now when we have the sorted list of all degree distributions we iterate over it and compute DP for each mask which is the pair This also shows that actually we don't need the list of masks strictly in sorted order. It will be enough for this list to be sorted by sum of degrees in mask. This obviously can be done in Note that this approach can be easily extended to any other restriction on degrees of vertexes. The complexity will be D is the bound on degree. But larger D will require some smart inner DP on aggregating DPs for children biconnected components, while for D = 3 it is easier to hardcode all possibilities.You can check it out my solution for details. P.S. I don't have a proof but numerical experiments and my experience in dealing with such sums shows that F(K) ~ 4^{K} / sqrt(K) * 0.57
answered
anton_lunyov ♦♦ |

@djdolls The link to the practice problem (in the beginning of the post) points to a nonexistent page. Infact this is the case with all the editorials this month.

Fixed for this problem :)