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

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

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

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

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

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

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

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

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.