AFTD Auto-Formalizing Theoretical Domains

cnf_incidence_treewidth

def

The incidence treewidth tw*(F) of a CNF formula F: the treewidth of its incidence graph.

Statement

noncomputable def cnf_incidence_treewidth {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) : ℕ
Defined in
Short Resolution Refutations for CNFs with Bounded Weighted Incidence Treewidth, arXiv:2610.02047, Sec. 3.2 (incidence treewidth)
Verified
06 Oct 2026
Axioms
none listed
Built on 3
  • graph_treewidthThe treewidth of a graph: the least w such that it has a tree decomposition of width at most w.
  • cnf_incidence_graphThe incidence graph G*(F) of a CNF formula F: the bipartite graph whose vertices are the variables of F and the clauses of F, a variable x…
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
Used by 2

Lean source view module on GitHub

/-- The incidence treewidth of a CNF formula. -/
noncomputable def cnf_incidence_treewidth {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) : ℕ :=
  graph_treewidth (cnf_incidence_graph F)
See it in the graphDiscuss this resultChallenge it