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
- cnf_incidence_treewidth_emptyThe incidence treewidth of the empty formula is 0.
- cnf_incidence_treewidth_le_cardUniversal upper bound: the incidence treewidth of any CNF formula F is at most |vars(F)| + |F|.
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)