Problema mínimo de cobertura de ruta

Estamos trabajando en computadoras distribuidas y se nos ocurrió un problema de complejidad que se reduce a un problema mínimo de cobertura de ruta. Actualmente no sabemos cómo resolverlo. El problema es el siguiente:

Sea un número entero y sea un gráfico que contenga vértices. Rotulamos cada vértice con un par tal que . De aquí en adelante, nombramos vértices usando su etiqueta. El conjunto de aristas en se define de la siguiente manera: . $k$ $Z_k$ $\frac{k(k+1)}{2}$ $(i,j)$ $1 \leq i \leq j \leq k$ $Z_k$ $\{ ((i,j),(i',j')) | i' >i \land j' \geq i \}$

¿Cuál es el camino mínimo que cubre ? $Z_k$

La lectura "On Path Cover Problems in Digraphs and Applications to Program Testing" de Ntafos et al. , hemos visto que la cobertura de ruta mínima es igual al cardinal del mayor conjunto de vértices incomparable. Estábamos pensando en el siguiente conjunto: que tiene un cardenal de . $S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$ $\frac{k^2}{4}-\frac{k}{2}$

Sinceramente,

Pierre

graph-theory co.combinatorics application-of-theory Pierre
fuente

¿debería ser lugar de en la definición de un borde de ?

j^{'} \geq j

$j' \ge j$

j^{'} \geq i

$j' \ge i$

Z_{k}

$Z_k$

Suresh Venkat

Respuestas:

Parece que su gráfico es un DAG cerrado transitivamente, ¿verdad? Si es así (y esto es probablemente una reafirmación de lo que usted dice en su cita de Ntafos et al), el número mínimo de rutas necesarias para cubrir el DAG es solo el número máximo de elementos incomparables por pares; Este es el teorema de Dilworth .

Su ejemplo puede ser lo suficientemente simple como para identificar directamente este conjunto incomparable máximo, pero en general es posible encontrar este conjunto en tiempo polinómico, mediante un algoritmo basado en la correspondencia de gráficos. La sección "Prueba a través del teorema de König" del artículo de Wikipedia sobre el teorema de Dilworth explica cómo.

David Eppstein
fuente