Property testing in directed graphs
Yaron Orenstein
Abstract:
The main focus of this talk is on property testing in directed graphs.
Property testing problems are relaxations of decision problems.
Namely, a property testing algorithm for a graph property $P$ is given query
access to a graph $G$ and a distance parameter $\epsilon$. If $G$ has the
property $P$, then the algorithm should accept with high constant probability,
and if $G$ is $\epsilon$-far from having the property $P$, then the algorithm
should reject with high constant probability. Both the types of queries allowed
and the distance measure used (which determines when a graphs is $\epsilon$-far
from having a property), may vary, depending on the types of graphs considered
(e.g., dense, bounded-degree, or sparse and unbounded-degree).
I will survey known results for testing properties of directed graphs,
and will present several new results. These include a testing algorithms
for Eulerianity in bounded degree graphs and in unbounded-degree sparse graphs,
as well as an almost matching lower bound for the latter. If time permits,
I will also shortly discuss testing $k$-edge connectivity of directed graphs
(both in the bounded-degree case and in the unbounded-degree (sparse) case),
and $(k,\ell)$-edge-connectivity orientability (which is a property of undirected
graphs that is related to directed graphs).