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.

I'd be glad to hear your thoughts about the current idea or your own ideas.

  • Do you mean the input graph is a tree? – xskxzr Jun 15 at 17:21
  • Seems the same as this question, though that answer seems incorrect... – xskxzr Jun 15 at 18:03
  • @xskxzr, yes. The input is a graph which is constrained to be a tree. – blueplusgreen Jun 15 at 19:33
  • 2
    @orlp For a tree, $\Theta(|V|)=\Theta(|E|)=\Theta(|V|+|E|)$. – xskxzr Jun 18 at 8:20
  • 1
    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 at 13:19
up vote 3 down vote accepted
+100

(This answer expands on Albert Hendriks' approach from the comments.)

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 at 4:56
  • How do you transform marked vertices to covered edges? – xskxzr Jun 21 at 6:54
  • 1
    @AlbertHendriks The idea is to support r[0] >= r[1] >= 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[0] >= r[1], r[0] >= x > r[1], and r[0] >= r[1] >= x. In every case, the first two must become the new r[0] and the new r[1], respectively. – Gassa Jun 21 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 at 9:08
  • @Gassa in the discussion with xskxzr, I think you can easily mark the edge belonging to r[0] and return r[1]+1. There may be some corner cases (what if each time r[0]=r[1], 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 at 14:08

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.