Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth

Abstract

The neighbourhood complexity $nc(G,k)$ of a graph $G$ is a quantity measuring, for a graph $G$ and an integer $k$, the maximum possible number (over all vertex subsets $S$ of size $k$) $|\{N[v]\cap S, v\in V(G)\}|$ of $S$-neighbourhoods in $G$. This notion is important in structural graph theory and algorithm design (especially in parameterized complexity, in particular model checking and kernelization). While generally $nc(G,k)\leq 2^k$ and this bound can be achieved, it is known that sparse graphs and structured dense graphs have linear neighbourhood complexity, that is, $nc(G,k)\in O(k)$ for any such graph $G$. However, for many graph classes, the best possible constants are not known. We focus on graphs of bounded treewidth and pathwidth, showing that (when $k\geq w+1$) (i) if $G$ has treewidth $w\geq 2$, then $nc(G,k)\leq (k-w+1)2^{w}+w$, and (ii) if $G$ has pathwidth $w\geq 2$, then $nc(G,k)\leq (k-w+2)2^{w-1}+2k-w-2$. Moreover, we provide constructions that reach these bounds, whenever $w\geq 2$ and $k\geq 2w+1$ ($k\geq 2w-1$ for pathwidth). Interestingly, in contrast, we also have the tight bound $nc(G,k)\leq \frac{7}{3}k$, for graphs $G$ with pathwidth 1 or treewidth 1.