<p>This has been called the <em>microstructure complement</em> when the edges represent the forbidden partial assignments.  I personally prefer the term <em>clause structure</em>.  The clause structure of a constraint satisfaction problem instance is obtained by applying the <em>direct encoding</em> 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.)</p>

<p>If the edges represent the allowed partial assignments (with non-edges denoting forbidden partial assignments), this is called the <em>microstructure</em>.  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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-05-10T11:52:54.620Z
Thank you. What you describe as *clause structure* seems to be very close to what I was searching for. I'll wait with accepting for a while. Maybe there will be more terms coming up.
ziggystar
CC BY-SA 3.0
2013-05-10T15:47:16.640Z
Since I searched the literature on this for my thesis, a large part of which is about these structures, I would be very interested if this notion has been used elsewhere.
András Salamon
CC BY-SA 3.0
2013-05-10T18:35:49.473Z
It seems that treewidth can become lower after this "transformation" for certain problems. You know anything about this?
ziggystar
CC BY-SA 3.0
2013-05-12T08:29:27.677Z
The sanity clauses to enforce that each variable is only assigned one value often lead to high treewidth.  But otherwise it is possible.
András Salamon
CC BY-SA 3.0
2013-05-10T10:46:44.267Z
2013-05-10T10:46:44.267Z
András Salamon
<p>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.</p>

<p>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.</p>

<p>How is the latter graph called?</p>

<sat><csp>
How is this graphical representation of SAT/CSP instances called?
ziggystar
# How is this graphical representation of SAT/CSP instances called?

(Asked by: username_0 on 2013-05-10)

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?

**Tags:** sat, csp

---

## 1 answers

### Answer by username_1 on 2013-05-10. Score: 5 | Accepted answer

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](http://dx.doi.org/10.1007/978-3-540-45193-8_57)
* Eugene C. Freuder, [*Eliminating Interchangeable Values in Constraint Satisfaction Problems*](http://www.aaai.org/Library/AAAI/1991/aaai91-036.php), AAAI 1991, 227–233.
* P. Jégou, [*Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems*](http://www.aaai.org/Library/AAAI/1993/aaai93-109.php), 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](http://dx.doi.org/10.1007/978-3-540-85958-1_35)

> **Comments:**
> **username_0**: Thank you. What you describe as *clause structure* seems to be very close to what I was searching for. I'll wait with accepting for a while. Maybe there will be more terms coming up.  
> **username_1**: Since I searched the literature on this for my thesis, a large part of which is about these structures, I would be very interested if this notion has been used elsewhere.  
> **username_0**: It seems that treewidth can become lower after this "transformation" for certain problems. You know anything about this?  
> **username_1**: The sanity clauses to enforce that each variable is only assigned one value often lead to high treewidth.  But otherwise it is possible.  

---

