Sin duda se puede hacer un algoritmo que lo haga en tiempo polinómico. Así es como puedes hacerlo: primero, resuelve el problema para árboles enraizados. Es decir, suponga que su árbol está rooteado y que su camino tiene que empezar desde el vértice raíz. Si tienes un algoritmo que resuelve el problema para árboles enraizados, entonces puedes encontrar la respuesta al problema original simplemente probando cada vértice como raíz.
En el caso de los árboles enraizados, esto se puede resolver de forma recursiva. No te daré la solución completa (es larga). En su lugar, te daré una pista.
En primer lugar, he aquí cómo sería normalmente el primer intento de solución recursiva. Para un árbol rooteado $T$ con raíz $r$ Llamemos a $f(T)$ la longitud mínima de un camino que comienza en $r$ y visita cada borde tantas veces como sea necesario. Ahora, si suponemos que $f$ puede implementarse como una función recursiva, entonces debería haber una forma de calcular de alguna manera $f(T)$ utilizando valores $f(T_1),\,f(T_2),\,\ldots,\,f(T_k)$ que se calcularon recursivamente para los subárboles $T_i$ cuyas raíces son hijos de $r$ . Pero no hay una forma obvia de hacerlo, y es ahí donde uno suele abandonar el enfoque recursivo.
Pero todavía se puede hacer si se enfoca de forma inteligente, utilizando esta idea: en lugar de calcular sólo $f$ como función recursiva, calcular simultáneamente $f$ y $g$ , donde $g(T)$ es la longitud mínima de un camino que visita cada arista de $T$ la cantidad requerida de veces, comienza en $r$ y también termina en $r$ . Yo digo que $g(T)$ puede calcularse recursivamente a partir de los valores $g(T_i)$ y $f(T)$ también puede calcularse recursivamente a partir de los valores $f(T_i)$ y $g(T_i)$ .
