License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.96
URN: urn:nbn:de:0030-drops-181480
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18148/
Peng, Pan ;
Wang, Yuyang
An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs
Abstract
We revisit the relation between two fundamental property testing models for bounded-degree directed graphs: the bidirectional model in which the algorithms are allowed to query both the outgoing edges and incoming edges of a vertex, and the unidirectional model in which only queries to the outgoing edges are allowed. Czumaj, Peng and Sohler [STOC 2016] showed that for directed graphs with both maximum indegree and maximum outdegree upper bounded by d, any property that can be tested with query complexity O_{ε,d}(1) in the bidirectional model can be tested with n^{1-Ω_{ε,d}(1)} queries in the unidirectional model. In particular, {if the proximity parameter ε approaches 0, then the query complexity of the transformed tester in the unidirectional model approaches n}. It was left open if this transformation can be further improved or there exists any property that exhibits such an extreme separation.
We prove that testing subgraph-freeness in which the subgraph contains k source components, requires Ω(n^{1-1/k}) queries in the unidirectional model. This directly gives the first explicit properties that exhibit an O_{ε,d}(1) vs Ω(n^{1-f(ε,d)}) separation of the query complexities between the bidirectional model and unidirectional model, where f(ε,d) is a function that approaches 0 as ε approaches 0. Furthermore, our lower bound also resolves a conjecture by Hellweg and Sohler [ESA 2012] on the query complexity of testing k-star-freeness.
BibTeX - Entry
@InProceedings{peng_et_al:LIPIcs.ICALP.2023.96,
author = {Peng, Pan and Wang, Yuyang},
title = {{An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {96:1--96:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18148},
URN = {urn:nbn:de:0030-drops-181480},
doi = {10.4230/LIPIcs.ICALP.2023.96},
annote = {Keywords: Graph property testing, Directed graphs, Lower bound, Subgraph-freeness}
}
|
Keywords: |
|
Graph property testing, Directed graphs, Lower bound, Subgraph-freeness |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
