Clever Geek Handbook

Find the maximum subset of a tree with a maximum distance of at most K

I ran into a dynamic programming problem in interviews called "Far Vertices".

The problem is this:

You are given a tree with N vertices and N-1 edges. Your task is to mark as few vertices as possible so that the maximum distance between two unmarked vertices will be less than or equal to K. You should write this value on the output. The distance between two vertices i and j is defined as the minimum number of edges you must go in to reach vertex i from vertex j.

I tried to do dfs from each node of the tree to find the maximum connected subset of nodes, so that each pair of subsets did not have a distance greater than K. But I could not determine the state and transitions between states.

Is there anyone who could help me?

Thank.

+3


source to share


2 answers


A few basic things that I can notice (perhaps very obvious to others): 1. There is only one route between two given vertices. 2. The farthest vertices will have only one outgoing edge.

Now to solve the problem.



  • I would start with a set of vertices that have only one edge and call them EDGE [] calculate the distance between vertices in EDGE []. This will give you (EDGE [i], EDGE [j], distance) pairs of values

  • For all pairs of vertices in EDGE with distance> K, DO EDGE [i] .occur ++, EDGE [i] .distance = MAX (EDGE [i]. Distance, distance) EDGE [j] .occur ++, EDGE [j] .distance = MAX (EDGE [j]. Distance, distance)

  • Find the CANDIDATES in EDGE [] that have a maximum (distance) from those marked with a max (meet)

  • Repeat until all pairs of vertex edges have distance less than or equal to K

+2


source


The task is essentially to find the largest subtree of diameter & lt = k and subtract its size from n. You can solve it with DP.

Some helpful notes:

Diameter of the tree embedded in node v (T (v)):

  • 1 if n has no children,
  • max (diameter T (c), height T (c) + 1), if there is one child c,
  • max (max (diameter T (c)) for all children c of v, max (height T (c1) + height T (c2) + 2) for all children c1, c2 of v, c1! = c2)

Since we care about maximizing the tree size and the diameter of the bounding tree, we can flip the above to suggest bounds for each subtree:



  • For any tree rooted at v, the subtree of interest is at most k deep.
  • If n is a node in T (v) and has no children & lt = = k from v, its maximum size is 1.
  • If n has one child c, the maximum size T (n) of diameter <= k is the maximum size T (c) + 1.

Now for the tricky bit. If n has more than one child, we must find all the possible sizes of the tree resulting from allocating the available depth to each child. So let's say we are at depth 3, k = 7, we have 4 depths left. If we have three children, we can allocate all 4 children 1, 3 to child 1 and 1 to child 2, 2 to child 1 and 1 to children 2 and 3, etc. We have to do this carefully, making sure that we don't exceed the diameter k. You can do this with a local DP.

For each node, we want to calculate maxSize (d), which gives the maximum size of the tree embedded in that node, which has a diameter <= k up to depth d. Nodes with 0 and 1 children are easy to figure this out as above (e.g. for one child, v.maxSize (i) = c.maxSize (i-1) + 1, v.maxSize (0) = 1), Nodes with with two or more children, you compute dp [i] [j], which gives the maximum tree size referenced to diameter k, using up to the i-th child spanning up to depth j. Recursion is dp [i] [j] = max (child (i) .maxSize (m - 1) + dp [i - 1] [min (j, k - m)] for m from 1 to j. D [ i] [0] = 1. This suggests that try to give the i-th child from 1 to j depth and give the rest of the available depth to the previous nodes. "The rest of the available depth" is the minimum j, the depth we are working with or k - m, since the depth,the depth given for the child i + given by the rest cannot exceed k. Transfer the values ​​of the last dp row to the maxSize table for this node. using depth limited DFS, it will calculate all required maxSize entries in correct order, and the answer for node v is v.maxSize (k). Then you do this once for each node in the tree, and the answer is the maximum value found.

Sorry for the confusing nature of the explanation. It was difficult for me to think through and difficult to describe. A few simple examples should be clearer to work with. I haven't figured out the complexity, but n is small and it passed all test cases in .5 to 1s in Scala.

+2


source






More articles:


All Articles