Jan Jedelský

Petr Hliněný, Jan Jedelský

We introduce H-clique-width, a new structural measure of graphs that aims to provide a hereditary analogue of the traditional graph product structure. The definition naturally generalises the ordinary clique-width concept. As a result, for a class H of graphs (such as the class of paths), the H-clique-width of a graph G equals the least integer t such that G is isomorphic to an induced subgraph of the strong product of a graph from H and a graph of clique-width t. We study basic properties of H-clique-width and compare it to other established structural parameters of graphs. Notably, we prove that the celebrated Planar graph product structure theorem by Dujmovic et al., and related graph product structure results, can all be formulated with the induced subgraph containment relation. In particular, every planar graph is isomorphic to an induced subgraph of the strong product of a path and a graph of tree-width 39.

Jan Jedelský

The first-order (FO) model checking problem asks, given an FO sentence $ϕ$ and a graph $G$, whether $G$ is a model of $ϕ$. This problem is known to be $\mathsf{AW[*]}$-hard when parameterized by the quantifier rank of the formula. A classical algorithm decides this problem in XP-time parameterized by the number of variables in the formula. Due to $\mathsf{AW[*]}$-hardness, it is natural to ask about the complexity of the problem when restricted to some well-behaved class of graphs. There are many results describing graph classes $\mathcal{C}$ such that the FO model checking problem restricted to $\mathcal{C}$ admits an $\mathsf{FPT}$-time algorithm when parameterized by the quantifier rank of the formula. Parameterization by the quantifier rank is significantly more restrictive than parameterization by the number of variables. We investigate the graph classes $\mathcal{C}$ for which the FO model checking problem restricted to $\mathcal{C}$ admits an $\mathsf{FPT}$-time algorithm when parameterized by the number of variables in the formula. We characterize these classes in the monotone setting, and prove a slightly weaker result in the hereditary setting.