25 problems

Let $\mathcal{C}$ be a hereditary class of relational structures. Here, model-checking on $\mathcal{C}$ is tractable if there is an algorithm that, on input a structure…

Let ${\mathscr C}$ be a hereditary class of graphs. A class is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from the class using a fixed first-…

Independent-planar-minor MIS conjecture. For every planar $H$ and every $k$, MIS is polynomial-time solvable on the class of $kH$-free graphs.

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…

Let $\mathcal{C}$ be a hereditary class of graphs. FO model-checking conjecture. There is an FPT first-order model-checking algorithm for graphs in $\mathcal{C}$ if and only if…

Let $k$, $\delta$, and $h$ be the parameters of the Map-$\varepsilon$-PDD problem, where $h$ is the value of $H$ in a phylogenetic tree. Map-$\varepsilon$-PDD conjecture. Map-…

Let $\mathcal{C}$ be a $1$-colorful minor-closed class, meaning a class of $1$-colorful graphs closed under taking colorful minors. A $1$-colorful rainbow $(k\times k)$-grid is the…

FP-versus-symmetric subtraction conjecture. $[\mathrm{FP}-\text{\normalfont\textsc{\#mon2sat}}]^{\log}$ is strictly contained in…

Let $q$-CNFSAT denote the satisfiability problem for conjunctive normal form formulas whose clauses have at most $q$ literals, and let $n$ be the number of variables in the input f…

Let $\mathcal{H}$ be a minor-closed graph class. For a graph $G$, let $\mathsf{id}_{\mathcal{H}}(G)$ denote the minimum number of edge identifications needed to transform $G$ into…

Let $(G,\ell)$ be an instance of textsc{Induced Matching}, together with a path decomposition of $G$ of width $\operatorname{pw}$. The Strong Exponential Time Hypothesis (SETH) ass…

GI-hardness conjecture. $\textsc{Comp-Sub}(\mathcal{PM})$ is $\GI$-hard on $C_{k\geq 6}$-free graphs.

Let $G=(V,E)$ be the graph in an instance of M-EPVCB, and let $\Delta(G)$ denote its maximum degree. The degree-deficit hardness conjecture. M-EPVCB is W[1]-hard with respect to th…

Let $G=(X,Y,E)$ be the edge-weighted bipartite graph in an instance of M-EPVCB, and let $|X|$ and $|Y|$ denote the sizes of its two bipartition classes. The minimum-side hardness c…

Let $\mathscr C$ be a hereditary class of structures. A class is monadically NIP if it remains NIP after arbitrary unary predicates are added. Hereditary first-order model-checking…

Induced-subgraph counting hardness conjecture. Then $\#{\textsc{IndSub}}(\Phi)$ is $\#{\mathsf{W[1]}}$-hard.

Let $G$ be a graph on $n$ vertices, and let $k$ be a nonnegative integer. Suppose that at least $n-k$ vertices of $G$ have degree at least $n/2-k$. Combined parameterization conjec…

RPP PSAKS conjecture. RPP has a PSAKS with respect to the parameter $c$.

Let $\mathcal{D}$ be a graph class, and for every FO formula $\psi(x,y)$ let $F_\psi$ be a graph such that $F_\psi$ is not an induced subgraph of any member of…

Let $\mathcal{C}$ be a nowhere dense graph class, and let $\mathcal{D}$ be a graph class FO interpretable in $\mathcal{C}$. FO model-checking conjecture. The class $\mathcal{D}$ ha…

Let $\mathcal{G}$ be a graph class with bounded expansion, let $I$ be a simple first-order graph interpretation scheme, and let $\varphi$ be a first-order property to be tested. Th…

The nowhere-dense domination-set kernelization dichotomy. If $\mathcal{C}$ is nowhere dense, then for each $r\in\mathbb{N}$, the textsc{Distance-$r$ Dominating Set} problem admits…

Let $G$ be a graph with a given rotation system, and let $k\geq 1$ be an integer. A drawing of $G$ respecting the prescribed rotation system is one in which the clockwise order of…

Cyclability completeness conjecture. The problem textsc{Cyclability} is $\mathsf{\Pi}_{2}^{\mathrm{P}}$-complete.

Let $H$ be a hypergraph, and let the incidence treewidth of $H$ be the treewidth of its incidence graph. Generalized-hypertree-width conjecture. Generalized Hypertree Width is W[1]…