31 problems

Let $G$ be a graph and let $S\betasubseteq V(G)$. The set $S$ is $2k$-edge-connected if no set of fewer than $2k$ edges separates vertices of $S$. An $S$-tree is a tree in $G$ cont…

A minimum spanning tree is a shortest connection of a finite set $A$ of points in the plane by segments with endpoints in $A$. The Steiner ratio is the infimum, over finite point s…

Let $M$ be a circle of radius $R$ and let $r$ satisfy $R>r$. A maximal distance minimizer is a connected compact set of minimal length whose closed $r$-neighborhood contains $M$. M…

Let $\rho_2$ denote the infimum, over finite point sets in the Euclidean plane, of the length of a Steiner tree divided by the length of a Euclidean minimum spanning tree. Gilbert–…

West–Wu's conjecture. For every positive integer $k$, if $T$ is $3k$-edge-connected in $G$, then $G$ admits $k$ pairwise edge-disjoint $T$-connectors.

Let $\operatorname{ssr}(\mathbb R^2)$ denote the Steiner subratio of the Euclidean plane, defined as the infimum of the ratios of minimal-filling weight to Steiner minimal-tree len…

A Steiner tree on random points is a minimum-length network connecting the points, and the route-length between two points is the length of the path between them in the tree. For p…

Let $\mathbb{M}^n$ be a piece-wise differentiable, elliptic Minkowski space, and let $s(\mathbb{M}^n)$ denote the maximum degree of a Steiner point in a Steiner minimal tree in…

Let $\mathbb{M}^n$ be an $n$-dimensional Minkowski space, and let $s(\mathbb{M}^n)$ denote the maximum degree of a Steiner point in a Steiner minimal tree in $\mathbb{M}^n$. Morgan…

Cieslik's conjecture. The maximum degree satisfies

Morgan's conjecture. For all $d\geq 2$,

Let a Steiner network have terminal nodes, Steiner nodes, and entry/exit points on the boundaries of soft obstacles. After perturbing the terminal nodes, consider the positions of…

For a finite point set $P$ in the plane, let $\rho$ denote the infimum, over all such point sets, of the ratio between the length of a shortest Steiner tree and the length of a min…

Let $r\in(0,1)$ and $\alpha\in(0,1/r-1)$. A regular, unit simplicial complex on $m$ vertices has constituent simplices that are regular and unit. Euclidean Steiner tree conjecture…

A regular simplicial complex is a simplicial complex embedded with regular simplices as its constituent simplices. Simplicial-complex efficiency conjecture. Regular simplicial comp…

Let $d$ be the number of terminals in a regular simplex, and let $k\geq 1$. The construction described immediately before the claim recursively splits Steiner points and coordinate…

Let $k\geq 1$ and let $d$ satisfy … A good binary tree of height $k$ is defined recursively: a height-zero tree is a single node, and for positive height at most one child-subtree…

Let $G$ be a graph with $m$ edges, and embed each edge by its characteristic vector, as in the Vertex Cover reduction discussed in the source. Consider the Euclidean Steiner tree o…

Let $d\geq 1$, and consider finite point configurations of $d+1$ points in Euclidean space. Their Steiner ratio is the ratio of the cost of the optimal Steiner tree to the cost of…

For a finite point configuration in Euclidean space, define its Steiner ratio as the ratio of the cost of its optimal Steiner tree to the cost of its minimum spanning tree. A regul…

Let $(G,T)$ be a facet-inducing Steiner graph, with terminal set $T$ and facet weights $c$ whose corresponding facet inequality is in minimum integer form. For $|T|\leq 5$, the fac…

Let $\ell\ge 2$ facilities $W_1,\dots,W_\ell\subset\mathbb R^2$ be connected to terminals $P_1,\dots,P_n$ by a Weber network with terminal-facility weights $m_{rj}$ and facility-fa…

Let $G$ be a connected graph with at least $k$ vertices and at least $k$ edges, and let $L(G)$ be its line graph. For a set $S\subseteq V(G)$ with $|S|\geq 2$, let $\lambda_G(S)$ b…

Consider the efficiently solvable class of bidirected relaxations for the Steiner tree problem, whose characteristic representative is the bidirected cut relaxation. The bidirected…

Let an $\varepsilon$-approximate Steiner tree be a tree whose angles at Steiner points lie in $[2\pi/3-\varepsilon,2\pi/3+\varepsilon]$. For $d\geqslant 2$, let…