Mostrar cómo resolver el problema de encontrar una arborescencia de coste mínimo en un grafo dirigido en tiempo polinómico.

Question

Dado un grafo dirigido G = (V,E) con un vértice raíz r \in V, una arborescencia es un subconjunto de aristas que contiene un camino dirigido desde la raíz a cada vértice del grafo.

Mostrar cómo resolver el problema de encontrar una arborescencia de coste mínimo en el grafo dirigido en tiempo polinómico.

Answer 1

Considere la posibilidad de representar la búsqueda de una arborescencia como un problema de grupo de flujos. Queremos enviar 1 unidad de flujo a cada vértice de G además de r. También queremos minimizar el peso total de las aristas en las que enviamos algún flujo. El problema se simplifica a $$ minimize \sum\nolimits_{(i,j) \in E} f_{ij}c_{ij} $$ $$ s.t. \space\space\space\space f_{ij}^{k} \le f_{ij} \space\space\space\space for\space all \space k\in V - \{r\} $$ $$ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\Sigma_{j:(r,j) \in E} f_{ij}^{k} = 1 \space\space\space\space for\space all \space k\in V - \{r\} $$ $$ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\Sigma_{i:(i,j) \in E} f_{ij}^{k} = \Sigma_{k:(j,k) \in E} f_{jk}^{k} \space \space\space for\space all \space j,k\in V - \{r\} $$ $$ \space\space\space\space\space\space\space\space\space f_{ij}, f_{ij}^k \ge 0 \space \space\space for\space all \space k\in V - \{r\} $$ Dónde $f_{ij}$ determina si una arista está en la arborescencia y $f^k_{ij}$ es el flujo enviado a lo largo de la arista (i,j) en el flujo hacia k. Como un LP de flujo tiene una solución integral, esto encuentra una arborescencia válida en tiempo poli.