# Cover k edges to minimize the length of the longest uncovered path in a tree

You are given a tree $G\langle V, E\rangle$ and an integer $k$. The goal is to cover $k$ edges of the graph, to minimize the length of the longest uncovered path in the tree (and to return this path's length)

Constrains: $O(n\log n)$ time and $O(n)$ space.

Now, the scheme of the algorithm is kinda obvious (from the given constrains). We need to priorities the edges and pick the highest $k$-edges (technically, we throw all edges to a priority queue and pick the first $k$)

So, I think, the keys should tell us how centric the edge is.

My first attempt was BFSing the graph from some node and BFSing again from the most distant node of the first scan.

Each node will get two values: distance from the first starting node and distance from the second starting node.

Though, I'm not sure how well this method grasp the notion of centric.

• Do you mean the input graph is a tree? – xskxzr Jun 15 '18 at 17:21
• Seems the same as this question, though that answer seems incorrect... – xskxzr Jun 15 '18 at 18:03
• @xskxzr, yes. The input is a graph which is constrained to be a tree. – blueplusgreen Jun 15 '18 at 19:33
• @orlp For a tree, $\Theta(|V|)=\Theta(|E|)=\Theta(|V|+|E|)$. – xskxzr Jun 18 '18 at 8:20
• Not sure if this is correct. $u$ = length of uncovered path. For a target $u$, we can check in $O(n)$ if we can do it with with $k$ covers. So we have to do a binary search for $u$, which yields $O(n \log n)$ – Albert Hendriks Jun 19 '18 at 13:19

First idea: let us turn the problem around. As stated, we fix the number of covered edges, $k$, and minimize the maximum length of an uncovered path $d(k)$. Instead, let us fix the maximum length of an uncovered path, $d$, and minimize the number of covered edges $k(d)$.

Suppose now we can calculate $k(d)$ in $O(n)$. Then the original problem can be solved in $O(n \log n)$. Indeed, note that both $d(k)$ and $k(d)$ are non-increasing functions. To answer the question "what is $d(k_0)$?", we can find the minimum $d_0$ such that $k(d_0) \le k_0$. And that can be done in $log (n)$ calculations of $k(d)$ by doing a binary search for the right $d$ with the obvious bounds of $[0, n-1]$.

What's left is to, given a fixed value $d$, calculate $k(d)$ in $O(n)$.

Second idea: we can select an arbitrary vertex as the root, run a depth-first search from the root, and make decisions about covering edges in depth-first search order.

Let us visit a vertex $v$ in our depth-first search. We recursively visit all its children in any order. After visiting child $u$, we assume that we have dealt with all uncovered paths longer than $d$ in $u$'s subtree. We also know the length $\mathrm{dfs}(u) \le d$ of the longest uncovered path from $u$ to the vertices of its subtree. The longest uncovered path from $v$ to the vertices of $u$'s subtree has an extra edge $v - u$, so its length is $r = \mathrm{dfs}(u) + 1$.

(I) Obviously, if $r > d$ (it can only be $d + 1$), we have to cover some edge on the long path we found. Since the whole subtree of $u$ is already dealt with, it makes sense to cover an edge which is the closest to the complement of the subtree of $u$ in the whole tree, which is the edge $v - u$.

(II) But there's more to consider. A path can go from the subtree of one of our children, via our vertex $v$, to the subtree of another child. And if such path has length greater than $d$, we have to cover an edge on it.

To find such paths, for our vertex $v$, we store the maximum length of an uncovered path into a child's subtree we have so far. Let this stored length be $s$, initially zero. After each child $u$ we visit, check whether $r + s > d$. If so, let us cover the edge to the longest of $r$ and $s$, so the new maximum length of an uncovered path becomes $s_{\textit{new}} = \min (s_{\textit{old}}, r)$. If $r + s \le d$, we don't yet have to cover anything, and the new maximum length is $s_{\textit{new}} = \max (s_{\textit{old}}, r)$.

Note now that, with such implementation, case (I) is covered by case (II). In particular, if we don't yet store a path in a child's subtree, the stored value just adds a length of $0$.

When we finish visiting all children of $v$, the stored value $s$ is the length of the longest remaining uncovered path from $v$ to the vertices of its subtree. In particular, if $v$ is a leaf, the value $s$ remained zero. We can now return this value as $\mathrm{dfs}(v)$.

The remaining question is, if we don't cover an edge using the algorithm above, could it have helped us later if we had in fact covered it? The answer is no: such a cover could safely be moved at least one step closer to the root of the tree, without altering other covers.

In pseudocode, with a bit more low-level details than the explanation above. Assume the vertices are numbered 0, 1, ..., n-1. We select vertex 0 as the root (recall that the root can be arbitrary), and just call dfs (0, -1).

dfs (v, p):                            // v is current vertex, p is its parent
{s, w} := {0, -1}                  // maximum path of length s into child w's subtree
for u in adjacent[v]:              // all neighbors of v...
if u != p:                     // ...except its parent, if it has one
r := dfs (u, v) + 1
if r + s > d:              // we have to cover the longest...
if r > s:
cover (v, u)
else:
cover (v, w)
{s, w} := {r, u}   // ...and possibly update to shortest
else:
if r > s:
{s, w} := {r, u}   // here, update to longest
return s                           // length of the longest remaining path


As we can see, dfs (v, p) returns the length of the longest uncovered path from $v$ to the vertices of its subtree.

So, we set the value d (to the pseudocode, it acts as a global variable), run dfs, and track the number of covered edges as the total number of calls to the cover function. The cover function may actually record the covered edges if need be, but at the very least, it increases the counter k by 1. If the edges themselves are not needed, we can drop the variable w too, and leave only s from the tuple {s, w}.

For the original problem, do the above in a binary search over the possible values of d to get the full solution.

• Overall the idea looks good, but in the pseudocode I don't understand what you do if r[i] < x. – Albert Hendriks Jun 21 '18 at 4:56
• How do you transform marked vertices to covered edges? – xskxzr Jun 21 '18 at 6:54
• @AlbertHendriks The idea is to support r >= r >= all other. That somewhat lengthy pseudocode does just that. The three cases when inserting x to the stored head of the sorted array r are: x > r >= r, r >= x > r, and r >= r >= x. In every case, the first two must become the new r and the new r, respectively. – Gassa Jun 21 '18 at 9:05
• @xskxzr Gah! I was covering (marking) vertices instead of edges. It may be possible to adjust, but at least not trivially. Anyway, thanks for the catch, I'll try to come up with a fix. – Gassa Jun 21 '18 at 9:08
• @Gassa in the discussion with xskxzr, I think you can easily mark the edge belonging to r and return r+1. There may be some corner cases (what if each time r=r, at some point you may have to mark them both). Also I think every -1 should be replaced with 0. But overall I think this leads to a solution so I upvote it. – Albert Hendriks Jun 21 '18 at 14:08