##  [Treewidth de Incidencia](/es/node/60908) 

 Definición

El treewidth del grafo de incidencia de una fórmula lógica o una instancia CNF: el grafo de incidencia tiene un vértice por cada variable y por cada cláusula, y aristas entre una variable y cada cláusula que la contiene; el treewidth de incidencia mide cuán cercano está este bipartito a un árbol.

 

 

 

 

 

 





## Principio

Principio

Un bajo treewidth de incidencia captura la esparcidad estructural y la dependencia limitada entre cláusulas y variables, permitiendo programación dinámica o algoritmos fijados-por-parámetro que explotan la descomposición en árbol.

 

 

 

 

 





## Demostración

Demostración

Una CNF cuyo grafo de incidencia tiene treewidth acotado admite algoritmos SAT que se ejecutan en tiempo lineal en el tamaño de la fórmula pero exponencial en el treewidth; muchos algoritmos de CSP y conteo de modelos explotan pequeño treewidth de incidencia para ser tractables.

 

 

 

 

## Aplicación incorrecta

Aplicación incorrecta

Confundir treewidth de incidencia con treewidth primal (que conecta variables que aparecen juntas) o dual (interacciones cláusula-cláusula) conduce a conclusiones erróneas sobre aplicabilidad algorítmica, ya que estos parámetros difieren y delimitan distintos comportamientos algorítmicos.

 

 

 

 

 





## Consecuencia

Consecuencia

Treewidth de incidencia acotado implica la existencia de descomposiciones estructuradas que hacen que problemas difíciles sean FPT en el parámetro treewidth y orienta elecciones de codificación para reducir interacciones.

 

 

 

 

## Inversión

Inversión

Se puede invertir la perspectiva estructural y considerar medidas de localidad como tamaño de cláusula o grado de variable; un treewidth de incidencia alto no excluye fragmentos localmente tratables pero indica un acoplamiento global que frustra una simple descomposición.

 

 

 

 

 





## Límite

Límite

Depende de construir el grafo de incidencia (variables y cláusulas como vértices, aristas para la incidencia); excluye simplificaciones semánticas como eliminación de variables o subsunción salvo que se apliquen antes de construir el grafo, y difiere de otros parámetros gráficos por los tipos de vértices y la definición de aristas.

 

 

 

 

 





## Tensión semántica

Tensión semántica

Compite con treewidth primal y dual: el treewidth primal puede ser pequeño mientras el de incidencia es grande y viceversa; la elección del modelo de grafo influye en las garantías algorítmicas disponibles.

 

 

 

 

 





## Síntesis

Síntesis

El treewidth de incidencia es un parámetro estructural del grafo bipartito variable-cláusula que cuantifica el acoplamiento global; valores bajos habilitan técnicas de programación dinámica y FPT para SAT y CSP, y su relación con otras medidas de anchura guía qué descomposiciones y codificaciones son eficaces.