Multitree

A directed acyclic graph in which every ordered pair of vertices has at most one directed path, equivalently a DAG whose reachability order is diamond-free.

Version

v2 · 2026-09-06 · History

Domain-specific #

2337

Origin domain

mathematics

Subdomain

directed graphs

Aliases

Strongly unambiguous graph, Mangrove graph, Diamond-free reachability DAG

Core Idea

A multitree is a directed acyclic graph in which there is at most one directed path from any vertex (u) to any vertex (v). The condition permits a node to have multiple parents and permits overlapping hierarchies, but forbids two distinct ancestry routes connecting the same ordered pair. Equivalently, the reachability relation is a diamond-free partial order; the transitive reduction of such a poset is a multitree.^[1]

Another equivalent test is that the subgraph reachable from any one vertex induces an undirected tree.

Structural Signature

• A directed graph with no directed cycle.
• Reachability as a partial order.
• At most one directed path for every ordered vertex pair.
• Absence of a reachability diamond.
• Tree-shaped descendant subgraph from each root vertex.
• Possible multiple parents without reconvergent ancestry from one source.
• A transitive reduction representing cover relations.
• Unambiguous propagation between comparable nodes.
• Compatibility with overlapping taxonomies.
• Explicit separation from other uses of “multitree.”

What It Is Not

It is not an ordinary rooted tree, because nodes may have more than one parent. It is not a polytree, whose entire underlying undirected graph is a tree; every polytree is a multitree but not conversely. It is not merely any DAG, and diamond-free refers to reachability order rather than only absence of a four-edge subgraph in an unreduced drawing.

Scope of Application

Multitrees model overlapping classifications, unambiguous nondeterministic computation, inheritance structures, and directed reachability where duplicate routes would create ambiguity. Furnas and Zacks use multitrees to represent multiple overlapping hierarchies while retaining navigable local tree structure.^[1] Wigderson analyzes unambiguous reachability restrictions in complexity theory.^[2]

Clarity

State whether the graph includes transitive edges or is transitively reduced, and test uniqueness over directed paths in the represented relation. Name whether “multitree” means this DAG/poset concept, a series–parallel order, or an unrelated data structure. Distinguish path uniqueness from merely unique shortest path.

Manages Complexity

The abstraction permits a concept to participate in multiple broader categories without allowing two different inheritance chains from one ancestor to the same descendant. Consequently, propagation from a source has a unique explanation path.

Abstract Reasoning

1. Verify directed acyclicity.
2. Compute or reason about reachability.
3. Search for an ordered pair joined by two distinct directed paths.
4. Equivalently search the reachability poset for a diamond.
5. Reduce transitive edges when a cover graph is required.
6. Check each root's reachable subgraph for an undirected cycle.
7. Use unique paths for attribution or propagation.
8. If a second path is needed, decide whether ambiguity is acceptable or the identity should be a general DAG.

Poset treatments connect the forbidden diamond to extremal questions about diamond-free families.^[3]

Knowledge Transfer

The portable pattern is allow multiple local hierarchies but forbid reconvergence that gives one ancestor two distinct routes to one descendant. It transfers to provenance and access inheritance. The proposed immediate parent is Directed Acyclic Graph.

Examples

Two unrelated roots may point into one shared node without violating the condition, because neither root necessarily has two paths to it. If a source branches through (a) and (b) and both later reach (z), the two source-to-(z) paths form a forbidden diamond.

A family taxonomy with marriage links can form a multitree when cross-links do not join blood-related branches and thereby create reconvergent ancestry. Standard extremal-combinatorics treatments provide the wider order-theoretic setting in which forbidden suborders are analyzed.^[4]

Structural Tensions

• Overlapping hierarchy versus unique explanation path.
• Multiple parents versus forbidden reconvergence.
• Drawn edges versus reachability relation.
• Expressiveness versus unambiguous propagation.
• Terminological reuse across literatures.

Structural–Framed Character

Unique-path acyclic structure is structural. Directed paths, reachability posets, transitive reductions, diamonds, and taxonomy graphs are constitutive. The identity is domain-specific.

Structural Core vs. Domain Accent

The structural core is DAG + multiple roots/parents - reconvergent paths. The domain accent is graph- and order-theoretic reachability.

Instantiates / Related Primes

Directed Acyclic Graph is the proposed immediate parent. Tree, Uniqueness, Hierarchy, and Path are related primes. Polytree and Topological Sorting are domain-specific neighbors.

The prospective queue contains one strict edge to prime:directed_acyclic_graph. No live DAG mutation is authorized.

Relationships to Other Abstractions

Current abstraction Multitree Domain-specific

Parents (1) — more general patterns this builds on

• Multitree is a kind of Directed Acyclic Graph Prime

  Directed Acyclic Graph is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

• Multitree → Directed Acyclic Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space

Multitree sits in a sparse region of the domain-specific corpus (84^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Discrete Structures & Graph Algorithms (17 abstractions)

Nearest neighbors

• Good Spanning Tree — 0.83
• Homogeneous Graph — 0.82
• Quotient Graph — 0.82
• Cage (Graph Theory) — 0.80
• Tree (Data Structure) — 0.80

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

• Rooted tree.
• Polytree.
• Arbitrary DAG.
• Unique-shortest-path graph.
• Diamond-free graph rather than diamond-free reachability poset.
• Other domain-specific uses of “multitree.”

References

[1] George W. Furnas and Jeff Zacks, “Multitrees: Enriching and Reusing Hierarchical Structure,” in Proceedings of CHI 1994 (ACM, 1994), 330–336, doi:10.1145/191666.191778. registry ↩a ↩b

[2] Avi Wigderson, “The Complexity of Graph Connectivity,” in Mathematical Foundations of Computer Science 1992, LNCS 629 (Springer, 1992), 112–132, doi:10.1007/3-540-55808-X_10. registry ↩

[3] Jerrold R. Griggs and Wei-Tian Li, “Progress on Poset-Free Families of Subsets,” in Recent Trends in Combinatorics (Springer, 2016), 317–338, doi:10.1007/978-3-319-24298-9_13. registry ↩

[4] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, 6^th ed. (Springer, 2018), chapters on partially ordered sets and extremal set systems, doi:10.1007/978-3-662-57265-8. registry ↩