Resumen:Las medidas estructurales de gráficos, como el ancho de árbol, son herramientas centrales en la complejidad computacional que resultan en algoritmos eficientes al explotar el parámetro. Incluso se sabe que los solucionadores SAT modernos funcionan de manera eficiente en instancias de árboles de pequeño ancho. Dado que estos solucionadores se aplican ampliamente, la investigación está interesada en codificaciones compactas en (Q)SAT para resolver y comprender las limitaciones de codificación. Aún más general es el parámetro del gráfico ancho de camarilla, que a diferencia del ancho del árbol puede ser pequeño para gráficos densos. Aunque hay algoritmos disponibles para el ancho de camarilla, se sabe poco sobre las codificaciones. We initiate the quest to understand encoding capabilities with clique-width by considering abstract argumentation, which is a robust framework for reasoning with conflicting arguments. Se basa en gráficos dirigidos y solicita propiedades computacionalmente desafiantes, lo que lo convierte en un candidato natural para estudiar propiedades computacionales. Diseñamos reducciones novedosas desde problemas de argumentación a (Q)SAT. Nuestras reducciones preservan linealmente el ancho de la camarilla, lo que resulta en reducciones guiadas por descomposición dirigida (DDG). Establecemos resultados novedosos para toda la semántica de la argumentación, incluido el conteo. En particular, los gastos generales causados por nuestras reducciones de DDG no pueden mejorarse significativamente bajo suposiciones razonables.
Publicado originalmente en export.arxiv.org el 17 de noviembre de 2025.
Ver fuente original
