Segundo más pequeño

13

¿Se sabe algo sobre el segundo corte - t más pequeño en una red de flujo? O, más en general, sobre este problema:st

Entrada: una red y un número k , todo en binario. Salida: A k ésimo más pequeño s - t corte.Nk
kst

Un ésimo corte s - t más pequeño ( S , T ) es cualquier corte s - t , de modo que haya exactamente k - 1 corte s - t cuyas capacidadeskst(S,T)stk1 st

  • son pares y diferentes
  • verdaderamente más pequeño que la capacidad de .(S,T)

Me gustaría saber cómo se puede calcular y si esto se puede hacer de manera eficiente en el caso de .k=1

Oliver Witt
fuente
Puede encontrar el segundo corte más pequeño agregando peso a todos los bordes en el corte más pequeño y luego calculando el nuevo corte más pequeño. Esto probablemente funciona siempre que k esté codificado en unario (y ciertamente para k constante). ϵkk
Yuval Filmus
2
No veo cómo eso ayuda. Imagine una red de ruta que consta de los tres nodos , v , t solo con los dos bordes ( s , v ) y ( v , t ) . Además, permiten la capacidad de ser c ( s , v ) = 1 y c ( v , t ) = 2 . Claramente, los cortes de corte mínimo ( s , v ) y los segundos cortes de corte más pequeños ( v ,svt(s,v)(v,t)c(s,v)=1c(v,t)=2(s,v) . Aumentar las capacidades como describió nuevamente produciría ( s , v ) como corte mínimo con capacidad 1 + ϵ . ¿Cómo voy a inferir el segundo corte más pequeño de eso? (v,t)(s,v)1+ϵ
Oliver Witt
Agregar un límite inferior en la tapa de corte es una desigualdad lineal, solo agregue un épsilon más grande que la tapa de min y ejecute LP. Puedes repetirlo k veces para obtener lo que quieres. Esto probablemente se puede volver a lanzar como una modificación en la red pero no lo he resuelto.
Kaveh
Veo cómo funciona si está en codificación unaria. ¿Qué pasa si es binario? En este caso, la modificación de la red no se puede hacer en k iteraciones. kk
Oliver Witt
1
Dudo que haya una solución fácil si k es binario. Podemos verificar si hay un corte de la tapa c como describí. Me parece que esencialmente cuenta el número de posibles c, podría proporcionarse para relacionar el conteo del número de coincidencias y probablemente # P-completo. (Esto es solo mi intuición, no una discusión.)
Kaveh

Respuestas:

7

El segundo corte más pequeño, y más generalmente los cortes más pequeños, se pueden encontrar en el tiempo polinomio en k y el tamaño de la red. Ver:kk

HW Hamacher. Un algoritmo para encontrar los k mejores cortes en una red. Oper Res. Letón. 1 (5): 186-189, 1982, doi: 10.1016 / 0167-6377 (82) 90037-2 .(Kn4)k

HW Hamacher, J.-C. Picard y M. Queyranne. Al encontrar los mejores cortes de en una red. Oper Res. Letón. 2 (6): 303-305, 1984, doi: 10.1016 / 0167-6377 (84) 90083-X .K

HW Hamacher y M. Queyranne. mejores soluciones para problemas de optimización combinatoria. Ana. Oper Res. 4 (1–4): 123–143, 1985, doi: 10.1007 / BF02022039 .K

David Eppstein
fuente
¿No permiten estos pesos iguales entre los mejores ? La pregunta parece ser acerca del peso k -ésimo más pequeño , que como sugiere Kaveh huele más a un problema # P-completo. kk
András Salamon
También lo entiendo así: se permiten pesos iguales. Esto parece no responder a la pregunta. Sin embargo, no tenía conocimiento de estos documentos, gracias por eso.
Oliver Witt
1
La pregunta está mal formulada, porque pide una cosa (el ésimo más pequeño corte) y luego añade una restricción que convierte la cuestión en otra cosa (el k ésimo más pequeño corte de peso distinta). Estoy de acuerdo en que es probable que la versión de peso distintivo del problema sea $ P-completa. kk
David Eppstein