Resumen - Parametrizaciones de FPT de Ancho de Hipertree Fraccional y Generalizado

Parametrizaciones de FPT de Ancho de Hipertree Fraccional y Generalizado

2025-07-15 08:23:01

{"Matthias Lanzinger","Igor Razgon","Daniel Unterberger"}

{cs.DS,cs.CC}

Este documento presenta los primeros algoritmos de tiempo de ejecución en función del parámetro fijo (FPT) para determinar con precisión varios parámetros centrales de descomposición de hipergráfos, incluyendo el ancho de hiperárbol generalizado (ghw) y el ancho de hiperárbol fraccional (fhw). A pesar de que se reconoce su importancia en la teoría de la complejidad, las bases de datos y la satisfacción de restricciones, no se conocían algoritmos FPT exactos para estos parámetros hasta ahora. Los autores obtienen sus resultados para clases de hipergráfos con rango y grado limitados. Su enfoque extiende un algoritmo reciente para el ancho de árbol (Bojańcyk y Pilipczuk, LMCS 2022) utilizando transducciones de orden cuasi-monádico (MSO). Este marco les permite superar las importantes dificultades técnicas presentadas por los hipergráficos, cuyas descomposiciones estructurales son más complejas que las de sus contrapartes gráficas. Las contribuciones principales del documento son: 1. **Definición de funciones de ancho manejables**: Los autores definen una nueva clase de funciones de ancho, denominadas manejables, que son más generales que las funciones de ancho tradicionales utilizadas para el ancho de árbol. Esto les permite aplicar sus algoritmos a una gama más amplia de medidas de ancho de hipergráfos. 2. **Generalización del algoritmo para el ancho de árbol**: Los autores extienden el algoritmo para el ancho de árbol de Bojańczyk y Pilipczuk a un marco general para parámetros de hipergráficos. Esto les permite aplicar el algoritmo a ghw y fhw. 3. **Construcción de transducciones**: Los autores construyen transducciones de orden cuasi-monádico que relacionan las descomposiciones en árboles con los bosques de eliminación óptimos. Esto les permite verificar el ancho f de un hipergráfico. 4. **Algoritmo para verificar ghw y fhw**: Los autores presentan un algoritmo FPT para verificar ghw y fhw para hipergráficos con rango y grado limitados. Los autores creen que sus resultados tendrán una significativa influencia en el estudio de los hipergráficos y sus aplicaciones en diversas áreas. También discuten varios problemas abiertos relacionados con su trabajo, incluyendo la posibilidad de eliminar la restricción de grado de sus algoritmos.