72 problems

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-…

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…

The parameterized complexity classes in the hierarchy … form a hierarchy of distinct classes. Strictness conjecture for the W-hierarchy. The inclusions in the $\mathsf{W}$-hierarch…

Proper-containment conjecture. Each of these containments is proper.

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…

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 $(G,R)$ be an annotated graph, let $k$ be the number of terminal pairs, and write … Here $f$ denotes a computable function, and $|G|$ denotes the size of $G$. XP tractability c…

Monadic NIP characterization. First-order model checking is fixed-parameter tractable on ${\mathcal C}$ if and only if ${\mathcal C}$ has monadic NIP; for hereditary classes of rel…

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…

VFPT versus VW[1] conjecture. There exists a weft-$1$-definable parameterized p-family that is not in $\mathrm{VFPT}$.

Valiant's conjecture. There exists a Boolean-definable sequence $(f_d)_{d\in\mathbb{N}}$ with

A class of relational structures is independent when it has the relevant independence property, and it is hereditary when it is closed under induced substructures. A TOWS graph is…

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…

Parameterized complexity classes are denoted by $\textsf{W[1]}$ and $\textsf{FPT}$. W[1]-FPT separation conjecture. The classes $\textsf{W[1]}$ and $\textsf{FPT}$ are not equal. Th…

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…

Let $(G,\chi)$ be a $1$-colorful graph, and let … be the set of vertices with color $1$. A class of colorful graphs is colorful minor-closed if it is closed under taking colorful m…

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

Let $G$ be a graph from a nowhere dense class, and let $k$ be the parameter bounding the size of the connected dominating sets in the token-jumping connected dominating set reconfi…

Currently, the focus is on monadically dependent graph classes, that is, graph classes $\mathcal{C}$ such that $\mathcal{G} \not\preceq_{\mathsf{FO}} \mathcal{C}$, where…

The parameterized complexity classes form the hierarchy … The first levels satisfy $\mathsf{W}[1]=\mathsf{A}[1]$ and $\mathsf{W}[i]\subseteq \mathsf{A}[i]$ for every $i\geq 2$. Str…

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 a first-order sentence $\phi$ define the hereditary first-order model-checking problem $\operatorname{Her}(\phi)$. A problem is coNP-intermediate if it belongs to coNP but is n…

Let $\mathcal{G}$ be an arbitrary $(\operatorname{tw},\operatorname{had})$-bounded graph class, meaning that there is a function $f$ with…

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…