English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We revisit the relation between two fundamental property testing models forbounded-degree directed graphs: the bidirectional model in which the algorithmsare 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 areallowed. Czumaj, Peng and Sohler [STOC 2016] showed that for directed graphswith both maximum indegree and maximum outdegree upper bounded by $d$, anyproperty that can be tested with query complexity $O_{\varepsilon,d}(1)$ in thebidirectional model can be tested with $n^{1-\Omega_{\varepsilon,d}(1)}$queries in the unidirectional model. In particular, if the proximity parameter$\varepsilon$ approaches $0$, then the query complexity of the transformedtester in the unidirectional model approaches $n$. It was left open if thistransformation can be further improved or there exists any property thatexhibits such an extreme separation.  We prove that testing subgraph-freeness in which the subgraph contains $k$source components, requires $\Omega(n^{1-\frac{1}{k}})$ queries in theunidirectional model. This directly gives the first explicit properties thatexhibit an $O_{\varepsilon,d}(1)$ vs $\Omega(n^{1-f(\varepsilon,d)})$separation of the query complexities between the bidirectional model andunidirectional model, where $f(\varepsilon,d)$ is a function that approaches$0$ as $\varepsilon$ approaches $0$. Furthermore, our lower bound also resolvesa conjecture by Hellweg and Sohler [ESA 2012] on the query complexity oftesting $k$-star-freeness.

An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs