17 problems

Let $N$ and $F$ be the nest and food source, respectively, in a finite graph, and let ants make successive random walks from $N$ that stop when they hit $F$, updating pheromone lev…

Let $G$ be a graph and let $k$ node pairs $(s_1,t_1),\dots,(s_k,t_k)$ be given. The $k$-Disjoint Shortest Paths ($k$-DSP) problem asks for node-disjoint shortest paths…

Equivistal subdivision conjecture. The equivalence relation induced by equivistality constitutes a convex polyhedral subdivision of $S$. Moreover, the number of open regions in thi…

Polynomial combinatorial-type conjecture. The cardinality of the set of combinatorial types of shortest paths in $S$ is polynomial in the number of facets of $S$ when the dimension…

Polynomial source-image conjecture. There is a fixed polynomial $f_d$, independent of both $S$ and $v$, such that

Let $G$ be a plane graph, and let $P$ be a set of non-crossing single-touch shortest paths in $G$. The path covering with forests number of $P$, denoted by $\operatorname{PCFN}(P)$…

Converse compatibility conjecture. If $\Sigma_1$ and $\Sigma_2$ are two compatible signed graphs, then the connected tensor product $\Sigma_1\otimes\Sigma_2$ is compatible.

In the Poisson multigraph model, each pair of vertices is joined by infinitely many edges whose weights form a rate-$1$ Poisson process, and $X_k$ denotes the cost of the $k$th suc…

Let $p\geq 3$, let $G^{(p)}_{n+1}$ contain the copy $AG^{(p)}_n$, and let $S_{n_0}$ be the recursively defined border set. Let $a$ be the vertex labeled $A^{n_0+1}$, and call a ver…

Let $G^{(p)}_n$ be the recursively defined Tower of Hanoi graph, and let $S_n$ be the border set of the copy $AG^{(p)}_n$ in $G^{(p)}_{n+1}$. A shortest path from $a$ to a vertex o…

Let $p\geq 3$, let ${\cal A}_p$ be an alphabet of $p$ letters, and let $A,B\in{\cal A}_p$. For $n\geq 2$, consider vertices labeled $A^n$ and $B^n$. A vertex on a path is special i…

Let $G(n,\pi)$ be the unit disk graph, and let two vertices be displaced by $r_{xy}$. Write $\sigma_{r_{xy}}$ for the number of geodesic paths between them. Negative-binomial conje…

Let $G$ be a large but finite graph with negative curvature. Let the demand and inertia of a vertex be the graph quantities defined in the paper. Jonckheere–Lou–Bonahon–Baryshnikov…

Let $G$ be a large but finite graph with negative curvature. Let the demand of a vertex mean the quantity measuring how many shortest paths pass through it, as defined in the paper…

Consider the complete graph with edge weights of the form $\operatorname{Exp}(1)^s$, where $s>1$, and the forward-backward single-source shortest paths algorithm. The linear-time c…

Consider the complete graph with edge weights of the form $\operatorname{Exp}(1)^s$, where $s>1$, and the forward-backward single-source shortest paths algorithm. The conjecture. T…

Classification conjecture. At least when $\gamma$ is not algebraic, there is some simple classification of when and how non-uniqueness of minimum-cost routes occurs.