Encontrar caminos min-max vertex-disjoint con una fuente común en gráficos planos

Dado un gráfico plano no ponderado y una colección de pares de vértices ( es una constante), encuentre caminos de vértice-disjuntos (excepto fuente) de a tales que la longitud del camino más largo se minimiza.$(s,t_1),\dots,(s,t_k)$k s t $k\ge2$$k$$s$$t_i$

Pregunta: ¿Existe un algoritmo de tiempo polinómico para el problema?

Algunos resultados relacionados:

• si no se soluciona, el problema es NP-hard incluso si ;t 1 = ⋯ = t $k$$t_1=\dots=t_k$
• si el gráfico de entrada está ponderado y las fuentes de las rutas no coinciden, es decir, las rutas son el problema es NP-duro incluso para ;$(s_1,t_1),\dots,(s_k,t_k)$$k=2$

• un problema con un objetivo diferente, es decir, minimizar la suma de las longitudes de ruta, es

  • solucionable con el algoritmo de flujo de costo mínimo para fuentes coincidentes;
  • NP-hard para fuentes no coincidentes y general ;$k$
  • abierto para fuentes no coincidentes y constante .$k$

Esto no es exactamente lo que solicitó, pero el problema es NP-completo si k no es una constante sino parte de la entrada.

Esto se sigue de la demostración del Teorema 1 en van der Holst y de Pina [HP02], que dice: dado un grafo planar G , distintos vértices s y t en G , y números enteros positivos k y b , es NP completo para decidir si hay k caminos pairwise internamente vértice-disjuntos entre s y T cada uno de longitud como máximo b .

Tenga en cuenta que el problema en la declaración del Teorema 1 es diferente del suyo en dos aspectos. Una diferencia es, como mencioné, que k se da como parte de la entrada. El otro es que el problema en [HP02] se trata de rutas con puntos finales comunes en lugar de rutas con una fuente común y diferentes sumideros. No sé cómo solucionar la primera diferencia; la diferencia es tan grande que es probable que necesitemos una prueba completamente diferente para arreglar k . Pero al menos sé cómo solucionar la segunda diferencia.

La prueba del Teorema 1 en [HP02] da una reducción de 3SAT. Esta reducción tiene la siguiente propiedad: en la instancia ( G , s , t , k , b ) construida por la reducción, el grado de vértice t siempre es igual a k . Deje que t ₁ , ..., t _k sean los k vecinos de t . Entonces, en lugar de preguntar si hay k pairwise internamente caminos vértice-disjuntos entre s y t Obra cada uno de longitud como máximo b, podemos preguntar igualmente si hay rutas de vértice-disjunta-excepto-fuente por pares P ₁ , ..., P _{k, de} modo que cada P _i sea ​​una ruta entre s y t _i de longitud como máximo b −1.

[HP02] H. van der Holst y JC de Pina. Trayectos disjuntos de longitud en gráficos planos. Matemática Aplicada Discreta , 120 (1–3): 251–261, agosto de 2002. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3