{"id":"arxiv/2607.16889","url":"https://arxiv.org/abs/2607.16889","tags":["cs.DM","math.CO"],"score":0,"title":"Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth","domain":"cs.DM","source":"arxiv","authors":["Gaétan Berthe","Florent Foucaud","Tuomo Lehtilä","Aline Parreau"],"reviews":0,"subject":"cs.DM","summary":"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)$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-18","reactions":{}}