AOT & AOG - Using Tree Decomposition as Guiding Pseudo Tree

this article will go over the creation of

• OR Search Trees (AOT)
• OR Search Graphs (AOG) - specifically Context Minimal AND/OR Search Graphs

while using a tree decomposition as the guiding pseudo tree

Example

• we create a tree decomposition of the primal graph shown below
• to form a tree decomposition we will use purple arrows of the bucket elimination algorithm (note: we don’t actually have to execute the bucket elimination algorithm, we are just using intuition of buckets)
• the tree decomposition is a valid guiding pseudo tree for creating an AOT

generating-pseudo-trees-from-tree-decompositions-from-bucket-trees-1.drawio

• the AOT is shown below (assume each variable A, …, F has domain {0, 1})

generating-pseudo-trees-from-tree-decompositions-from-bucket-trees-2.drawio

• to turn the OR Search Tree into a OR Search Graph we will need to know to contexts of each variable (A, …, F)
• we do this by forming an induced graph of the extended graph below
• the context of a node in an induced graph are its parents (assume all all edges are pointing down)
  • context of F = AEF
  • context of D = BED
  • context of E = ABE
  • context of C = ABC
  • context of B = AB
  • context of A = A
• merge all nodes in the OR Search Tree that have the same context

generating-pseudo-trees-from-tree-decompositions-from-bucket-trees-3.drawio