¿Reducir el flujo máximo a la coincidencia bipartita?

Hay una reducción famosa y elegante del problema de coincidencia bipartita máxima al problema de flujo máximo: creamos una red con un nodo fuente , un nodo terminal t y un nodo para cada elemento que se va a combinar, luego agregamos los bordes apropiados.$s$$t$

Ciertamente, hay una manera de reducir el flujo máximo a la coincidencia bipartita máxima en tiempo polinómico, ya que ambos pueden resolverse individualmente en tiempo polinómico. Sin embargo, ¿existe una reducción "agradable" del tiempo polinómico del flujo máximo (en gráficos generales) a la coincidencia bipartita máxima?

Por extraño que parezca, no se conoce tal reducción. Sin embargo, en un artículo reciente, Madry (FOCS 2013), mostró cómo reducir el flujo máximo en gráficos de capacidad unitaria (logarítmicamente en muchos casos de) coincidencia máxima en gráficos bipartitos.$b$

En caso de que no esté familiarizado con el problema de coincidencia máxima de , esta es una generalización de la coincidencia, definida de la siguiente manera: la entrada es un gráfico (en nuestro caso, un gráfico bipartito), G = ( V , E ) y un conjunto de demandas integrales para cada vértice, con la demanda del vértice v denotada por b v . El objetivo es encontrar un conjunto de aristas S más grande posible, de modo que ningún vértice v tenga más de b v aristas en S incidente en $b$$G=(V,E)$$v$$b_v$$S$$v$$b_v$$S$$v$. Es un ejercicio simple para generalizar la reducción del emparejamiento bipartito a los flujos máximos y mostrar una reducción similar del emparejamiento bipartito a los flujos máximos. (Uno de) el (los) resultado (s) sorprendente (s) del artículo de Madry es que, en cierto sentido, estos problemas son equivalentes, dando una reducción simple que reduce el flujo máximo en gráficos de capacidad unitaria (generalmente, gráficos donde la suma de capacidades, | u | 1 es lineal en el número de aristas, m ) a un problema de coincidencia b en un gráfico con nodos O ( m ) , vértices y suma de demandas.$b$$|u|_1$$m$$b$$O(m)$

Si le interesan los detalles, consulte la sección 3, hasta el Teorema 3.1 y la sección 4 (y la prueba de corrección en el Apéndice C) de la versión ArXiv del documento de Madry, aquí . Si la terminología no es evidente por sí mismo, ver sección 2.5 para un resumen relativo a la equiparación de problema, y tener en cuenta que U $b$$u_e$ es la capacidad del borde en la instancia de flujo máximo original.$e$

Así que aquí hay un intento de responder a su pregunta:

El teorema de Konig sobre emparejamientos bipartitos se probó y, en consecuencia, se redujo utilizando el teorema de Max-Flow Min-Cut. El teorema de Konig establece lo siguiente. Si G es un gráfico bipartito, entonces max {| M | : M es una coincidencia} = min {| C | : C es una portada}. Prueba. La parte max {| M |} ≤ {| C |} es trivial. Supongamos que P y Q son las clases de bipartición de G. Agregamos dos vértices, r y s a G, y arcos rp para cada y qs para cada q ∈ Q , y el borde directo pq de p ∈ P a q ∈ Q . Este es un dígrafo G ∗ . Definimos capacidades u (rp) = 1, u (pq) =$p\in P$$q \in Q$$p\in P$$q\in Q$$G_{∗}$$\infty$$e \in E$$f_{x}$$G_{∗}$$f_{x}$$pq \in M$$G_{∗}$$\cup (Q \cap R)$$|Q \cap R|$y entonces C es una portada de tamaño | M |.

Quiero decir que esto es todo en mi opinión que hiciste en la pregunta y esta es mi respuesta potencial :).