I like to think of treewidth in terms of its characterization from tree decomposition, a task where you find a clique tree (or junction tree) of an undirected graph.
Clique trees for an undirected graph is a tree such that:
node of a tree corresponds to a clique of a graph
maximal clique of a graph corresponds to a node of a tree
given two adjacent tree nodes, the clique they correspond to inside the graph is separated given their intersection set (sepset)
You can check that these properties hold in the example below. I will also refer to nodes of a clique tree as ‘cliques’. (image from here)
My intuition for the point of tree decompositions is that you want to coarsen the variables of a complicated graph so that they can be represented in a simpler form (tree), while ensuring the preservation of useful properties such as:
how the sepset mediates (i.e. removing the sepset from the graph separates the variables associated with all of the nodes on one side of the tree with another) the two cliques in the original graph
clique trees satisfy the running intersection property: if (the cliques corresponding to) the two nodes of a tree contain the same variable X, then X is also contained in (the cliques corresponding to) each and all of the intermediate nodes of the tree.
Intuitively, information flow about a variable must connected, i.e. they can’t suddenly disappear and reappear in the tree.
Of course tree decompositions aren’t unique (image):
So we define treewidth(G)=minclique tree T of Gmaxclique of Tsize(T)−1.
Intuitively, treewidths represent the degree to which nodes of a graph ‘irreducibly interact with one another’, if you really want to see the graph as a tree.
e.g., the first clique tree of the image above is a suboptimal coarse graining in that it misleadingly characterizes G as having a greater degree of ‘irreducible interaction’ among.
I like to think of treewidth in terms of its characterization from tree decomposition, a task where you find a clique tree (or junction tree) of an undirected graph.
Clique trees for an undirected graph is a tree such that:
node of a tree corresponds to a clique of a graph
maximal clique of a graph corresponds to a node of a tree
given two adjacent tree nodes, the clique they correspond to inside the graph is separated given their intersection set (sepset)
You can check that these properties hold in the example below. I will also refer to nodes of a clique tree as ‘cliques’. (image from here)
My intuition for the point of tree decompositions is that you want to coarsen the variables of a complicated graph so that they can be represented in a simpler form (tree), while ensuring the preservation of useful properties such as:
how the sepset mediates (i.e. removing the sepset from the graph separates the variables associated with all of the nodes on one side of the tree with another) the two cliques in the original graph
clique trees satisfy the running intersection property: if (the cliques corresponding to) the two nodes of a tree contain the same variable X, then X is also contained in (the cliques corresponding to) each and all of the intermediate nodes of the tree.
Intuitively, information flow about a variable must connected, i.e. they can’t suddenly disappear and reappear in the tree.
Of course tree decompositions aren’t unique (image):
So we define treewidth(G)=minclique tree T of Gmaxclique of Tsize(T)−1.
Intuitively, treewidths represent the degree to which nodes of a graph ‘irreducibly interact with one another’, if you really want to see the graph as a tree.
e.g., the first clique tree of the image above is a suboptimal coarse graining in that it misleadingly characterizes G as having a greater degree of ‘irreducible interaction’ among.