I've got an interesting graph-theory problem. I am given a tree $T$ with $n$ nodes and a set of edges. $T$ is, of course, undirected. Each edge has weight that indicates how many times (at least) it has to be visited. We are strolling from node to node using edges and the task is to find minimal number of needed steps to satisfy above conditions. I can start from any node.

For example, this tree (edge weight along edge):

Mathematica graphics

we need $8$ steps to walk this tree. That are for example: $4\to5\to6\to5\to3\to5\to3\to2\to1$

I don't know how to approach this algorithm. Is it possible to find this optimal tour or can we find this minimal number not directly?

  • 3
    $\begingroup$ I planted the tree. Please make sure I didn't break your tree. $\endgroup$ – Frenzy Li Nov 25 '12 at 11:49
  • $\begingroup$ @FrenzYDT., thank you! $\endgroup$ – ray Nov 25 '12 at 11:54
  • $\begingroup$ Even if irrelevant, I'm curious how did you deduce that :) $\endgroup$ – ray Nov 25 '12 at 12:10
  • $\begingroup$ @FrenzYDT. Actually, in any tree you can pick an optimal path in such a way that every edge $(a,b)$ is only visited in this fashion ($a \to b \to a \to \ldots$). But it doesn't guarantee that reducing the weight by 2 will reduce the resulting path by 2, because the optimal path can actually visit an edge many more times than is required by its weight. $\endgroup$ – Dan Shved Nov 25 '12 at 12:18
  • 1
    $\begingroup$ @FrenzYDT. That tree looks oddly familiar. Is it generated by Mathematica? $\endgroup$ – Yong Hao Ng Nov 27 '12 at 14:37

You can certainly make an algorithm that will do this in polynomial time. Here is how you can do this: first, solve the problem for rooted trees. That is, suppose that your tree is rooted and that your path has to start from the root vertex. If you have an algorithm that solves the problem for rooted trees, then you can find the answer to the original problem simply by trying every vertex as the root.

For rooted trees this can be solved recursively. I won't give you the entire solution (it's lengthy). Instead, I'll give you a hint.

First of all, here is how the first attempt at a recursive solution would normally go. For a rooted tree $T$ with root $r$, let's call $f(T)$ the minimal length of a path that starts at $r$ and visits every edge as many times as needed. Now, if we suppose that $f$ can be implemented as a recursive function, then there should be a way to somehow calculate $f(T)$ using values $f(T_1),\,f(T_2),\,\ldots,\,f(T_k)$ that were calculated recursively for the subtrees $T_i$ whose roots are children of $r$. But there's no obvious way to do this, and that's where one would usually give up the recursive approach.

But it can still be done if approached wisely, using this idea: instead of calculating only $f$ as a recursive function, calculate simultaneously $f$ and $g$, where $g(T)$ is the minimal length of a path that visits each edge of $T$ the required amount of times, starts at $r$ and also ends at $r$. I say that $g(T)$ can be calculated recursively from values $g(T_i)$, and $f(T)$ can also be calculated recursively from values $f(T_i)$ and $g(T_i)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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