Search Results

Documents authored by Wang, Yuyang


Document
Track A: Algorithms, Complexity and Games
An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs

Authors: Pan Peng and Yuyang Wang

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


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.

Cite as

Pan Peng and Yuyang Wang. An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 96:1-96:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ICALP.2023.96},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail