Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
On the query complexity of testing orientations for being Eulerian
Fischer E., Lachish O., Matsliah A., Newman I., Yahalom O. ACM Transactions on Algorithms8 (2):1-41,2012.Type:Article
Date Reviewed: Jun 15 2012

Since Leonhard Euler created graph theory, in 1736, while studying the seven bridges problem in Königsberg, testing graphs for being Eulerian has been an old and challenging problem. Graphs can be either undirected (the edges have no orientation) or directed (the edges are oriented). An Eulerian path traverses the graph by including each edge exactly once. This paper studies directed graphs. The simple definition may be amplified to state that a directed graph is Eulerian if for every vertex in the graph, its in-degree is equal to its out-degree.

This very long paper is the authors’ collaborative contribution to the problem of testing the orientations of graphs. The query complexity of testing for the Eulerian property is still unknown and is the subject of this paper. The authors develop several algorithms, and upper and lower bounds on their performance. The main difficulty in testing is the possibility that an orientation may have few unbalanced vertices. Fixing the graph for the unbalanced vertices may have adverse consequences on the balanced vertices, making the imbalance even worse than before.

The paper is divided into ten sections. The first section is a history and brief literature review of the Eulerian property of graphs and the problem of determining bounds on the performance of algorithms for testing this property. Section 2, “Preliminaries,” has a set of observations and theorems concerning tests and corrections. The third section, “A Linear Lower Bound for 1-Sided Tests,” concludes that there is no sublinear 1-sided test.

The next three sections are closely related. The fourth section presents three generic tests: “one 1-sided p-test and two 2-sided p-tests for being Eulerian.” The parameter p is “the number of required correction paths in an orientation that is far from being Eulerian.” The three generic tests are a central component of this paper. In section 5, which is coupled with the previous section, the authors find “a general lower bound for the required number p of correction paths.” In the sixth section, they continue the study of lower bounds and “obtain a lower bound for the required number p of correction paths in an expander graph.”

Sections 7, 8, and 9 are also related. Section 7 presents a variation of the test on expander graphs (from the previous section) that is used to develop a 1-sided test and a 2-sided test in the next section. Section 9 is the longest individual section of the paper. The authors derive 1-sided and 2-sided bounds for general graphs.

The tenth and last section presents concluding remarks and is remarkable in its candor. Despite their achievement--developing a test with sublinear performance--the authors admit that the process was very involved and the result should be considered only as a first step. They then proceed to pose several unsolved problems to the readers.

This very theoretical paper is directed toward readers with considerable expertise in graph theory.

Reviewer:  Anthony J. Duben Review #: CR140270 (1211-1166)
Bookmark and Share
  Featured Reviewer  
 
Graph Algorithms (G.2.2 ... )
 
 
Probabilistic Algorithms (Including Monte Carlo) (G.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Algorithms": Date
Planar graph decomposition and all pairs shortest paths
Frederickson G. (ed) Journal of the ACM 38(1): 162-204, 1991. Type: Article
Oct 1 1991
High probability parallel transitive-closure algorithms
Ullman J., Yannakakis M. SIAM Journal on Computing 20(1): 100-125, 1991. Type: Article
Dec 1 1991
Clique partitions, graph compression and speeding-up algorithms
Feder T., Motwani R.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1331991. Type: Proceedings
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy