6
$\begingroup$

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?

  • 1
    @FrenzYDT. That tree looks oddly familiar. Is it generated by Mathematica?2012-11-27

1 Answers 1

4

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)$.