##  [Inzidenz-Treewidth](/de/node/60908) 

 Definition

Der Treewidth des Inzidenzgraphen einer logischen Formel oder CNF-Instanz: Der Inzidenzgraph hat einen Knoten für jede Variable und jede Klausel und Kanten zwischen einer Variable und jeder Klausel, die sie enthält; Inzidenz-Treewidth misst, wie baumartig diese bipartite Struktur ist.

 

 

 

 

 

 





## Prinzip

Prinzip

Niedriger Inzidenz-Treewidth erfasst strukturelle Sparsamkeit und begrenzte Wechselabhängigkeit zwischen Klauseln und Variablen und ermöglicht dynamische Programmierung oder fixe-Parameter-Algorithmen, die die Baumzerlegung ausnutzen.

 

 

 

 

 





## Demonstration

Demonstration

Eine CNF, deren Inzidenzgraph beschränkten Treewidth hat, erlaubt SAT-Algorithmen mit Laufzeit linear in der Formelausdehnung, aber exponentiell im Treewidth; viele CSP- und Modellzähl-Algorithmen nutzen kleinen Inzidenz-Treewidth für Traktabilität.

 

 

 

 

## Fehlanwendung

Fehlanwendung

Die Verwechselung von Inzidenz-Treewidth mit primalem Treewidth (verbunden Variablen, die zusammen auftreten) oder dualem Treewidth (Klausel-Klausel-Interaktionen) führt zu falschen Rückschlüssen über algorithmische Anwendbarkeit, da diese Parameter unterschiedlich sind und verschiedene algorithmische Eigenschaften begrenzen.

 

 

 

 

 





## Konsequenz

Konsequenz

Beschränkter Inzidenz-Treewidth impliziert die Existenz strukturierter Zerlegungen, die sonst schwierige Probleme fix-parameter-traktabel (FPT) im Treewidth-Parameter machen und leitet Entscheidungen zur Kodierung, um Interaktionen zu reduzieren.

 

 

 

 

## Umkehrung

Umkehrung

Man kann die strukturelle Sicht umkehren und Lokalitätsmaße wie Klauselgröße oder Variablengrad betrachten; hoher Inzidenz-Treewidth schließt lokale traktable Fragmente nicht aus, signalisiert jedoch globale Kopplung, die einfache Zerlegungen durchkreuzt.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Hängt von der Konstruktion des Inzidenzgraphen ab (Variablen und Klauseln als Knoten, Kanten für Inzidenzen); schließt semantische Vereinfachungen wie Variablenelimination oder Subsumption aus, sofern sie nicht vor dem Aufbau des Graphen angewendet werden, und unterscheidet sich von anderen Graphparametern durch Knotentypen und Kantendefinitionen.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Steht im Wettbewerb mit primalem und dualem Treewidth: primaler Treewidth kann klein sein während Inzidenz-Treewidth groß ist und umgekehrt; die Wahl des Graphmodells beeinflusst, welche algorithmischen Garantien gelten.

 

 

 

 

 





## Synthese

Synthese

Inzidenz-Treewidth ist ein struktureller Graphparameter des bipartiten Variablen-Klausel-Inzidenzgraphen, der globalen Kopplungsgrad quantifiziert; niedrige Werte ermöglichen dynamische Programmierung und FPT-Techniken für SAT und CSP, und seine Beziehung zu anderen Breitenmaßen leitet, welche Zerlegungen und Kodierungen wirksam sind.