Segundo más pequeño

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

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

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

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$

cc.complexity-theory optimization max-flow-min-cut flow-problems 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

esté codificado en unario (y ciertamente para

constante).

ϵ

$\epsilon$

k

$k$

k

$k$

Yuval Filmus

No veo cómo eso ayuda. Imagine una red de ruta que consta de los tres nodos

solo con los dos bordes

. Además, permiten la capacidad de ser

. Claramente, los cortes de corte mínimo

y los segundos cortes de corte más pequeños

s

$s$

v

$v$

t

$t$

(s, v)

$(s,v)$

(v, t)

$(v,t)$

c (s, v) = 1

$c(s,v)=1$

c (v, t) = 2

$c(v,t)=2$

(s, v)

$(s,v)$

. Aumentar las capacidades como describió nuevamente produciría

como corte mínimo con capacidad

. ¿Cómo voy a inferir el segundo corte más pequeño de eso?

(v, t)

$(v,t)$

(s, v)

$(s,v)$

1 + ϵ

$1+\epsilon$

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

iteraciones.

k

$k$

k

$k$

Oliver Witt

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:

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 y el tamaño de la red. Ver: $k$ $k$

HW Hamacher. Un algoritmo para encontrar los mejores cortes en una red. Oper Res. Letón. 1 (5): 186-189, 1982, doi: 10.1016 / 0167-6377 (82) 90037-2 . $(K\cdot n^4)$ $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

-ésimo más pequeño , que como sugiere Kaveh huele más a un problema # P-completo.

k

$k$

k

$k$

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

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

é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.

k

$k$

k

$k$

David Eppstein