Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
Discrete Mathematics
Summary
The authors study a measure called neighbourhood complexity, which counts distinct sets of neighbors in a graph relative to a subset of vertices. They focus on graphs with limited tree-like structure, measured by treewidth and pathwidth, and find specific upper bounds on neighbourhood complexity for these cases. They prove that for graphs with treewidth or pathwidth greater than or equal to 2, the complexity grows roughly like a linear function multiplied by an exponential in the treewidth/pathwidth. They also show these bounds are the best possible by providing examples that reach them. For simpler graphs with treewidth or pathwidth 1, they establish a tighter linear upper bound on neighbourhood complexity.
Authors
Gaétan Berthe, Florent Foucaud, Tuomo Lehtilä, Aline Parreau
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.