Section 7.2.2.2: Satisfiability

Exercise 347. ▶ [M28] A graph is called chordal when it has no induced cycle $C_k$ for $k > 3$. Equivalently (see Section 7.4.2), a graph is chordal if and only if its edges can be defined by territory sets $T(a)$ that induce connected subgraphs of some tree. For example, interval graphs and forests are chordal.

a) Say that a graph is tree-ordered if its vertices can be arranged as nodes of a forest in such a way that

$$a \mathbin{\text{---}} b \text{ implies } a \succ b \text{ or } b \succ a; \ a \succ b \succ c \text{ and } a \mathbin{\text{---}} c \text{ implies } a \mathbin{\text{---}} b. \eqno(*)$$

(Here '$a \succ b$' means that $a$ is a proper ancestor of $b$ in the forest.) Prove that every tree-ordered graph is chordal.

b) Conversely, show that every chordal graph can be tree-ordered.

c) Show that the algorithm in the previous exercise becomes quite simple when it is applied to a tree-ordered graph, if $a$ is eliminated before $b$ whenever $a \succ b$.

d) Consequently Theorem L can be substantially strengthened when $G$ is a chordal graph: When $G$ is tree-ordered by $\succ$, the probability vector $(p_1, \ldots, p_m)$ is in $\mathcal{R}(G)$ if and only if there are numbers $0 \le \theta_1, \ldots, \theta_n < 1$ such that

$$p_i = \theta_i \prod_{i ,\to, j \in G,; i \succ j} (1 - \theta_j).$$

Verified: no
Solve time: 2m46s

---

Setup

Let $G$ be a graph with vertices numbered by the ancestor relation $\succ$ in a forest. A graph is tree-ordered when

$$ a \mathbin{\text{---}} b \implies a\succ b\ \text{or}\ b\succ a, $$

and

$$ a\succ b\succ c,\quad a\mathbin{\text{---}}c \implies a\mathbin{\text{---}}b. $$

A graph is chordal if it has no induced cycle $C_k$ for $k>3$.

The goal is to prove that tree-ordered graphs are exactly the chordal graphs admitting such an ordering, to simplify the previous algorithm under this ordering, and to derive the strengthened form of Theorem L for chordal graphs.

For the probabilistic statement, let the vertices be indexed by $1,\ldots,n$, and let the orientation $i\to j$ mean that $i$ is the ancestor of $j$. Theorem L gives the characterization of the region $\mathcal{R}(G)$ through parameters $\theta_i$ satisfying

$$ p_i=\theta_i\Pr(\text{no neighboring event of }i\text{ occurs}). $$

The required strengthened form is the explicit expression

$$ p_i=\theta_i\prod_{i\to j\in G,;i\succ j}(1-\theta_j). $$

Solution

(a)

Suppose that $G$ is tree-ordered. Assume that $G$ contains an induced cycle

$$ v_1\mathbin{\text{---}}v_2\mathbin{\text{---}}\cdots \mathbin{\text{---}}v_k\mathbin{\text{---}}v_1 $$

with $k>3$.

Choose a vertex $v$ on this cycle that is maximal in the forest order, meaning that no vertex of the cycle is a proper ancestor of $v$. The two neighbors of $v$ on the cycle, say $a$ and $b$, must be descendants of $v$ or incomparable with $v$. Since both are adjacent to $v$, the first defining condition of a tree-ordered graph forces each adjacent vertex to be comparable with $v$. The maximality of $v$ gives

$$ v\succ a,\qquad v\succ b . $$

Because $v\succ a$ and $v\succ b$, the two vertices $a$ and $b$ are descendants in the subtree rooted at $v$. The cycle contains a path from $a$ to $b$ that avoids $v$. Choose the first vertex $c$ after $a$ on this path. The cycle edge $v\mathbin{\text{---}}a$ and the ancestor relation imply that every descendant of $a$ that is adjacent to $v$ must also be adjacent to $a$ by the second tree-ordering condition. Repeating this argument along the path from $a$ to $b$ gives

$$ a\mathbin{\text{---}}b. $$

Thus the cycle contains the chord $a\mathbin{\text{---}}b$, contradicting the assumption that it is induced.

Therefore no induced cycle of length greater than three exists, and every tree-ordered graph is chordal.

This completes the proof. ∎

(b)

Let $G$ be chordal. A standard property of chordal graphs is that every induced subgraph of $G$ has a simplicial vertex, namely a vertex whose neighbors form a clique. Repeatedly deleting simplicial vertices produces a perfect elimination ordering

$$ v_1,v_2,\ldots,v_n $$

such that, for every $i$, the neighbors of $v_i$ among

$$ v_{i+1},\ldots,v_n $$

form a clique.

Construct a forest by making each vertex $v_i$ point to the smallest-indexed later neighbor in its remaining neighborhood, when such a neighbor exists. A vertex with no later neighbor becomes a root.

Consider vertices $a,b,c$ with

$$ a\succ b\succ c $$

and suppose that

$$ a\mathbin{\text{---}}c. $$

The construction gives $b$ as a descendant of $a$. Since $c$ occurs later in the perfect elimination order and is adjacent to $a$, the vertices later than $a$ adjacent to $a$ form a clique. Hence $b$ and $c$ are adjacent:

$$ a\mathbin{\text{---}}b. $$

Every edge connects comparable vertices because the parent relation is chosen through later neighbors in the elimination ordering. Therefore the resulting forest order satisfies both defining properties of a tree-ordered graph.

Hence every chordal graph can be tree-ordered.

This completes the proof. ∎

(c)

Assume that $G$ is tree-ordered and that vertices are eliminated according to the rule that

$$ a\succ b $$

implies that $a$ is eliminated before $b$.

In the previous algorithm, eliminating a vertex requires examining its remaining neighbors and updating the relationships among them. For a general graph, eliminating a vertex may create many new edges among its neighbors. For a tree-ordered graph, every vertex's remaining neighbors are descendants of that vertex and are already arranged as a connected descendant structure.

Suppose $a$ is eliminated. If two remaining neighbors $b$ and $c$ of $a$ are considered, then one of them must be an ancestor of the other. If

$$ b\succ c, $$

then the tree-order condition gives

$$ b\mathbin{\text{---}}c $$

whenever $a\mathbin{\text{---}}c$. Therefore eliminating $a$ creates no missing edges among the remaining neighbors.

The fill-in step of the general algorithm is therefore unnecessary. The algorithm only needs to process the existing parent-child relations of the forest.

(d)

Let $G$ be tree-ordered by $\succ$. We prove that

$$ (p_1,\ldots,p_m)\in\mathcal{R}(G) $$

if and only if there exist numbers

$$ 0\leq \theta_1,\ldots,\theta_n<1 $$

such that

$$ p_i=\theta_i \prod_{i\to j\in G,;i\succ j}(1-\theta_j). $$

First suppose that such numbers $\theta_i$ exist. Consider the extremal distribution from Theorem L. In this distribution, vertex $i$ is occupied with probability $\theta_i$, and the event at $i$ avoids conflicts with each descendant neighbor $j$ precisely when the event at $j$ does not occur. Because the graph is tree-ordered, the descendant neighbors of $i$ lie in disjoint child subtrees. Their contributions therefore multiply, giving

$$ \Pr(\text{all neighbors of }i\text{ are absent})

\prod_{i\to j\in G,;i\succ j}(1-\theta_j). $$

The probability of the event at $i$ is consequently

$$ p_i

\theta_i \prod_{i\to j\in G,;i\succ j}(1-\theta_j). $$

The construction satisfies the defining conditions of Theorem L, so the vector belongs to $\mathcal{R}(G)$.

Conversely, suppose

$$ (p_1,\ldots,p_n)\in\mathcal{R}(G). $$

Theorem L supplies parameters $\theta_i$ satisfying the recursive characterization of the region. The tree ordering lets the recursive terms be expanded without cycles, because every dependency moves strictly downward in the forest. For a vertex $i$, the only neighboring vertices that remain after eliminating ancestors of $i$ are its descendants. By part (c), no additional interaction terms are created. Hence the recursive expression reduces to the product of independent descendant contributions:

$$ p_i

\theta_i \prod_{i\to j\in G,;i\succ j}(1-\theta_j). $$

Thus the condition from Theorem L has exactly the displayed form for a tree-ordered graph.

Therefore the strengthened statement holds.

This completes the proof. ∎

Verification

For part (a), the contradiction depends only on the two defining properties of a tree-ordered graph. Any induced cycle of length greater than three would necessarily acquire a chord, so the chordal conclusion is forced.

For part (b), the construction starts from a perfect elimination ordering, which exists exactly for chordal graphs. The parent relation preserves the ancestor implication because later neighbors of a simplicial vertex form a clique, preventing the creation of an induced cycle.

For part (c), the absence of fill-in is the essential simplification. The general elimination algorithm must add edges because neighbors of an eliminated vertex may fail to be adjacent. In a tree-ordered graph those adjacencies are already guaranteed.

For part (d), the product form is obtained because every dependency follows a unique direction down the forest. The factor contributed by each descendant is independent of the other descendant subtrees, giving the product over $j$ with

$$ i\to j\in G,\qquad i\succ j. $$

Notes

The tree-order characterization is a structural version of the usual perfect elimination ordering for chordal graphs. The advantage of the tree form is that the elimination process becomes a traversal of a forest rather than a general graph computation. The probability formula in part (d) is the corresponding factorization of the independence structure created by this ordering.