Testing Depth First Search Numbering
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914024173600768 |
|---|---|
| author | Czumaj, Artur Sohler, Christian Walzer, Stefan |
| author_facet | Czumaj, Artur Sohler, Christian Walzer, Stefan |
| contents | Property Testing is a formal framework to study the computational power and complexity of sampling from combinatorial objects. A central goal in standard graph property testing is to understand which graph properties are testable with sublinear query complexity. Here, a graph property P is testable with a sublinear query complexity if there is an algorithm that makes a sublinear number of queries to the input graph and accepts with probability at least 2/3, if the graph has property P, and rejects with probability at least 2/3 if it is $\varepsilon$-far from every graph that has property P.
In this paper, we introduce a new variant of the bounded degree graph model. In this variant, in addition to the standard representation of a bounded degree graph, we assume that every vertex $v$ has a unique label num$(v)$ from $\{1, \dots, |V|\}$, and in addition to the standard queries in the bounded degree graph model, we also allow a property testing algorithm to query for the label of a vertex (but not for a vertex with a given label).
Our new model is motivated by certain graph processes such as a DFS traversal, which assign consecutive numbers (labels) to the vertices of the graph. We want to study which of these numberings can be tested in sublinear time. As a first step in understanding such a model, we develop a \emph{property testing algorithm for discovery times of a DFS traversal} with query complexity $O(n^{1/3}/\varepsilon)$ and for constant $\varepsilon>0$ we give a matching lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05132 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Testing Depth First Search Numbering Czumaj, Artur Sohler, Christian Walzer, Stefan Data Structures and Algorithms Property Testing is a formal framework to study the computational power and complexity of sampling from combinatorial objects. A central goal in standard graph property testing is to understand which graph properties are testable with sublinear query complexity. Here, a graph property P is testable with a sublinear query complexity if there is an algorithm that makes a sublinear number of queries to the input graph and accepts with probability at least 2/3, if the graph has property P, and rejects with probability at least 2/3 if it is $\varepsilon$-far from every graph that has property P. In this paper, we introduce a new variant of the bounded degree graph model. In this variant, in addition to the standard representation of a bounded degree graph, we assume that every vertex $v$ has a unique label num$(v)$ from $\{1, \dots, |V|\}$, and in addition to the standard queries in the bounded degree graph model, we also allow a property testing algorithm to query for the label of a vertex (but not for a vertex with a given label). Our new model is motivated by certain graph processes such as a DFS traversal, which assign consecutive numbers (labels) to the vertices of the graph. We want to study which of these numberings can be tested in sublinear time. As a first step in understanding such a model, we develop a \emph{property testing algorithm for discovery times of a DFS traversal} with query complexity $O(n^{1/3}/\varepsilon)$ and for constant $\varepsilon>0$ we give a matching lower bound. |
| title | Testing Depth First Search Numbering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.05132 |