{"ID":2874258,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.05132","arxiv_id":"2509.05132","title":"Testing Depth First Search Numbering","abstract":"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\u003e0$ we give a matching lower bound.","short_abstract":"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 que...","url_abs":"https://arxiv.org/abs/2509.05132","url_pdf":"https://arxiv.org/pdf/2509.05132v1","authors":"[\"Artur Czumaj\",\"Christian Sohler\",\"Stefan Walzer\"]","published":"2025-09-05T14:19:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}