Ordered Graph
given an undirected graph 𝐆 = (𝑉, 𝐸) an ordered graph is a pair (𝐆, 𝑑) where:
- 𝑉 = {𝑣1, …, 𝑣𝑛} is the set of nodes
- 𝐸 is a set of arcs over 𝑉
- 𝑑 = (𝑣1, …, 𝑣𝑛) is an ordering of the nodes
Width
The nodes adjacent to 𝑣 that precede it in the ordering 𝑑 are called its parents
- width of a node in an ordered undirected graph is its number of parents (i.e. number of the node’s neighbors that precede it in the ordering)
- width of an ordering 𝑑, denoted 𝑤(𝑑), is the maximum width over all nodes
- width of a graph, denoted 𝑤(𝐆), is the minimum width of all the orderings of the graph
Induced Graph
The induced graph 𝐆𝑖of an ordered graph (𝐆, 𝑑) is as follows:
- the nodes of 𝐆 are processed from last to first (top to bottom) along node ordering 𝑑
- when a node 𝑣 is processed, all of its parents are connected with an edge
THEOREM: the resulting induced graph is triangulated (i.e. chordal graph where there are no loops of length > 3 without a “bridge”)
Induced Width (= Tree Width)
The nodes adjacent to 𝑣 that precede it in the ordering 𝑑 are called its parents
- induced width of a node in a graph is its number of parents in the induced graph (𝐆𝑖, 𝑑)
- induced width of an ordered graph 𝑤𝑖(𝑑) is the maximum induced width over all nodes in the induced graph (𝐆𝑖, 𝑑)
- induced width of a graph 𝑤𝑖(𝐆) is the minimal induced width over all its orderings
A rather important observation is that a graph is a tree (has no cycles) if and only if it has an induced-width = 1
The task of finding the minimal induced width of a graph (over all possible orderings) is NP-Complete (Arnborg, 1985)
Example Induced Graphs & Induced Width
Click here to expand...
a. depicts graph 𝐆
b. 𝑑1 = (𝐸, 𝐷, 𝐶, 𝐹, 𝐴, 𝐵)
c. 𝑑2 = (𝐵, 𝐴, 𝐶, 𝐹, 𝐸, 𝐷)d. 𝑑3 = (𝐵, 𝐷, 𝐸, 𝐶, 𝐴, 𝐹)for each ordering 𝑑:
- ordered graph - black edges
- induced graph - includes gray edges
Along 𝑑1
Along 𝑑2
Along 𝑑3
Width
Induced Width
Width
Induced Width
Width
Induced Width
𝐴
1
4
1
1
2
2
𝐵
3
3
0
0
0
0
𝐶
0
2
1
1
0
1
𝐷
0
1
1
1
1
1
𝐸
0
0
1
1
1
1
𝐹
0
3
1
1
1
1
Max
3
4
1
1
2
2
The width of the graph 𝐆 is 1
The induced width of the graph 𝐆 is also 1
---(induced-graph---induced-width)---(conditional-induced-graph---conditional-induced-width)/ordered-graph-and-induced-graph-(1).png)
Conditional Induced Graph
The conditional induced graph 𝐆𝑐𝑖of an ordered graph (𝐆, 𝑑) given evidence variables 𝐄 is obtained as follows:
- obtain induced graph 𝐆𝑐𝑖
- disregard all edges connected to observed nodes in 𝐆𝑐𝑖
- the resulting graph is a conditional induced graph
Conditional Induced Width
conditional induced width
- conditional induced width of an ordered graph (𝐆, 𝑑) given a set of evidence variables 𝐄, denoted as 𝑤𝑖𝐄(𝑑), is the width of the conditional induced graph (𝐆𝑖, 𝑑)
- conditional induced width of a graph 𝐆 given a set of evidence variables 𝐄, denoted as 𝑤𝑖(𝐆), is the minimal conditional induced width over all its orderings