How is this graphical representation of SAT/CSP instances called?

Question

Given a CNF formula (SAT problem), we can construct the constraint/dependency graph, which contains a vertex for each variable and a hyperedge for each clause. Same goes for CSPs, where we have a hyperedge for each constraint.

But given a CNF formula, we could also define a (slightly larger) graph that has literals as vertices and clauses as hyperedges, where each edge is incident to each literal it contains. This can analogously be done for a CSP.

How is the latter graph called?

Answer 1

This has been called the microstructure complement when the edges represent the forbidden partial assignments. I personally prefer the term clause structure. The clause structure of a constraint satisfaction problem instance is obtained by applying the direct encoding of the instance to SAT, where each possible value $a$ of variable $v$ is represented by a literal $(v,a)$, the forbidden partial assignments are SAT clauses involving these literals, and a clause $\{(v,a),(v,b)\}$ is added for every variable $v$ and any values $a\ne b$. (These clauses force a solution to be a function, assigning at most one value to each variable.)

If the edges represent the allowed partial assignments (with non-edges denoting forbidden partial assignments), this is called the microstructure. This representation doesn't require the extra clauses. However, one has to be careful of the semantics of missing edges. One must decide whether only edges of a particular arity are covered by the stipulation that missing edges are forbidden, or whether the microstructure should contain all consistent partial assignments. The semantics of the clause structure is much more straightforward.

The early work in constraint satisfaction only considered arity 2, when the microstructure and the clause structure are graphs. But the definition was general (or unspecific) enough that it applies for any arity.

• David A. Cohen, A New Class of Binary CSPs for which Arc-Consistency Is a Decision Procedure, CP 2003, 807–811. doi:10.1007/978-3-540-45193-8_57
• Eugene C. Freuder, Eliminating Interchangeable Values in Constraint Satisfaction Problems, AAAI 1991, 227–233.
• P. Jégou, Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems, AAAI 1993, 731–736.
• András Z. Salamon and Peter G. Jeavons, Perfect Constraints Are Tractable, CP 2008, 524–528. doi:10.1007/978-3-540-85958-1_35