Axiomas para los caminos más cortos

Supongamos que tenemos un gráfico ponderado no dirigido (con pesos no negativos). Supongamos que todos los caminos más cortos en son únicos. Supongamos que tenemos estos caminos (secuencias de bordes no ponderados), pero no conocemos sí. ¿Podemos producir cualquier que hubiera dado estos caminos como los más cortos en tiempo polinómico? La versión más débil: ¿podemos decidir en tiempo polinómico si tal existe? $G = (V, E, w)$ $G$ $\binom{n}{2}$ $G$ $G$ $G$

La condición obvia necesaria es la siguiente: para cada par de caminos, su intersección también es un camino. ¿Es esta condición suficiente?

graph-theory co.combinatorics graph-algorithms metrics ilyaraz
fuente

Debo confundirme acerca de la entrada: si en la unión de los caminos más cortos tienes dos vértices

u, v

$u,v$ en un ciclo, entonces hay dos caminos entre ellos (que son necesariamente los más cortos), y uno debe ser más corto que el otro. condición de singularidad

Suresh Venkat

@Suresh: No sé a qué quieres llegar. Si el gráfico G es el gráfico completo, entonces el camino más corto único entre dos vértices es un solo borde, y la unión de todos estos caminos más cortos es el gráfico completo.

Tsuyoshi Ito

Creo que la respuesta es 'no' para reconstruir un gráfico ponderado, ya que si falta algún borde en su entrada, en realidad podría (a) faltar en el gráfico o (b) ser un borde con un peso realmente muy alto. Creo que la versión sin pesas es más interesante. Además, ¿por qué la gráfica que queremos encontrar está ponderada y las rutas que nos dan no están ponderadas?

Artem Kaznatcheev

Sea

H

$H$ la unión de los caminos más cortos. ¿Hay alguna razón por la cual

H

$H$ no sea un gráfico que produzca estos mismos caminos más cortos? o, en otras palabras, ¿no es el caso de que si los caminos más cortos dados no son los más cortos en

H

$H$ , entonces no hay un gráfico para el cual sean los caminos más cortos?

Sasho Nikolov

@SashoNikolov ¿Qué pesos debemos asignar a los bordes?

ilyaraz

Respuestas:

Me topé con esta vieja pregunta mientras realizaba una búsqueda iluminada, y resultó que recientemente recibí respuestas en este documento que también podría compartir. Espero que la combinación de nigromancia de hilos y autopromoción sea perdonable.

¿Podemos producir cualquier G que hubiera dado estos caminos como los más cortos en tiempo polinómico? La versión más débil: ¿podemos decidir en tiempo polinómico si tal G existe?

La respuesta es sí a ambos. El algoritmo de Mohammad definitivamente funciona, pero hay un método más rápido y directo que evita la necesidad de ejecutar oráculos de separación cúbica. Sea un gráfico ponderado auxiliar no dirigido, donde el peso de cada borde es un número entero que indica cuántas de las rutas tomadas en la entrada contienen ese borde. Ahora, considere la instancia de flujo multicommodity capacitado en borde sobre (interpretando los pesos de borde como capacidades) en el que el objetivo es empujar simultáneamente 1 unidad de flujo entre cada par de nodos. Obviamente, esta instancia de flujo MC puede satisfacerse presionando el flujo de forma natural a lo largo de los caminos dados en la entrada. Resulta que uno puede probar que nuestro $H = (V, E, w')$ $e \in E$ $n \choose 2$ $H$ $n \choose 2$ las rutas son rutas más cortas únicas en algunos si y solo si esta es la forma única de satisfacer la instancia de flujo de MC. Podemos probar la unicidad configurando un LP cuyas restricciones son las habituales para la viabilidad del flujo de MC más una determinada función objetivo cuidadosamente elegida, y los pesos de borde de un satisfactorio se pueden extraer del dual de este LP. $G$ $G$

La condición obvia necesaria es la siguiente: para cada par de caminos, su intersección también es un camino. ¿Es esta condición suficiente?

Esta condición a veces se llama "consistencia" (un conjunto de rutas es consistente si la intersección de dos es una subruta de cada una). De lo anterior se deduce que la consistencia no es suficiente. Uno de los dos contraejemplos más pequeños es el siguiente sistema codificado por colores de cuatro rutas en seis nodos:

En otras palabras, no hay forma de asignar pesos a los 8 bordes representados aquí, de modo que todas estas cuatro rutas sean simultáneamente la ruta más corta única entre sus puntos finales. Sin embargo, cualquier par de ellos se cruzan en un solo nodo, por lo que son consistentes (incluso si los completamos con algunas rutas adicionales de la manera correcta para que en total). Hay infinitos contraejemplos como este; Ver el artículo para una caracterización. $n \choose 2$

Otros tres comentarios rápidos sobre todo esto:

Las afirmaciones análogas que podría desear para todos se mantienen bien en la configuración de gráficos dirigidos en lugar de no dirigidos,
Hay una buena interpretación topológica de esta teoría que conduce a algunas ideas e intuiciones adicionales sobre cómo se pueden estructurar los caminos más cortos y únicos, y
Por algunas razones técnicas, la teoría se simplifica convenientemente en la configuración de DAG en lugar de gráficos no dirigidos o dirigidos (cíclicos).

GMB
fuente

Puedes escribir el problema como un LP, ¿no? Para cualquiera de los dos vértices u, v, y cualquier ruta P de u a v, el peso de P es mayor o igual al peso de la ruta más corta dada entre u y v. Estas son todas desigualdades lineales, y aunque hay exponencialmente muchos, el problema de separación está en P (es solo un problema de ruta más corta de todos los pares). Por lo tanto, puede usar el algoritmo elipsoide para resolverlo.

Mohammad
fuente