Problemas que son fáciles en gráficos no ponderados, pero difíciles para gráficos ponderados

Muchos problemas de gráficos algorítmicos se pueden resolver en tiempo polinómico tanto en gráficos no ponderados como ponderados. Algunos ejemplos son la ruta más corta, el árbol de expansión mínimo, la ruta más larga (en gráficos acíclicos dirigidos), flujo máximo, corte mínimo, coincidencia máxima, arborescencia óptima, ciertos problemas de subgrafo más densos, cortes directos disjuntos máximos, camarilla máxima en ciertas clases de gráficos, máximo independiente establecido en ciertas clases de gráficos, varios problemas de ruta máxima disjunta, etc.

Sin embargo, hay algunos (aunque probablemente significativamente menos) problemas que se pueden resolver en tiempo polinómico en el caso no ponderado , pero se vuelven difíciles (o tienen estado abierto) en el caso ponderado . Aquí hay dos ejemplos:

1. Dado el gráfico completo -vertex, y un entero k ≥ 1 , encuentre una subgrafía de conexión k que abarque con el mínimo número posible de aristas. Esto se puede resolver en tiempo polinómico, utilizando un teorema de F. Harary, que indica la estructura de los gráficos óptimos. Por otro lado, si los bordes están ponderados, entonces encontrar el peso mínimo del subgrafo de conexión conectado k es N P- duro.$n$$k\geq 1$$k$$k$$NP$

2. Un artículo reciente (diciembre de 2012) de S. Chechik, MP Johnson, M. Parter y D. Peleg (ver http://arxiv.org/pdf/1212.6176v1.pdf ) considera, entre otras cosas, un problema de ruta que llame a la ruta de exposición mínima. Aquí se busca una ruta entre dos nodos especificados, de modo que el número de nodos en la ruta, más el número de nodos que tienen un vecino en la ruta es mínimo. Demuestran que en los gráficos de grados acotados esto se puede resolver en tiempo polinómico para el caso no ponderado, pero se convierte en duro en el caso ponderado, incluso con el grado 4 (Nota: la referencia se encontró como respuesta a la pregunta ¿Qué? Cuál es la complejidad de este problema de ruta? )$NP$

¿Cuáles son algunos otros problemas interesantes de esta naturaleza, es decir, cuando cambiar a la versión ponderada provoca un "salto de complejidad"?

En el mundo de los algoritmos de aproximación existe el problema de la cubierta de vértices capacitados. Dado y capacidades enteras c ( v ) para cada v ∈ V, el objetivo es encontrar una cubierta de vértice de tamaño mínimo para G donde el número de bordes cubiertos por v sea ​​como máximo c ( v ) . Este problema tiene una aproximación de factor constante en el caso no ponderado (es decir, queremos minimizar el tamaño de la cubierta del vértice) mientras es Ω ( log n ) -duro (a menos que$G=(V,E)$$c(v)$$v \in V$$G$$v$$c(v)$$\Omega(\log n)$ ) en el caso ponderado (cada vértice tiene un peso w ( v ) y queremos minimizar el peso de la cubierta).$P = NP$$w(v)$

Mi ejemplo favorito es el problema de dominación independiente (dado el gráfico y el entero k , ¿ tiene G un conjunto independiente máximo de inclusión de, como máximo, k vértices?). Por un buen resultado debido a Martin Farber ( ver aquí ), la versión no ponderada es polinomialmente solucionable en gráficos cordales. Gerard Chang demuestra que la versión ponderada es NP-complete para gráficos cordales ( ver aquí ).$G$$k$$G$$k$

El problema de coincidencia perfecta en los gráficos bipartitos está en mientras que la coincidencia perfecta de peso exacto del gráfico bipartito es N P -Completo .$P$$NP$

Siguiendo la respuesta de Mohammad Al-Turkistany, parece que muchos de los problemas no ponderados solucionables en tiempo polinomial podrían convertirse en completos en el caso ponderado, si preguntamos si hay una solución que tenga exactamente un peso dado. La razón es que esto puede permitir codificar el problema de suma de subconjuntos en la tarea considerada.$NP$

Por ejemplo, en el caso de la coincidencia perfecta de peso exacto, podemos tomar un gráfico bipartito completo como entrada, asignando pesos dados a los bordes de una coincidencia particular, y peso 0 a todos los demás bordes. Es fácil ver que este grafo ponderado tiene una correspondencia perfecta de peso exactamente si y sólo si existe un subconjunto de los pesos que resume exactamente a W . (Si hay un subconjunto de este tipo, entonces podemos tomar los bordes correspondientes de la coincidencia fija, y extenderlo a una coincidencia perfecta con los bordes de peso 0, usando que es un gráfico bipartito completo). Creo, un truco simple similar también puede funcionar para otros problemas.$W$$W$

El Equilibrio de gráficos (también conocido como Orientación mínima de salida) es otro ejemplo de este fenómeno. En este problema, se nos da un gráfico ponderado de borde no dirigido. El objetivo es orientar los bordes de manera que se minimice el grado máximo de salida del dígrafo resultante (ponderado).

El problema a menudo está motivado por un escenario de programación. Imagine que cada vértice es un procesador y cada borde es un trabajo que solo se puede ejecutar en uno de sus dos puntos finales. El peso de una arista es la longitud del trabajo correspondiente y el objetivo es minimizar el makepan.

El problema es NP-hard y APX-hard, incluso si todos los pesos son 1 o 2 (ver Ebenlendr et al. "Balanceo de gráficos: un caso especial de programación de máquinas paralelas no relacionadas" en SODA 2008). Sin embargo, está en P para gráficos no ponderados (ver Asahiro et al. "Clases de gráficos y la complejidad de la orientación del gráfico que minimiza el grado máximo ponderado" en CATS 2008).

Tal vez este es solo un ejemplo trivial y puede considerarlo un caso degenerado, pero el primer ejemplo que se me ocurrió es el Problema del vendedor ambulante (donde generalmente se supone que el gráfico está completo). Tenga en cuenta que la versión no ponderada es Hamiltonian Cycle, que es trivial para gráficos completos.

Encontrar la ruta de costo mínimo bajo restricción de retraso (también conocido como el problema de la ruta más corta restringida) parece encajar aquí.

$G=(V,E)$$d:V\to\mathbb {N}^+$$c:\to\mathbb {N}^+$$D\in \mathbb {N}^+$$s,t\in V$

$s-t$$D$

$\forall v\in V:d(v) =1$$hop-count$

Si el problema se pondera, se convierte en la ruta más corta restringida , que se sabe que es NP completa incluso en DAG.

El problema Local Max Cut con el entorno FLIP es PLS completo en gráficos generales ponderados de enteros.

AA Schaeffer y M. Yannakakis. (1991) Problemas de búsqueda local simples que son difíciles de resolver. SIAM Journal on Computing, 20 (1): 56-87.

Sin embargo, si el mayor peso es polinómico en el tamaño del gráfico, las mejoras locales al potencial (peso de un corte) convergerán en el tiempo polinómico, ya que cada mejora aumentará la función potencial en al menos uno y la función potencial está polinomialmente delimitado. (Con los pesos generales, encontrar una solución accesible mediante mejoras locales a partir de un corte de inicio específico es completo para PSPACE).

Algo similar ocurre también en otros "juegos potenciales".

El vendedor ambulante está abierto en los gráficos de cuadrícula vendidos, pero se sabe que el ciclo de Hamilton (la variante no ponderada) es polinomial.

Discusión de ambos sobre el proyecto de problemas abiertos:

http://cs.smith.edu/~orourke/TOPP/P54.html

En 2K_1-free El corte máximo es polinómico y el corte máximo ponderado es NP-completo.