Efficient Trace Frequency Queries in Sparse Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912734131519488 |
|---|---|
| author | Awofeso, Christine Drange, Pål Grønås Greaves, Patrick Lachish, Oded Reidl, Felix |
| author_facet | Awofeso, Christine Drange, Pål Grønås Greaves, Patrick Lachish, Oded Reidl, Felix |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22289 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Trace Frequency Queries in Sparse Graphs Awofeso, Christine Drange, Pål Grønås Greaves, Patrick Lachish, Oded Reidl, Felix Data Structures and Algorithms 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. |
| title | Efficient Trace Frequency Queries in Sparse Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.22289 |