56 problems

Given a semicomplete digraph $D$ and distinct vertices $x,y\in V(D)$, determine a longest directed $(x,y)$-path. Given a locally semicomplete digraph $D$ and distinct vertices…

For a pivoting rule $P$ and dimension $n$, let $g_n^{P}(\mathbb{R})$ denote the supremum, over all nonsingular matrices $A\in\mathbb{R}^{n\times n}$, of the ratio between the large…

Determine whether there exist universal constants $C,c>0$ and a polynomial-time online signing algorithm such that, for every dimension $n\ge 1$ and every finite horizon $T$, when…

Fix a code ${\mathcal M}$. Given a code ${\mathcal C}$ of length $n$, polynomial-time minor-containment conjecture. It is decidable in time polynomial in $n$ whether ${\mathcal C}$…

Let $F$ be a clause-set with deficiency surplus $\operatorname{\sigma}(F) \ge 1$. Write $\mu\\!\operatorname{vd}(F)$ for its minimum variable-degree and $\operatorname{nM}(k)$ for…

Let $C^{QFW}_{n,m}$ denote the total cost of the Quick-Find-Weighted algorithm through its first $m$ mergers, and let $\build{\longrightarrow }{}_{\mathcal L_2}$ denote convergence…

Let $(a_0,a_1,\dots,a_l)$ be a sequence generated by the CCL procedure, and let $\pi$ be the fast forward permutation coded by this sequence. Choose $x\in\{0,\dots,N-1\}$ uniformly…

Let $G$ be a planar graph with $n\geq 3$ vertices. A balanced four-coloring is a proper $4$-coloring in which each color is used on fewer than $n/2$ vertices. Linear-time balanced…

Linear-time certifying algorithm conjecture. For every fixed positive integer $k$, there is a certifying algorithm that runs in time

Let an equitable $k$-coloring be a proper $k$-coloring whose color classes have sizes differing by at most one, and let $d(x)$ denote the degree of a vertex $x$. Kierstead-Kostochk…

Let $G$ be a string graph, let $n$ be its size, and let $\omega(G)$ and $\beta(G)$ denote the parameters used by the source. An $f(\omega(G),\beta(G))$-coloring is a coloring with…

Universal termination conjecture. There exist universal functions $S(a,b,c)$ and $T(a,b,c,p,k,n)$ such that, when the proposed algorithm is guided by this pair of functions, it ter…

Let $Q_1,\ldots,Q_n$ be points and let $B_1,\ldots,B_n$ be edges of a convex hull, with each point matched to one edge and the resulting triangles considered as in the preceding he…

Exact growth conjecture. For each positive integer $N$, one has

Let $G$ be a 4-connected finite graph with $n$ vertices and $m$ edges. The linear-time decomposition algorithm conjecture. There is an algorithm that returns the tetra-separation d…

Let $\lambda$, $mu$, and $nu$ be partitions of $n$, and suppose that $f^{\lambda}\geq f^{mu}\geq f^{nu}$. Kronecker algorithm conjecture. The Kronecker coefficient $g(\lambda,mu,nu)$…

Let $\lambda$, $mu$, and $nu$ be partitions such that $|\lambda|=|mu|+|nu|$. Assume $c^{\lambda}_{mu,nu}>0$. Output-sensitive Littlewood–Richardson conjecture. There exists a classica…

Let $\bla$, $\bmu$, and $\bnu$ be partitions such that $|\bla|=|\bmu|+|\bnu|$. Littlewood–Richardson algorithm conjecture. There exists a classical algorithm running in time … that…

Hypercube-decomposition conjecture. For any hypercube decomposition $[u,z]$ of $[u,v]$,

Let $A_{fi}$ be the function-field ring considered in the paper, and let a pseudo-matrix over $A_{fi}$ represent a module by its coefficient ideals and matrix. Polynomial-time Herm…

Let $G_i'$ be the graph associated with a node $X_i$ of the smooth tree-decomposition, and let $f$ and $g$ be partial colorings of $G_i'$. For each tuple…

For each positive integer $k$, let $c(k)$ denote the exponent for counting copies of an arbitrary $k$-vertex tournament. Recursive counting conjecture. For all $k \ge 3$ it holds t…

For a positive integer $k$, let $c(k)$ be the exponent for counting copies of an arbitrary $k$-vertex tournament, and let $c^*(k)$ be the exponent for counting copies of the transi…

Hochbaum–Nishizeki–Shmoys conjecture. There exists a polynomial-time algorithm that finds a proper edge-coloring of every multigraph $G$ using $\max\\{\Delta(G)+1,\Gamma(G)\\}$ col…

The algorithms use a Weyl group $W$ and a subset $W'\subset W$ in their final optimization step to remove nonmaximal states. Weyl group optimization conjecture. At the last step of…