Okay, so much for inference.

Now there's one thing missing.

We talked about decomposition, or we mentioned that decomposition is a thing.

So let's look at this now.

The idea is basically if I have a constrained network, then of course I can do inference

to get rid of many of the branches in my search tree.

The other idea I can do is to try to use the structure of the network to decompose the

network into smaller networks and then solve them separately and compose the solutions

to the smaller networks to one big solution for the whole network.

So let's talk about what this means.

Here we have an example of our Australia map again but reduced to a simple graph and one

thing you should note is there is this one node T, Tasmania, which is completely separate

from the rest of the network.

That means I can solve this network and then just assign any color to T, it doesn't matter

because it's not connected to any of the others.

And this is a general principle.

Whenever I have a constraint network where I have like separate components that are disconnected

in a topological sense and I can just solve them separately, take the solutions for both

of them and just unify them to one solution.

This is stated here somewhat high-browly as a theorem which basically just says if I have

sub-components which are disconnected from each other, which is meant by each connected

component, so this is one connected component and this is one connected component, if I

have solutions to each of the connected components then I can unify them and I get a solution

to the whole network.

The proof is literally trivial and ultimately just amounts to the fact that there is no

constraint between the two connected components in this case or in a general case between

arbitrarily many connected components.

If the components are disconnected then there is nothing that impacts the solutions in any

way so I can just solve them separately and then unify them.

Now this is a nice thing because this also means here's just one example.

If I have a network with 40 variables and each one has two values in their domain and

I have four separate connected components, each of them are size 10, if I solve all of

those separately then I just basically four times do the algorithm with complexity to

the 10.

If I try to solve the whole network at once I get to the 40 and that's a huge reduction.

So this is a smart idea and one particular thing that is useful when it comes to constraint

networks is that it happens to be the case that if my constraint graph is acyclic, which

just to warn you this one isn't, if my constraint graph is acyclic then I can find a solution

rather quickly, i.e. to be precise my whole algorithm will, I can do an algorithm in nk

squared which is again of a factor of k and also n versus m.

I'll show you that on the next slide how this works for an acyclic constraint graph.

But the main point is keep in mind this one is not exactly acyclic.

Do you all know what an acyclic graph is?

I should ask that.

Some of you are shaking their heads.

An acyclic graph is simply a graph that doesn't have any cycles.

It literally is that simple.

So this one is not acyclic because I have a cycle between s.a and t and w.a so I can

go in this cycle, I can go in this cycle, I can go in this cycle, I can go in this cycle,

I can go in this cycle, I can go in this cycle, this cycle, this cycle, this cycle, this cycle