expansión lemma-variaciones y aplicaciones a preprocesamiento de tiempo polinómico
Autores: Jacob, Ashwin; Majumdar, Diptapriyo; Raman, Venkatesh
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
expansión lemma-variaciones y aplicaciones a preprocesamiento de tiempo polinómico
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Núcleo
Tratable de parámetro fijo
Lema de expansión
De tamaño polinomial
Límites inferiores
óptimo asintóticamente
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 41
Citaciones: Sin citaciones
En la complejidad parametrizada, es bien conocido que un problema parametrizado es tratable por parámetro fijo si y solo si tiene un núcleo: una instancia equivalente a la instancia de entrada, cuyo tamaño es solo una función del parámetro. El tamaño del núcleo puede ser exponencial o peor, lo que resulta en una búsqueda de problemas tratables por parámetro fijo con núcleos de tamaño polinomial. Los avances en maquinaria (mostrando límites inferiores para los tamaños de los núcleos) han llevado a los investigadores a cuestionar cuáles son los tamaños óptimos asintóticamente para los núcleos de problemas tratables por parámetro fijo. En este artículo, hicimos un estudio de una herramienta llamada lema de expansión que ayuda a reducir el tamaño del núcleo. Su origen temprano fue en forma de descomposición de coronas, es decir, para obtener el núcleo lineal del problema; el lema específico fue identificado como la herramienta detrás del núcleo óptimo para el problema del conjunto de vértices de retroalimentación no dirigida. Desde entonces, se han descubierto varias variaciones y extensiones de la herramienta. Las estudiamos junto con sus aplicaciones en este artículo.
Descripción
En la complejidad parametrizada, es bien conocido que un problema parametrizado es tratable por parámetro fijo si y solo si tiene un núcleo: una instancia equivalente a la instancia de entrada, cuyo tamaño es solo una función del parámetro. El tamaño del núcleo puede ser exponencial o peor, lo que resulta en una búsqueda de problemas tratables por parámetro fijo con núcleos de tamaño polinomial. Los avances en maquinaria (mostrando límites inferiores para los tamaños de los núcleos) han llevado a los investigadores a cuestionar cuáles son los tamaños óptimos asintóticamente para los núcleos de problemas tratables por parámetro fijo. En este artículo, hicimos un estudio de una herramienta llamada lema de expansión que ayuda a reducir el tamaño del núcleo. Su origen temprano fue en forma de descomposición de coronas, es decir, para obtener el núcleo lineal del problema; el lema específico fue identificado como la herramienta detrás del núcleo óptimo para el problema del conjunto de vértices de retroalimentación no dirigida. Desde entonces, se han descubierto varias variaciones y extensiones de la herramienta. Las estudiamos junto con sus aplicaciones en este artículo.