vamaddur's blog

Diameter of a Psuedotree
By vamaddur, history, 7 years ago, In English

I know how to find the diameter of a tree in linear time, prove the validity of the algorithm used to do so (successive BFS's), and prove why it doesn't work for non-tree connected graphs.

However, I need an algorithm/approach that has better complexity than O(N^2) to find the diameter of a relatively large WEIGHTED pseudotree (a tree with one extra edge).

Please help, and thanks in advance!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it
  1. Pseudotree is basically a single cycle with trees attached to its vertexes.
  2. Find the cycle with DFS. You run usual DFS and when it finds edge going to an already visited vertex (and not previous vertex) — here is the cycle.
  3. Decompose pseudo tree in cycle and trees.
  4. Answer either goes through cycle's edges or not. If it does not, it's completely inside some tree. If it does, then it starts in the deepest leaf of one tree and ends in the deepest leaf of another tree.
  5. The first part is the problem you already know how to solve: find diameter of the tree.
  6. The second part is more tricky. It can be reformulated as follows: you have an array of K elements, where ai is the depth of i-th tree. You have to find such i and j that ai + a + j + min(|i - j|, K - |i - j|) is maximized.
  7. The last problem can be solved with improved brute force: run down i and assume that corresponding j can be found on the right of i (i.e. between i + 1 and something like ). Now you have a bunch of requests of the form "find maximal j + aj on this subsegment". It can be solved with arbitrary RMQ solution. That would result if for the whole solution.
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would I decompose the pseudotree cycle into trees?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      After you find the cycle, remove its edges from the graph (e.g. mark its edges are "shall not go here"). You're left with a forest, its components of connectivity are trees growing from the cycle (some trees may be degenerate — i.e. containing a single vertex only).

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        @yeputons I see! Then step 5 is finding the diameter of each tree in the new forest?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, exactly. I'm sorry if that wasn't clear from my initial message.

          → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Nevermind, my solution was wrong.

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Was printing my answer too slow (my english skill is so weak). However, decide to post it.

How does a tree with one extra egde look like? It's a simple cycle with trees rooted at this cycle's nodes. It can be two cases:

1) Simple — diameter lies inside one of this rooted trees. Easy to compute the answer.

2) Main one — diameter enters cycle at vertex u and leaves at v. Then the answer is the shortest of two pathes in cycle between u and v, plus hu, plus hv, where's hu is max height of u's rooted tree.

Let's enumerate nodes in our cycle as 0, 1, ... c - 1 (c — cycle length). Now suppose that diameter enters cycle at node 0. What's the answer in this case? It's h0 + max(h1 + 1, h2 + 2, h3 + 3, ... hx + x) where x is number around and then h0 + max(hx + 1 + (x - 1), hx + 2 + (x - 2), ... hc - 1 + 1).

Let's put values for one half of the cycle (h1 + 1, h2 + 2, ... hx + x) in some data structure (and the second half's values to another copy of this structure). What does change when we switch from node 0 to node 1? We need to remove one value from this structrure (h1 + 1), then decrease all values by 1, add new value (hx + 1 + x) and find maximum of them.

So we need a data structure which provides following operations: add/remove elements, decrease all elements by the same number and get maximum element. It's not hard data structure's task and can be done via simple heap/set with some additional easy manipulations to support decreasing. The key observation is — if all elements are decreased at once — maximum element remains the same, only his value is decreased.

The complexity for each DS operation will be O(log c), so overall complexity will be O(n + c log c). It can be futher reduced to O(1) for operation (and overall O(n)) with using queue that supports its maximum instead of heap/set (because we remove only head elements and add tail ones, not random ones).

P.S. Can you provide a link for this task?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I don't know how to prove this but I heard that the same approach for trees can be used to find the diameter of a tree with an extra edge. (Run BFS from an arbitrary vertex, find the farthest vertex and run BFS from this vertex). This works in O(n). I think I heard about this from tehqin's Algorithms Live.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It definitely does not work by running an ordinary BFS. Would using Dijkstra's algorithm in place of a BFS work? I am not able to prove this case.

    EDIT: The tree is weighted, as now clarified in the original post.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If this pseudotree is unweighted then it should work.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    Counterexample. We start at node 1. Two farthest nodes for it are 3 and 5. We choose 3. For 3 the farthest node is at distance 2. However, diameter is 3 (path from node 2 to node 5).

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    In episode 1, I ask if this algorithm still holds with one extra edge but don't reveal the answer. Finding a counterexample to the problem was the exercise. The two BFS method doesn't even work on unweighted pseudotrees. I plan to cover this problem in a future episode to teach applications of max queue. :)

    I usually use this exercise to argue the two DFS diameter search on trees is unintuitive (until you prove it). At the very least, the two DFS method was unintuitive to me when I was first told it works.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vamaddur (previous revision, new revision, compare).

→ Reply