i.e's blog

Task
By i.e, 4 years ago, In English

I came up with the task but after long unsuccessful thinking I decided to write about it.

You're given a rooted tree which consists of n vertexes. You need to arrange weights from 1 to n-1 (permutation) on edges, so that the maximal distance from root over all vertices will be minimized. Find out this distance.

Can someone provide polynomial solution?

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

»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it

It is trivial case of permutation programming.

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

    can you elaborate on that??

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

      she just means you can check all n! cases.

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

      Permutation programming is indeed like linear programming. It solves systems of linear inequalities with constraint that unknowns must form a permutation of numbers from 1 to n, given we have n unknowns. We can do binary search on answer, let's say current number we check is M. Distance from root to vertex v is a linear function of edge weights. We can construct system of inequalities (distance <= M) check whether it has solutions which are permutations of 1..n — 1. The technique of permutation programming is very complex and advanced and requires knowledge of very abstract and modern mathematics to understand, so I will only leave link to implementation: https://pastebin.com/5iQqJur0

      → Reply
»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Is $$$N!$$$ ok?

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

    dude I suppose it's not polynomial. I can solve it with like O(2^n*n) which is smaller than yours, but it's also not polynomial =(

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Couldn't think of a full solution, but I have an observation that in an optimal construction, it is always possible to assign weights such that the root to leaf path is non-decreasing.

By the way, it can be proven that this problem is strongly NP-hard for a general multiset of n-1 possible edge weights. We may prove it by reduction from 3-partition (split a set of size N into three subsets of size a, b and c such that the sum of elements in all three subsets are equal). We simply try all possible subset sizes (of which there are O(N^2)), and for each a, b, c such that a+b+c=n, we construct a tree with N+1 nodes and three edge-disjoint root-to-leaf paths of length a, b and c respectively.

I'm not sure if there is a general way to 3-partition a permutation in polynomial time (or more generally, k-partition a permutation in polynomial time, if k is treated as a constant). If there is no way to do so, then there is no polynomial solution for this problem. Otherwise, some observation on the nature of permutation from the 3-partition problem may help here.

→ Reply