Algoritmo polinómico para problema en gráficos que también puede ser resuelto como un problema de programación lineal.

Question

Tengo una (grafo) gráfico de $G = (V, E)$. Para cada vértice $i \in V$ tenemos un costo asociado $v_i$ y para cada arista $e \in E$ tenemos un premio asociado $x_e$.

Mi problema es encontrar a $W \subseteq V$ que:

1) tiene el máximo valor de $\sum_{e \in E(W)} x_e - \sum_{i \in W} v_i$

2) y contiene un determinado vértice $k$ ($k \in W$, $k$ es conocida a priori).

$E(W)$ son bordes con ambos extremos en $W$.

Edición debido a la pregunta por wece: En mi problema específico, ambos premios y los costos son no negativos ($\mathbb{R}^+$). Sin embargo, el valor de $\sum_{e \in E(W)} x_e - \sum_{i \in W} v_i$ puede muy bien ser negativo.

Este problema puede ser modelado como un entero de un problema de programación cuya matriz de restricciones ya he demostrado ser totalmente unimodular. Así que sé que puede ser resuelto exponencialmente, ya que si voy a resolver sus lineal de relajación voy a llegar a una solución integral y puedo usar una los puntos del interior con el método de complejidad polinomial.

Es este problema conocido? Quiero decir, no tiene un nombre específico en la literatura científica? Estoy tratando de encontrar un algoritmo polinomial para que en lugar de resolver el LP a través de los puntos del interior, alguna idea? Creo (pero puede que esté equivocado) que no podemos usar el max de flujo/min corte algoritmo de aquí.

Gracias.

Answer 1

Primero debemos descartar la $k$. Ya que sabemos que pertenece a $W$ nos puede quitar de la gráfica. También podemos modificar el coste de la vecina de $k$ a fin de tener en cuenta que el premio recibido desde el borde con $k$. Así, el nuevo costo de la $i$$v_i-x_{(k,i)}$. (Observe que si un costo es ahora negativa sabemos que este vértice pertenece a $W$ por lo tanto podemos repetir esto).

Ahora vamos a calcular el conjunto de $W$. Para ello utilizamos varios iteración de un máximo de flujo de algoritmo.

Deje $G=(V,E)$ ser un grafo no dirigido.

Definimos $G_0=(V_0,E_0)$ como:

• $V_0=V\cup E\cup\{s,t\}$
• $E_0=\{(s,e)\mid e\in E\}\cup \{(i,t)\mid i\in V\}\cup \{(e,i)\mid e=(i,i')\}$

Se define la capacidad de $C$ como sigue:

• $C(s,e)=x_e$
• $C(i,t)=v_i$
• $C(e,i)=+\infty$

Ejecutar el máximo flujo de algoritmo. Denotamos $U$ el conjunto de todos los vértices tales que el flujo saliente el vértice es menor que la capacidad de decir, que los $F(i,t)<C(i,t)$.

La idea es que sabemos que $U\cap W=\emptyset$ por lo tanto podemos eliminar los vértices $U$$V$.

Repita la construcción en el gráfico de $G'=(V\setminus U,E(V\setminus U))$, el máximo de flujo y otra vez hasta que todos los vértices $F(i,t)=C(i,t)$. En este punto los vértices de la izquierda son exactamente $W$.

Te dejo la prueba para usted, pero la idea es mostrar que en cada paso se mantienen los vértices de $W$. Esto es cierto porque los bordes de $E(W)$ son suficientes para llenar la capacidad de la $W$ vértices. Esto le da una inclusión, por el otro inclusión se puede proceder por el absurdo, supongamos que el conjunto consigue no maximiza la suma. Usted sabe que el conjunto es mayor que $W$. La razón de la suma de los premios obtenidos por las caras nuevas en comparación con los precios, usted sabe que es positivo puesto que el flujo fue máxima por lo tanto la contradicción.

(Lo siento, es muy tarde y estoy un poco cansado. Espero que mi idea son lo suficientemente claros y que no he cometido un error)