76 problems

Let $p,q$ be positive integers with $p\geq 1$ and $q\geq 2$, and let $i\leq p$ and $j\leq q$. Let $\Psi$ be a family of graphs for which recognizing generating subgraphs isomorphic…

For every fixed planar graph $H$, Maximum Independent Set is solvable in polynomial time on the class of $H$-induced-minor-free graphs.

Given a finite point set $P\subset\mathbb{R}^2$ with $|P|=n$, let $T$ range over spanning trees on $P$, with each edge weighted by its Euclidean length. Define the dilation of $T$…

Let $G_{\mathrm{frb100\text{-}40}}=(V,E)$ be the publicly specified $4{,}000$-vertex Model-RB benchmark graph. Determine its independence number…

Given a weighted graph $G=(V,E,w)$, where $w:E\to\mathbb{R}_{\ge 0}$, find an integral cycle basis $\mathcal{B}$ minimizing its total weight…

Given a graph $G=(V,E)$ and an integer $k$, determine whether there exists an edge set $F\subseteq E$ with $|F|\le k$ such that every connected component of $G-F$ has diameter at m…

Given local random-neighbor access to an unknown unweighted graph $G$ with $n$ vertices, let $N_G$ denote its normalized adjacency matrix and let…

Let $G=(V,E)$ be a simple graph, directed or undirected, with positive real-valued edge weights, and let $s,t\in V$. When the graph is accessed through vertex and incident-edge que…

Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,

Polynomial-time computation conjecture. The following problem can be solved in polynomial time: given a graph $G \in \mathcal{G}(\widehat{C}_{6},\widehat{C}_{7})$, output $WCW(G)$.

Xu et al.'s conjecture. The maximum forcing number of $G$ can be computed in polynomial time.

Polynomial-time dimension conjecture. The dimension of a poset given its linear extension graph can be determined in polynomial time.

Gartland and Lokshtanov's conjecture. For every fixed $r$ and CMSO$_2$ formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS and $\operatorname{lcol}(3)$ can be solved in polynomi…

Let $\mathscr C$ be a hereditary class of graphs. A class is dependent if it has the model-theoretic non-independence property, and first-order model checking is fixed parameter tr…

Worst-case output-size conjecture. For every $\varepsilon>0$, there exists a sourceless digraph $D$ such that, for every vertex $v$ of $D$, every quasi-kernel returned by the algor…

Small Quasi-Kernel Conjecture. The digraph $D$ contains a quasi-kernel of order at most $\frac{n}{2}$.

Let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid and let $K_{t,t}$ be the complete bipartite graph with both sides of the bipartition of size $t$. For a positive integer $t$, l…

Let $D$ be a connected plane digraph and let $k$ be an integer. The Directed Plane Strong Connectivity Augmentation problem asks whether there is a set $X\subseteq V(D)^2$ with…

Let $H$ be a simple graph. In Max Partial $H$-Coloring\, the input is a graph $G$ with a revenue function $\mathsf{rev}:V(G)\times V(H)\to\mathbb{Q}_{\geq 0}$, an…

NP-hardness conjecture. Minimum Eternal Vertex Cover is NP-hard on series-parallel graphs.

Quadratic-logarithmic lower-bound conjecture. There exist instances of the textsc{Pebble Motion Problem on Trees} for which the length of the shortest solution sequences is

The monadic dependence model-checking conjecture. For every monadically dependent class $\mathscr{C}$ there is a constant $c\in\mathbb N$ and an algorithm that, given a graph…

Hanauer et al.'s conjecture. If $\Delta\leq 5$, then

Hanauer's conjecture. If $\Delta\leq 5$, then

Let $D$ be a semicomplete digraph, and let $x,y$ be distinct vertices of $D$. A longest $(x,y)$-path is an $(x,y)$-path containing the maximum possible number of arcs. Longest path…