5 problems

Let a graph class have bounded induced matching treewidth, meaning that the induced matching treewidth of every graph in the class is bounded by a common constant. Fix a monadic se…

Let a digraph be given together with $k$ terminal pairs. A collection of paths is half-integral if every vertex belongs to at most two paths. Giannopoulou–Kawarabayashi–Kreutzer–Kr…

Bounded-treewidth induced subgraph conjecture. In polynomial time one can find a maximum-weight induced subgraph of $G$ with treewidth at most $r$.

CMSO₂ meta-theorem. For every fixed $k,r$ and a $\mathsf{CMSO}_2$ formula $\psi$, the $(r,\psi)$-textsc{MWIS} problem can be solved in polynomial time for graphs with induced match…

Fixed-pattern avoidance conjecture. The permutation pattern matching problem with text $t$ and pattern $\pi$ can be solved in time $2^{o(n)}$.