Steiner Trees and Convex Geometries
Morten Hegner Nielsen, Ortrud R. Oellermann · SIAM Journal on Discrete Mathematics · 2009
Let V be a finite set and $\mathcal{M}$ a collection of subsets of V. Then $\mathcal{M}$ is an alignment of V if and only if $\mathcal{M}$ is closed under taking intersections and contains both V and the empty set. If $\mathcal{M}$ is an alignment of V, then the elements of $\mathcal{M}$ are called convex sets and the pair $(V,\mathcal{M})$ is called an aligned space. If $S\subseteq V$, then the convex hull of S is the smallest convex set that contains S. Suppose $X\in\mathcal{M}$. Then $x\in X$ is an extreme point for X if $X\setminus\{x\}\in\mathcal{M}$. The collection of all extreme points of X is denoted by $\text{{\it ex\/}}(X)$. A convex geometry on a finite set is an aligned space with the additional property that every convex set is the convex hull of its extreme points. Let G be a connected graph. A set S of vertices is g-convex if for every pair $u,v$ of vertices in S, every vertex that belongs to some u-v geodesic (shortest path) is also in S. A set S of vertices in G is k-Steiner-convex, denoted by $g_k$-convex, if, for every set T of k vertices of S, every vertex that belongs to some Steiner tree for T, i.e., a subtree of G of smallest size containing T, is also in S. Let $R=\{k_1,k_2,\dots,k_t\}$ be a collection of positive integers such that $2\leq k_1