3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ziggystar May 10 '13 at 11:52
  • $\begingroup$ 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. $\endgroup$ – András Salamon May 10 '13 at 15:47
  • $\begingroup$ It seems that treewidth can become lower after this "transformation" for certain problems. You know anything about this? $\endgroup$ – ziggystar May 10 '13 at 18:35
  • $\begingroup$ The sanity clauses to enforce that each variable is only assigned one value often lead to high treewidth. But otherwise it is possible. $\endgroup$ – András Salamon May 12 '13 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.