Complejidad parametrizada de P a NP-hard y viceversa

60

Estoy buscando ejemplos de problemas parametrizados por un número , donde la dureza del problema no es monotónica en k . La mayoría de los problemas (en mi experiencia) tienen una transición de fase única, por ejemplo, k -SAT tiene una transición de fase única de k { 1 , 2 } (donde el problema está en P) a k 3 (donde el problema es NP- completar). Me interesan los problemas en los que hay transiciones de fase en ambas direcciones (de fácil a difícil y viceversa) a medida que k aumenta.kNkkk{1,2}k3k

Mi pregunta es algo similar a la que se hizo en Hardness Jumps in Computational Complexity , y de hecho algunas de las respuestas allí son relevantes para mi pregunta.

Ejemplos que conozco:

  1. coloración de los gráficos planos: en P excepto cuando k = 3 , donde es NP-completo.kk=3
  2. Árbol Steiner con terminales: en P cuando k = 2 (colapsa a la ruta s - t más corta) y cuando k = n (colapsa a MST), pero NP-hard "en el medio". No sé si estas transiciones de fase son nítidas (por ejemplo, P para k 0 pero NP-duro para k 0 + 1 ). También las transiciones de kkk=2stk=nk0k0+1k dependen del tamaño de la instancia de entrada, a diferencia de mis otros ejemplos.
  3. Contando asignaciones satisfactorias de una fórmula plana módulo : en P cuando n es un número primo de Mersenne n = 2 k - 1 , y # P-complete para la mayoría (?) / Todos los demás valores de n (de Aaron Sterling en este hilo ) . ¡Muchas transiciones de fase!nnn=2k1n
  4. Detección inducida de subgrafía: el problema no está parametrizado por un entero sino por un gráfico. Existen gráficos (donde denota un cierto tipo de relación de subgrafo), para lo cual determinar si H iG para un gráfico dado G está en P para i { 1 , 3 } pero NP- completa para i = 2 . (de Hsien-Chih Chang en el mismo hilo ).H1H2H3HiGGi{1,3}i=2
mikero
fuente
3
Corrección menor re ejemplo (3): el problema está en si n es un número entero de tipo Mersenne, es decir, n = 2 k - 1 para algún número natural k ; n no tiene que ser primo. (Por ejemplo, 2 11 - 1 no es primo). A menos que n sea ​​de esta forma, el problema es # P -completo. Pnn=2k1kn2111nP
Aaron Sterling
Gracias @ Aaron Sterling: he revisado ese ejemplo adecuadamente.
mikero
1
Ejemplo de corrección principal (3): las fórmulas también deben ser monótonas, de lectura doble y tener cláusulas de tamaño , donde n = 2 k - 1 , para ser manejables. Esto fue demostrado por Jin-Yi Cai y Pinyan Lu. No es así como Valiant lo motivó. Fijó el tamaño de la cláusula en 3 y luego varió solo el módulo. Se sabía que era duro en la característica 0. Valiant mostró dureza mod 2 y trazabilidad mod 7. La dureza mod 2 es P = # 2 P dureza, no # P-dureza. No sé qué familia de problemas parametrizados está tratando de describir. kn=2k1P=#2P
Tyson Williams
1
Para obtener más información sobre esto, incluidas las referencias en papel, consulte Holographic_algorithm # History en Wikipedia.
Tyson Williams
Una preocupación en relación con el ejemplo (4): espero que quiere decir que denota G ser una realización de la s -graph H . Pero, ¿cómo podemos decir que theta prism piramide? Tenga en cuenta que estamos hablando de subgrafos inducidos, no de subgrafos. HGGsH
Cyriac Antony

Respuestas:

25

Un campo con mucha no monotonicidad de la complejidad del problema es la prueba de propiedades. Deje que sea ​​el conjunto de todos los gráficos de n -vértices, y llame a P G n una propiedad de gráfico. Un problema genérico es determinar si un gráfico G tiene la propiedad P (es decir, G P ) o está "lejos" de tener la propiedad P en algún sentido. Dependiendo de qué es P y qué tipo de acceso de consulta tiene al gráfico, el problema puede ser bastante difícil.GnnPGnGPGPPP

Pero es fácil ver que el problema no es monótono, ya que si tenemos , el hecho de que P sea ​​fácilmente comprobable no implica que S sea ​​fácilmente comprobable o que T lo sea. SPTPST

Para ver esto, es suficiente observar que y P = son ambos trivialmente comprobables, pero que para algunas propiedades, existen fuertes límites inferiores.P=GnP=

Aaron Roth
fuente
¿Podría mencionar (o señalar) un ejemplo no trivial? Supongo que ya sabes algo. También es interesante si hay transiciones de fase P NP P NP.
Cyriac Antony
20

Para un gráfico dado y un número entero k 1 , la k -ésima potencia de G , denotada por G k , tiene el mismo conjunto de vértices de tal manera que dos vértices distintos son adyacentes en G k si su distancia en G es como máximo k . El problema de la potencia k de la gráfica dividida pregunta si una gráfica dada es la potencia k de la gráfica dividida.Gk1kGGkGkGkkk

vb le
fuente
17

Uno de estos problemas es la coloración de bordes de gráficos planos donde el parámetro es - grado máximo de un gráfico. Cuando Δ = 2 o Δ 7 se conocen algoritmos polinómicos exactos para él ( ver aquí ), mientras que para 3 Δ 6 dichos algoritmos no se conocen y no hay pruebas de dureza NP para estos casos.ΔΔ=2Δ73Δ6

La pregunta relacionada se discute aquí .

Oleksandr Bondarenko
fuente
14

Determinar si un gráfico tiene una camarilla dominante para:G

  • es trivial - la respuesta siempre es 'sí'diam(G)=1
  • es NP-completodiam(G)=2
  • es NP-completodiam(G)=3
  • es trivial - la respuesta siempre es 'no'diam(G)4

El caso se debe a Brandstädt y Kratsch , y el caso d i a m ( G ) = 2 se señala en un artículo mío reciente .diam(G)=3diam(G)=2

Austin Buchanan
fuente
+1 Buena respuesta. ¿Qué es la camarilla dominante?
Mohammad Al-Turkistany
1
Tal como suena: un conjunto dominante que también es una camarilla .
Austin Buchanan
13

¿Es este un ejemplo del fenómeno que estás buscando?

Considere el problema de k-Clique, donde k es el tamaño de la camarilla que estamos buscando. Entonces el problema es "¿Hay una camarilla de tamaño k en el gráfico G en n vértices?"

Para todas las constantes k, el problema está en P. (El algoritmo de fuerza bruta se ejecuta en el tiempo . Para valores grandes de k, por ejemplo valores como n / 2, es NP-completo. Cuando k se acerca mucho a n, como nc para alguna constante c, el problema está en P nuevamente porque podemos buscar en todos los subconjuntos de n vértices de tamaño nc y verificar si alguno de ellos forma una camarilla. (Solo hay O ( n c ) tales subconjuntos, que son polinómicamente grandes cuando c es una constante).O(nk)O(nc)

Robin Kothari
fuente
77
Este fenómeno es solo porque podríamos ver k como min (k, nk), y resolver k-clique o k-indept set (realmente el mismo problema). Si pensamos en 0 <k <= n / 2 por este motivo, la complejidad aumenta estrictamente en k.
Aaron Roth
44
@ Aaron: Me temo que su argumento no es correcto. Encontrar una camarilla de tamaño n − k es muy diferente de encontrar un conjunto independiente de tamaño k. Debes estar confundido por el hecho de que encontrar una camarilla de tamaño k en un gráfico G es equivalente a encontrar un conjunto independiente de tamaño k en el complemento de G.
Tsuyoshi Ito
Tsuyoshi: Sí, por supuesto. Tenía la intención de decir que WLOG, puede suponer k <= n / 2, ya que si no, tome el gráfico del complemento y resuelva el problema para k '= nk. Y, por supuesto, esto destaca que la complejidad está aumentando en k.
Aaron Roth
1
@Aaron: “si no, toma el gráfico del complemento y resuelve el problema para k '= nk”. Esa es exactamente la afirmación incorrecta que estoy tratando de objetar. Permítanme repetir lo que dije: "encontrar una camarilla de tamaño k en un gráfico G es equivalente a encontrar un conjunto independiente de tamaño k en el complemento de G." Encontrar una camarilla de tamaño k en un gráfico G no es equivalente a encontrar una camarilla de tamaño n − k en el complemento de G.
Tsuyoshi Ito
2
Ah, sí. :-) Eso fue una tontería, me retracté de mi objeción. Lo que está sucediendo aquí es solo que Binomial [n, k] = Binomial [n, nk], por lo que el tiempo de ejecución de la búsqueda exhaustiva es monótono aumentando para k <n / 2, y monótono disminuyendo para k> n / 2.
Aaron Roth
12

Aquí hay un ejemplo que podría ser del tipo que estás buscando. Sin embargo, el parámetro no es un entero, es un par de números. (Aunque uno de ellos se puede arreglar para que sea un problema de un parámetro).

El problema es evaluar el polinomio de Tutte de un gráfico G en las coordenadas (x, y). Podemos restringir las coordenadas para que sean enteros. El problema está en P si (x, y) es uno de los puntos (1, 1), (-1, -1), (0, -1), (-1,0) o satisface (x-1 ) (y-1) = 1. De lo contrario, es # P-duro.

Obtuve esto del artículo de Wikipedia sobre el polinomio de Tutte .

Robin Kothari
fuente
12

¿Qué pasa con la cuestión de calcular el permanente de una matriz módulo ? Para k = 2 esto es fácil (ya que permanente = determinante), y Valiant (en " La complejidad de calcular el permanente ") mostró que se puede calcular el módulo 2 d en el tiempo O ( n 4 d - 3 ) para d 2 por Una variante modificada de la eliminación gaussiana. Pero para k, que no es una potencia de 2 , es UP-Hard. kk=22dO(n4d3)d2k2

Kevin Costello
fuente
10

Otro problema con este fenómeno es el problema MINIMO -SPANNER en gráficos divididos.t

Para una constante , un t -spanner de un gráfico conectado G es un subgrafo de expansión conectado H de G de tal manera que para cada par de vértices x e y , la distancia entre x e y en H es como máximo t veces su distancia en G . El problema MINIMO t -SPANNER solicita un t -spanner con un número mínimo de aristas de un gráfico dado.ttGHGxyxyHtGtt

Un gráfico dividido es un gráfico cuyo conjunto de vértices se puede dividir en una camarilla y un conjunto independiente.

En este documento se demostró que MINIMUM 2-SPANNER en gráficos divididos es NP-hard mientras que para cada , MINIMUM t -SPANNER es fácil en gráficos divididos.t3t

usuario13136
fuente
10

Ejemplo bien conocido es colorante -Edge.k

Es decidible en tiempo polinómico si contrario es N P -completo .kΔNP

Para gráficos cúbicos, decidir la existencia de coloración de bordes usando:

  • k=2
  • k=3NP
  • k4

Holyer, Ian (1981), "La integridad de NP del coloreado de bordes", SIAM Journal on Computing 10: 718–720

http://en.wikipedia.org/wiki/Edge_coloring

Mohammad Al-Turkistany
fuente
¿Podría, por favor, agregar una referencia?
Oleksandr Bondarenko
10

nnnn

La prueba ha sido anunciada en este documento .

usuario13136
fuente
6

UV(G)GG[U]GU

Decidir si un gráfico de diámetro 1 tiene un conjunto de corte desconectado es trivial. El problema se vuelve NP-duro en los gráficos de diámetro 2, vea este documento y nuevamente es fácil en los gráficos de diámetro, al menos 3, vea este documento .

usuario13136
fuente