{"ID":2835892,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.22289","arxiv_id":"2511.22289","title":"Efficient Trace Frequency Queries in Sparse Graphs","abstract":"Understanding how a vertex relates to a set of vertices is a fundamental task in graph analysis. Given a graph $G$ and a vertex set $X \\subseteq V(G)$, consider the collection of subsets of the form $N(u) \\cap X$ where $u$ ranges over all vertices outside $X$. These intersections, which we call the traces of $X$, capture all ways vertices in $G$ connect to $X$, and in this paper we consider the problem of listing these traces efficiently, and the related problem of recording the multiplicity (frequency) of each trace. For a given query set $X$, both problems have obvious algorithms with running time $O(|N(X)| \\cdot |X|)$ and conditional lower bounds suggest that, on general graphs, one cannot expect better. However, in certain sparse graph classes, more efficient algorithms are possible: Drange \\etal (IPEC 2023) used a data structure that answers trace queries in $d$-degenerate graphs with linear initialisation time and query time that only depends on the query set $X$ and $d$. However, the query time is exponential in $|X|$, which makes this approach impractical. By using a stronger parameter than degeneracy, namely the strong $2$-colouring number $s_2$, we construct a data structure in $O(d \\cdot \\|G\\|)$ time, which answers subsequent trace frequency queries in time $O\\big((d^2 + s_2^{d+2})|X|\\big)$, where $\\|G\\|$ is the number of edges of $G$, $s_2$ is the strong $2$-colouring number and $d$ the degeneracy of a suitable ordering of $G$. We demonstrate that this data structure is indeed practical and that it beats the simple, obvious alternative in almost all tested settings, using a collection of 217 real-world networks with up to 1.1M edges. As part of this effort, we demonstrate that computing an ordering with a small strong $2$-colouring number is feasible with a simple heuristic.","short_abstract":"Understanding how a vertex relates to a set of vertices is a fundamental task in graph analysis. Given a graph $G$ and a vertex set $X \\subseteq V(G)$, consider the collection of subsets of the form $N(u) \\cap X$ where $u$ ranges over all vertices outside $X$. These intersections, which we call the traces of $X$, captu...","url_abs":"https://arxiv.org/abs/2511.22289","url_pdf":"https://arxiv.org/pdf/2511.22289v1","authors":"[\"Christine Awofeso\",\"Pål Grønås Drange\",\"Patrick Greaves\",\"Oded Lachish\",\"Felix Reidl\"]","published":"2025-11-27T10:12:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}