14 problems

Simple optimal solution conjecture. Every instance of MinCRS admits a simple optimal solution.

Let $K_n$ be the complete graph on $n$ vertices, with its edges assigned a uniformly random ordering, equivalently with independent continuous random weights. An accessible path is…

Let $n$ be a natural number, let ${\mathcal T}$ be a set of trees on vertex set $[n]$, let $\mu$ be a probability distribution on ${\mathcal T}$, and let…

Let $n$ be a natural number, let ${\mathcal T}$ be a set of trees on vertex set $[n]$, let $\mu$ be a probability distribution on ${\mathcal T}$, and let…

Let $n$ be a natural number, let $d=d(n)$ satisfy $2\leq d\leq n-1$, let ${\mathcal T}$ be a set of trees of maximum degree $d$ on vertex set $[n]$, let $\mu$ be a probability dist…

Let TND and TMW denote the temporal neighborhood diversity and temporal modular-width parameters, respectively, for temporal graphs. TND tractability conjecture. textsc{SingMinReac…

Let $G_{n,\delta}$ be an Erdős–Rényi random graph, and construct a temporal instance ${\cal I}(G_{n,\delta})$ by assigning labels to the edges of $G_{n,\delta}$ independently and u…

Let ${\cal G}_{n,\delta}$ denote the Erdős–Rényi random graph model with edge probability $\delta$, and let $(K_n,\lambda)$ be a random simple temporal graph. A $\delta$-clique is…

Let $p=\frac{c\log(n)}{n}$, and let $G$ be a random simple temporal graph with edge probability $p$, where $c\in(0,1)$. The largest temporal clique is bounded above by…

Let $n$ be the number of nodes, and let a sub-TVG be a randomly sampled sub-temporal visibility graph of the STARLINK satellite system. Let $r$ denote the convergence radius of its…

Linear temporal-reachability conjecture. There is a constant $c>0$ such that every strongly connected digraph admits an edge temporalisation with temporal reachability at least

Constant-factor approximability conjecture. The MRET problem can be approximated within a constant approximation ratio.

Two-arborescence conjecture. If

Bounded-pathwidth tractability conjecture. The problem can be solved in polynomial time under these restrictions.