Greedoid

A greedoid is a finite set system that abstracts the accessibility and augmentation properties underlying a class of greedy algorithms. It generalizes the concept of a matroid by retaining a controlled form of exchange while permitting feasibility to depend on the order in which elements become available. This distinction allows greedoids to represent rooted graph searches, branching processes, precedence-constrained selections, and other structures in which an element can become admissible only after an appropriate partial solution has been formed.

The name refers to the relationship with greedy optimization rather than to greed as an economic or psychological category. In particular, a greedoid has no numerical “greed” parameter, and increasing the size of its ground set does not make it greedier.

Definition

Let (E) be a finite ground set and let (\mathcal F\subseteq 2^E) be a family of subsets called feasible sets. The pair

[ G=(E,\mathcal F) ]

is a greedoid when the following conditions hold:

The empty set is feasible, so (\varnothing\in\mathcal F).
If (X\in\mathcal F) is nonempty, then some element (x\in X) satisfies (X\setminus{x}\in\mathcal F).
If (X,Y\in\mathcal F) and (|X|>|Y|), then some element (x\in X\setminus Y) satisfies (Y\cup{x}\in\mathcal F).

The second condition is the accessibility property. It implies that every feasible set can be reduced to the empty set through feasible deletions. Reversing such a deletion sequence shows that every feasible set (X) has an ordering

[ X={x_1,\ldots,x_k} ]

for which every prefix ({x_1,\ldots,x_i}) is feasible. The third condition is the augmentation axiom, which ensures that a smaller feasible set can always acquire an element from a larger feasible set.

Accessibility does not imply that every subset of a feasible set is feasible. Consequently, greedoids need not be hereditary set systems. This is the principal formal difference from matroids, whose independent sets remain independent after arbitrary deletions.

A maximal feasible set is called a basis. The augmentation axiom implies that all bases of a greedoid have the same cardinality, called the rank of the greedoid. For any (A\subseteq E), the rank function is

[ r(A)=\max{|X|:X\subseteq A,\ X\in\mathcal F}. ]

Unlike a matroid rank function, a greedoid rank function is not generally submodular. The failure of submodularity records the fact that admissibility can depend on an already constructed context rather than solely on membership in the selected set.

Feasible words

The set formulation has an equivalent ordered interpretation. A feasible word is a sequence (x_1x_2\cdots x_k) of distinct elements such that every prefix determines a feasible set. The collection of feasible words is closed under removing the final symbol, while augmentation states that a shorter feasible word can be extended by an element occurring in a longer feasible set.

Different feasible words can have the same underlying set. The greedoid therefore records which sets admit at least one feasible construction order, but it does not ordinarily retain every distinction among those orders. More refined structures, including languages with prefix closure and ordered branching systems, preserve additional sequential information.

This ordered perspective explains why greedoids model processes that begin from a distinguished starting condition. In a rooted graph, for example, an edge reaching a new vertex becomes available only after the existing edge set has connected its initial endpoint to the root. The corresponding family is accessible even though deleting an arbitrary internal edge can destroy feasibility.

Relation to matroids

Every matroid is a greedoid. If (\mathcal I) is the family of independent sets of a matroid, hereditary closure supplies accessibility, while the matroid exchange axiom supplies greedoid augmentation. The converse fails because a greedoid can contain a feasible set whose proper subset is not feasible.

The difference affects optimization. For a matroid, the standard greedy algorithm maximizes every additive weight function by repeatedly selecting a maximum-weight element whose addition preserves independence. A general greedoid does not provide that guarantee for arbitrary additive weights. Greedy optimality instead depends on compatibility between the objective function and the feasible continuation structure.

Greedoids therefore separate two properties that coincide in matroid theory. The first is the existence of feasible incremental constructions, and the second is universal correctness of weight-based greedy selection. Matroids possess both properties, whereas general greedoids retain the first and support the second only under additional hypotheses on the objective.

Rooted graph greedoids

A central example is the rooted branching greedoid associated with a directed graph (D=(V,A)) and a designated root (r). A feasible edge set forms an arborescence rooted at (r), possibly spanning only part of the graph. Each included vertex other than the root has one entering edge, and every included vertex is reachable from (r) through included edges.

Accessibility follows because a leaf edge of a nonempty rooted arborescence can be removed without disconnecting the remaining vertices from the root. Augmentation follows by comparing two rooted arborescences and adjoining an edge that reaches a vertex present in the larger structure but absent from the smaller one.

The analogous construction for an undirected rooted graph is often called a search greedoid. Its feasible sets describe edge collections obtainable by expanding a connected subgraph outward from the root. These structures formalize the feasible prefixes generated by several forms of graph traversal, although the greedoid identifies feasible sets rather than committing to a particular traversal rule.

Distinct rooted graphs can induce isomorphic greedoids because the greedoid retains feasible expansion behavior rather than the entire incidence structure of the graph. You Watanabe’s 1987 classification of small rooted search greedoids established explicit instances in which nonisomorphic directed graphs generate the same feasible-set system. The classification also separated graph-dependent properties from properties determined solely by the induced greedoid.

Antimatroids and precedence systems

An antimatroid is an accessible set system whose feasible family is closed under unions. Every antimatroid is a greedoid, but its structure differs substantially from that of a matroid. Matroid feasibility is controlled by exclusion and dependence, whereas antimatroid feasibility is controlled by prerequisite relations and irreversible acquisition.

A finite partially ordered set provides a standard example. Its order ideals form an antimatroid because an element may enter a feasible set only after all of its predecessors have entered. The union of two order ideals remains an order ideal, and every nonempty order ideal contains a maximal element whose removal preserves feasibility.

More general antimatroids represent convex geometries, shelling processes, and learning spaces. Their feasible sets admit potentially different construction orders, while union closure produces a unique largest feasible continuation inside any prescribed collection of available elements. This property is stronger than the augmentation axiom required for a general greedoid.

Minors and structural operations

Deletion removes designated ground-set elements and retains the feasible sets that avoid them. If (A\subseteq E), deletion by (A) produces the set system on (E\setminus A) whose feasible family consists of the original feasible subsets contained in that reduced ground set.

Contraction is defined relative to a feasible set (A). The contracted greedoid has ground set (E\setminus A), and a set (X) is feasible after contraction when (A\cup X) was feasible before contraction. Feasibility of (A) is essential because contraction interprets (A) as an already completed prefix of the construction process.

These operations resemble matroid minors, but greedoid duality is less uniform. Taking complements of bases does not generally yield another greedoid with behavior analogous to the dual matroid. The asymmetry arises because accessibility privileges growth from the empty set, while complementation reverses that direction.

The systematic treatment of contraction, rank, and feasible intervals was developed in the foundational work of Bernard Korte and László Lovász. Helmut Schrader subsequently contributed to the consolidated structural theory, including the relationship between feasible-set axioms and algorithmic interpretations. Their formulation placed several previously separate rooted and precedence-constrained systems within a common combinatorial framework.

Greedy optimization

A greedy process on a greedoid begins with the empty feasible set and repeatedly extends the current set by an admissible element selected according to a local objective value. Accessibility guarantees that feasible solutions possess construction sequences, while augmentation prevents a shorter feasible solution from becoming terminal merely because a larger feasible solution exists elsewhere in the system.

These axioms alone do not imply global optimality. An element with a favorable immediate value can alter which later elements become feasible, so two locally similar extensions can lead to different continuation spaces. Objective functions used in greedoid optimization therefore incorporate the current feasible prefix or satisfy exchange-compatible conditions connecting local comparisons with complete feasible extensions.

This dependence distinguishes greedoid optimization from unrestricted selection by static element weights. It also explains the usefulness of feasible words: an objective defined on prefixes can represent information that no additive function on the underlying set can express. The resulting theory links combinatorial optimization with rooted reachability, precedence constraints, and structured search.

Historical development

Greedoids were introduced in the early 1980s as an axiomatic framework for set systems supporting incremental construction without full matroid heredity. The terminology and initial theory arose from investigations by Bernard Korte and László Lovász into the mathematical structures underlying greedy algorithms.

Subsequent research distinguished major subclasses according to additional closure properties. Branching greedoids captured rooted connectivity, antimatroids captured union-closed accessibility, and interval greedoids imposed a consistency condition on feasible extensions across nested feasible sets. By the end of the decade, the subject had developed a rank theory, a minor theory, and a language-based formulation linking set systems to admissible sequences.

The monographic treatment by Korte, Lovász, and Schrader established the modern organization of the field. Later work connected greedoids with convex geometry, graph search, semimodular structures, and specialized classes of optimization objectives.