Induction on Directed Acyclic Graphs with Root / Polytree

36 Views Asked by At

Assume $G$ is a directed acyclic graph (DAG) with one root node $u$.

This makes $G$ a polytree, a DAG whose underlying undirected graph is a tree.

Let's say we want to prove that statement $P$ holds for all nodes of $G$.

Question:

Does the following induction principle hold:

$$P(u) \; \text{and} \; \forall v \in G\colon \big(\forall w \in G\colon [w \in \text{parents}(v) \implies P(w)] \implies P(v)\big)$$ $$\implies \forall v \in G\colon P(v)$$

I.e. $P$ holds for the root, and if $P$ holds for all parents of $v$, then $P$ holds for $v$.

Attempt to proof:

Consider it as a special case of Noetherian Induction.

We need to construct a well-founded relation.

Let $w \prec v$, if there is a directed path from $w$ to $v$.

This partial order is called reachability relation.

In particular, $w \in \text{parents}(v) \implies w \prec v$.

I think the following implication holds: $$\big(\forall w \in G\colon [w \in \text{parents}(v) \implies P(w)] \implies P(v)\big) \implies \big(\forall w \in G\colon [w \prec v \implies P(w)] \implies P(v)\big)$$

Note that a node can have an infinite number of parents or children.

Thus, it remains to show that $\prec$ is well-founded, that each non-empty subset of nodes has a minimal element with respect to $\prec$. This could follow from the property that $G$ is a directed tree (with root node $u$). There are no infinite descending chains.