Problemas NP-duros en los árboles

47

Varios problemas de optimización que se sabe que son NP-hard en los gráficos generales se pueden resolver trivialmente en tiempo polinómico (algunos incluso en tiempo lineal) cuando el gráfico de entrada es un árbol. Los ejemplos incluyen cobertura mínima de vértice, conjunto independiente máximo, isomorfismo de subgrafo. Mencione algunos problemas de optimización natural que siguen siendo NP-hard en los árboles.

Shiva Kintali
fuente
1
Jukka, es discutible si "community wiki" es necesario aquí. Obviamente, los problemas artificiales con poca relevancia probablemente serán rechazados, de todos modos.
Ryan Williams
1
También me inclino a pensar que CW no es necesario
Suresh Venkat
2
No estoy seguro si se necesita CW. No puedo pensar en ningún problema fuera de mi cabeza. Parece que los carteles deberían ser recompensados ​​por responder esta pregunta.
Robin Kothari
55
Algunos accesos aleatorios de Google de trabajos de investigación que muestran que un problema es NP-duro, incluso si la entrada es un árbol: capacitado de rutas para vehículos , un problema de latencia mínima , programación de llamadas ...
Jukka Suomela
44
Esto no es lo que solicitó, pero vale la pena mencionarlo aquí: hay algunos problemas que son fáciles para los árboles pero difíciles para el ancho de árbol limitado. Por ejemplo, las rutas de borde disjunto (Nishizeki, Vygen, Zhou '01) y la matriz de restricción (McDiarmid, Reed '03).
Diego de Estrada

Respuestas:

23

Puede encontrar ejemplos "naturales" y "bien conocidos" de problemas de gráficos que son difíciles incluso si están restringidos a los árboles de nuestra referencia estándar . Ejemplos:

(Estos se formulan como problemas de árbol, pero puede generalizarlos a gráficos arbitrarios. Luego, las formulaciones anteriores se obtienen como el caso especial cuando restringe su entrada a los árboles).


Una receta más general para generar problemas que son difíciles para los árboles: tome cualquier problema NP-hard relacionado con supersecuencias , supercadenas , subcadenas , etc. Luego, vuelva a interpretar una cadena como un gráfico de ruta etiquetado. Luego plantee la pregunta análoga para gráficos generales (subsecuencia ≈ gráfico menor, subcadena ≈ subgráfico). Y sabemos que el problema es NP-duro incluso en árboles (y en caminos).


También hay muchos problemas que son difíciles para las estrellas ponderadas, por reducción del problema de la suma de subconjuntos. Un ejemplo natural es:

  • TSP con dos viajeros : dado un gráfico de ponderación de borde y un límite W , ¿podemos encontrar dos caminatas cerradas C 1 y C 2 en G de modo que cada caminata tenga un peso total como máximo W , y cada nodo de G esté cubierto por al al menos un paseo?GWC1C2GWG

Nuevamente, es fácil encontrar variaciones del tema.

Jukka Suomela
fuente
Lástima que el compendio ya no se actualice.
Anthony Labarre
¿Qué es un "gráfico de ruta etiquetado"?
David
29

Es NP-complete para determinar si un árbol se puede incrustar en la cuadrícula entera bidimensional, con los vértices del árbol ubicados en puntos de cuadrícula distintos y los bordes del árbol ubicados en los bordes de la cuadrícula.

Véase, por ejemplo, Gregori, IPL 1989 .

David Eppstein
fuente
Entonces, ¿esto implica la dureza del dibujo rectilíneo de los árboles? ¿Hay un grado limitado que conserve la dureza?
Mohammad Al-Turkistany
2
Re el límite de grado: si existe un vértice de grado mayor que cuatro, entonces no es posible la incrustación en la cuadrícula.
David Eppstein
Gracias David, simple de decir pero un problema interesante.
Mohammad Al-Turkistany
Oh, el árbol de entrada también es un árbol binario. ¡Eso es genial!
Cyriac Antony
24

El problema de Group Steiner es un buen ejemplo. La entrada a este problema es un gráfico ponderado de borde no dirigido yk grupos de vértices S 1 , S 2 , ... , S k . El objetivo es encontrar un árbol de peso mínimo que contenga al menos un vértice de cada grupo. Es fácil ver que el problema de Set Cover es un caso especial incluso cuando G es una estrella. Por lo tanto, el problema es difícil de aproximar dentro de un factor O ( log n ) a menos que P = NP. Además, Halperin y Krauthgamer demostraron que es difícil aproximarse al problema dentro de unG=(V,E)S1,S2,,SkO(logn) factor de cualquier fijos ε > 0 algoritmos cuasi-polinomio menos NP ha aleatorios de tiempo (ver el papel para una exposición precisa). Hay unaaproximación O ( log 2 n ) en los árboles por Garg, Konjevod y Ravi.O(log2ϵn)ϵ>0O(log2n)

Chandra Chekuri
fuente
44
Aaah: el látex sin formato !! duele los ojos :)
Suresh Venkat
Bueno, no sé cómo hacer el formato de látex aquí :). Punteros ??
Chandra Chekuri
solo usa $ .. $ como siempre.
Suresh Venkat
ok todo arreglado ahora.
Suresh Venkat
22

Uno de los problemas más difíciles en los árboles es el problema de ancho de banda mínimo. Es duro en árboles de grado máximo 3. También es NP-duro en oruga circular de longitud de pelo 1.NP

Referencias

Michael R. Garey, Ronald L. Graham, David S.Johnson y Donald E. Knuth. Resultados de complejidad para la minimización del ancho de banda. SIAM J. Appl. Math., 34 (3): 477-495, 1978.

Burkhard Monien. El problema de minimización del ancho de banda para las orugas con longitud de cabello 3 es NP-completo. SIAM J. Algebraic Discrete Methods, 7 (4): 505-512, 1986.

W. Unger. La complejidad de la aproximación del problema del ancho de banda. En FOCS, páginas 82–91, 1998

Mohammad Al-Turkistany
fuente
1
La versión corregida del artículo de Unger son los resultados de dureza para aproximar el ancho de banda , Chandan Dubey, Uriel Feige y Walter Unger.
Yuval Filmus
8

Un problema que uno podría pensar que NO sería difícil para los árboles, pero es el problema de la etiqueta congelada en geometría computacional : brevemente, el problema de programar reactivaciones para robots que comienzan con un solo bot despierto, donde makepan es la medida del costo.

Se sabe que es NP-hard en gráficos de estrellas ponderadas. Sin embargo, está abierto si el problema es NP-duro en el avión. Se podría argumentar que la dureza NP no proviene del 'árbol', sino de la 'métrica arbitraria', pero los gráficos de estrellas solo le dan un espacio limitado de métricas.

Suresh Venkat
fuente
8

TV(T)kϕ:V(T){1,,k}Tii+1KK

k

usuario13136
fuente
8

La coloración del imperio es NP-difícil para los árboles.

rsGr(s,r)sCOLrGs

sCOLrs{3,,2r1}s

Jens G.
fuente
6

TSTT1TSTT1T

El problema es NP-hard (en realidad, es difícil de aproximar) solo cuando todos los árboles de entrada tienen un grado ilimitado.

Gianluca Della Vedova
fuente
6

Una coloración armoniosa de un gráfico simple es una coloración de vértice adecuada de tal manera que cada par de colores aparece junto en un borde como máximo. El número cromático armonioso de un gráfico es el menor número de colores en una coloración armoniosa del gráfico. Edwards y McDiarmid demostraron que este problema de encontrar el número cromático armonioso era NP-completo en los árboles . De hecho, también muestran que el problema sigue siendo NP-completo para árboles de radio 3.

Ashutosh Rai
fuente
5

uu

Tenga en cuenta que en el problema de TSP relacionado (y más famoso), el objetivo es minimizar la latencia máxima, en lugar de la media. Creo que el PRT generalmente se considera un problema más complicado (de hecho, el TSP está en P para las métricas del árbol).

La dureza de NP en los árboles se mostró en RA Sitters "El problema de latencia mínima es NP-Hard para árboles pesados", ISCO 2002.

Michael Lampis
fuente
1
Ese es un buen problema!
Tayfun paga el
3

Hay un problema (muy general) que examiné como parte de un proyecto: una variante de este problema sigue siendo NP-hard incluso en gráficos con dos vértices y un solo borde, y una variante diferente es NP-hard en los árboles. Dado que la dureza NP de la primera variante obviamente no se deriva de la forma del gráfico, la segunda es probablemente más interesante.

SCG=(V,E)SVCVSC=sS|s|FfF|f|eEteRC×F(c,f)Rcf

sSAsfAs|f||s|PrGr=(c,f)RcsfAseDer=(c,f)DePre(c,f)De|f|te

Si no necesita que se enruten todas las descargas, sino que intente maximizar la suma de los tamaños de archivo de las descargas que se enrutan, puede reducir fácilmente la suma de subconjuntos a este problema: tiene un único servidor con grandes cantidades de espacio, un cliente único conectado al servidor con un borde con una capacidad igual al valor objetivo de la instancia de suma de subconjuntos y para cada número entero en la instancia de suma de subconjuntos, crea un archivo con el mismo tamaño; el cliente luego desea descargar todos estos archivos.

Una variante (¿mucho?) Más interesante para esta pregunta es el caso de que intente minimizar el número de bordes cuya capacidad se excede; quizás la red en la que estamos trabajando modela los cables de Internet transatlánticos y reemplazar un cable es tan costosa que la diferencia en costo de actualización a un factor dos más rápido y una actualización a un factor tres más rápido es insignificante. También decimos que las ubicaciones de los archivos en los servidores ya están indicadas y no se pueden modificar, por lo que solo analizamos los problemas de enrutamiento.

USP(U)uU

sSusu

La idea es que el cliente necesita los archivos que son únicos para todos los clústeres de servidores, por lo que los bordes que conectan al cliente con los clústeres de servidores ya están en el límite de sus capacidades (sus capacidades son 1, los archivos tienen un tamaño 1). Si el cliente descarga cualquier elemento del universo desde cualquier clúster, el borde que se conecta a ese clúster se sobrecarga. Ya que solo requerimos minimizar el númerode sobrecargas (y no por cuánto excedemos las capacidades), el cliente puede descargar el resto de los elementos del universo alojado en ese clúster de servidores (por lo tanto, el resto de los elementos del subconjunto correspondiente) sin penalización. Por lo tanto, esto corresponde al subconjunto elegido. El cliente quiere descargar todos los archivos en el universo una vez, por lo que el universo estará cubierto, y para minimizar el número de bordes que están sobrecargados, necesitamos minimizar el número de subconjuntos elegidos.

Tenga en cuenta que la construcción anterior produce un gráfico de árbol, por lo que es un ejemplo de un problema NP-difícil en los árboles.

Alex ten Brink
fuente
3

El problema del flujo no divisible. De hecho, UFP es difícil incluso en un solo borde (mochila).

Arindam Pal
fuente
3

G(V,E)NP

Formalmente, el problema es:

ISOMORFISMO DE GRÁFICO PARTICIONADO

T=(V,E)

{E1,E2}ET1=(V,E1)T2=(V,E2)

La columna de completitud NP cita el manuscrito inédito de Graham y Robinson, "Factorización isomorfa IX: incluso árboles".

DS Johnson, La columna de completitud de NP: una guía en curso, Journal of Algorithms 3 (1982), 288–300

Mohammad Al-Turkistany
fuente
2

De alguna manera me perdí el problema del número acromático en la última respuesta, pero este es uno de los problemas más naturales que conozco, que son NP completos en los árboles.

Una coloración completa de un gráfico es una coloración adecuada de modo que haya un borde entre cada par de clases de color. La coloración se puede establecer en contraste con la coloración armoniosa, como una coloración adecuada de modo que cada par de colores aparezca en al menos un borde. Además, puede declararse como un homomorfismo completo (o completo) a una camarilla. El problema del número acromático es un problema de maximización , donde buscamos el mayor número de clases de color en una coloración completa del gráfico.

Yannakakis y Gravil demostraron que este problema es NP-hard en complemento de los gráficos bipartitos . Cairnie y Edwards extendieron ese resultado y demostraron que el problema es NP-completo en los árboles .

Se ha trabajado mucho en este problema en el campo de los Algoritmos de Aproximación [ 3 , 4 , 5 ].

Ashutosh Rai
fuente
2

nknk

usuario1105
fuente
-1

¿Es el circuito SAT en los árboles NPC? Los vértices internos del árbol están etiquetados como puertas OR / AND. Las hojas son entradas. Determine si hay un conjunto satisfactorio de entradas para que el circuito evalúe como Verdadero.

2k1

Chad Brewbaker
fuente
1
Umm, los circuitos que son árboles tienen un nombre: fórmulas. La fórmula SAT es, por supuesto, NP-completa, ya que 3-SAT o incluso CNF-SAT completo son sus casos especiales.
Emil Jeřábek apoya a Monica el
1
¿Cómo es eso? Todas las fórmulas son árboles. Si desea restringir múltiples ocurrencias de variables, esa es una restricción adicional. (También supongo que cuando escribe "entradas", realmente quiere decir "literales", ya que el Circuito SAT con solo AND, OR y literales positivos es trivialmente polinomial-time para empezar).
Emil Jeřábek apoya a Monica
1
((a+b)+c)+d((a+b)+c)+a
1
(pq)p
1
No es un problema de juguete. Esta es la terminología estándar, cuando cuando decimos que un circuito es un árbol, no significa que las variables aparezcan solo una vez. En cualquier caso e independiente de lo que llamamos, el problema que propones es trivial como escribí.
Kaveh