Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 16:13, 5 July 2021

Revision as of 14:39, 2 January 2023

Line 112:

A hinge is a subset of nodes of hypergraph having some properties defined below. A hinge decomposition is based on the sets of variables that are minimal hinges of the hypergraph whose nodes are the variables of the constraint satisfaction problem and whose hyperedges are the scopes of its constraints.

The definition of hinge is as follows. Let <math>H</math> be a set of hyperedges. A path w.r.t.with respect to <math>H</math> is a sequence of edges such that the intersection of each one with the next one is non-empty and not contained in the nodes of <math>H</math>. A set of edges is connected w.r.t.with respect to <math>H</math> if, for each pair of its edges, there is a path w.r.t.with respect to <math>H</math> of which the two nodes are the first and the last edge. A connected component w.r.t.with respect to <math>H</math> is a maximal set of connected edges w.r.t.with respect to <math>H</math>.

Hinges are defined for reduced hypergraphs, which are hypergraphs where no hyperedge is contained in another. A set of at least two edges <math>H</math> is a hinge if, for every connected component <math>F</math> w.r.t.with respect to <math>H</math>, all nodes in <math>F</math> that are also in <math>H</math> are all contained in a single edge of <math>H</math>.

A hinge decomposition is based on the correspondence between constraint satisfaction problems and hypergraphs. The hypergraph associated with a problem has the variables of the problem as nodes are the scopes of the constraints as hyperedges. A hinge decomposition of a constraint satisfaction problem is a tree whose nodes are some minimal hinges of the hypergraph associated to the problem and such that some other conditions are met. By the correspondence of problems with hypergraphs, a hinge is a set of scopes of constraints, and can therefore be considered as a set of constraints. The additional conditions of the definition of a hinge decomposition are three, of which the first two ensure equivalence of the original problem with the new one. The two conditions for equivalence are: the scope of each constraint is contained in at least one node of the tree, and the subtree induced by a variable of the original problem is connected. The additional condition is that, if two nodes are joined, then they share exactly one constraint, and the scope of this constraint contains all variables shared by the two nodes.

Line 280:

| first=Rina

| last=Dechter

|authorlink = Rina Dechter

| title=Constraint Processing

| publisher=Morgan Kaufmann

Line 286 ⟶ 287:

}} {{ISBN|1-55860-890-7}}

*{{cite book

| firstfirst1=Rod

| lastlast1=Downey

|author1link = Rod Downey

|author2=Michael Fellows

|first2=Michael

|last2 = Fellows

|author2author2link = Michael Fellows

| title=Parameterized complexity

| publisher=Springer

Line 297 ⟶ 301:

| first=Georg

| last=Gottlob

|author1link = Georg Gottlob

|author2=Nicola Leone |author3=Francesco Scarcello

|first2=Nicola|last2 = Leone

|author2link = Nicola Leone

|first3=Francesco| last3 = Scarcello

| title=Hypertree Decompositions: A Survey

| book-title=[[International Symposium on Mathematical Foundations of Computer Science|MFCS]] 2001

| pages=37–57

| year=2001

Line 307 ⟶ 314:

| first=Georg

| last=Gottlob

|author2first2=Nicola|last2 = Leone |author3first3=Francesco| last3 = Scarcello

| title=A comparison of structural CSP decomposition methods

| journal=[[Artificial Intelligence (journal)|Artificial Intelligence]]

| volume=124

| issue=2