On the query complexity of testing orientations for being eulerian. Transactions on Algorithms

Property testing deals with the following relaxation of decision problems: Given a property P and an input structure S, distinguish with high probability between the case where S satisfies the property P and the case where S is "far " from satisfying P. A tester is a randomized algorithm which answers such a question by reading only a small part of the input S, using retrieval procedures that we call queries. Property testing normally deals with very large input structures and/or with costly queries, and thus, the query complexity is assumed to be the most limited resource, rather than the computation time. A great deal of research in property testing is dedicated to graph properties. In most of the testing models, the input is a directed or undirected graph represented by an adjacency matrix or adjacency lists, whose entries are read through queries. In this work we consider the Orientation model suggested by Halevy, Lachish, Newman and Tsur. Here, the input is an orientation of an undirected graph, whose structure is known in advance. The distance between two orientations is defined as the fraction of edges in which they defer. Compared to the standard models, the Orientation model may be more appropriate in cases where the cost of adding or removing a link between two nodes in the graph is significantly higher than the cost of changing th