Implicaciones de un problema en XP cuando se parametriza por diámetro

8

Sea un problema de gráfico NP-completo. Supongamos que X es solucionable en tiempo polinómico en gráficos de diámetro acotado. En otras palabras, parametrizado por diámetro está en XP. (Recordemos que un problema está en XP si se puede resolver en tiempo). ¿Esto implica la capacidad de solución en tiempo de XP para otros parámetros interesantes?XXXnorteF(k)

Si es así, ¿hay quizás alguna lista más o menos "estándar" o una red de parámetros y cómo se relacionan documentados en alguna parte?

graph-theory parameterized-complexity fixed-parameter-tractable Juho
fuente

Respuestas:

10

Creo que la Figura 1 (página 4) del documento " Nuevas razas en algoritmos parametrizados " de Komusiewicz y Niedermeier es lo que está buscando.

En particular, estar en XP para el diámetro del parámetro implica estar en XP para los parámetros: conjunto dominante mínimo, conjunto independiente máximo, cobertura mínima de la camarilla, distancia al cograma, distancia al cogrupo, distancia a la camarilla, distancia al clúster, cubierta del vértice, y edición de clústeres.

Capó Edouard
fuente
¡Muchas gracias! Tenía la sensación de haber visto una figura como esta antes, pero no pude localizarla. Es posible que desee notar que se puede agregar "grado promedio" a la figura y conectarlo con una línea a "degeneración".
Juho
1

ISGCI acaba de agregar parámetros recientemente. Todavía están en beta en el momento de la escritura, pero uno podría mirar el diámetro : el conjunto dominante mínimo es un límite superior mínimo, y siguiendo el rastro hacia arriba, encontramos el conjunto independiente máximo, y así sucesivamente.

Hacen referencia, por ejemplo, al manuscrito 2013 de Sorge y Weller, disponible aquí (ver Figura 1).

Juho
fuente