Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an arbitrary 2-regular detachment of the graph and then generates a Eulerian circuit.
I couldn't find any reference that says, for example, how the algorithm constructs an arbitrary 2-regular detachment of the graph, what data structures it uses, what the time complexity is, and so on. Any ideas?
A version of Tucker's algorithm was used in B. Awerbuch, A. Israeli, and Y. Shiloach, Finding Euler Circuits in Logarithmic Parallel Time, STOC 1984, to find Euler tours efficiently in parallel, and similar ideas can be used to make the algorithm run sequentially in linear time.
Suppose you have a connected graph $G$ in which all vertices have even degree, and start by pairing off edges at each vertex. This forms a collection of cycles that together cover the graph, and Tucker's algorithm works by joining the cycles together one at a time.
To make this repeated joining process efficient, first run a connected components algorithm (e.g. DFS) to find which edges belong to which cycles. Make a bipartite multigraph $H$, where the vertices on one side of the bipartition correspond one-for-one with the vertices of $G$, the vertices on the other side of the bipartition correspond with the cycles you've constructed, and the edges of $H$ correspond to incidences between cycles and vertices in $G$. Construct a spanning tree $T$ of $H$ (e.g. DFS again), rooted at one of the cycle vertices.
Now, for each cycle $C$ that is not the root of $T$, join $C$ to its grandparent in $T$ (by swapping the edge pairing at the common vertex of the two cycles, represented by the parent of $C$), in constant time per join.
The same technique also works for directed graphs (and that's the version that Awerbuch et al use for their main presentation); in that case, the only difference is that you want equally many incoming and outgoing edges at each vertex, and the edge-pairing at each vertex must pair incoming edges with outgoing edges.
It can be done on $O(|E|\log |E|)$, nevertheless implementing it might be cumbersome. I won't get into details of how implement, but a general overview so we can analyze its running time:
For this we will need and adjacency list instead of an adjacency matrix.
Step 1.-, for each vertex split away the vertices, you can split away all the edges for each vertex, it can be done in $O(|E|)$ in total, by traversing each of the adjacency list of each vertex. Then do a DFS to find and store each cycle components in a doubly linked circular list. And we will need an array A of lists, such that list A[i] will have a pointer to each component such that vertex $i$ appears in that component. This can be done while doing DFS.
Step 2 and 3. For each of the lists at each vertex, we will take two adjacent components, and we will ask if both are the same, if they are, remove the first pointer, and continue. If both are different components, join the two lists, for this, in the list we should have a pointer to the position in the doubly linked list of such vertex. Then we can merge two components in $O(1)$. Then remove one of the entries and proceed until we have only one list, and remove it. Repeat for each vertex until only one list remains, such doubly linked circular list will be our eulerian cycle.
The tricky part, and where the $O(\log |E|)$ comes from is on finding if two components are the same. For this we can do relabeling the smallest component, and we will get an amortized time of $O(\log |E|)$, (see Cormen et al's chapter on Kruskal algorithm). Or maybe use a union-find data structure, in such case you can make it amortized $O(|E|\alpha(|E|))$, which is a little better time. It could be possible to get O(|E|) time but a clever use of pointers might be implied and escapes from my intuition currently.
Note that this operation to determine if two components are the same would be in function of $|E|$ instead of $n$, since we are duplicating vertices, but the number of vertices and its duplicates is bounded by $|E|$.
Notice that you are using a graph theory book and for the pure graph theory point of view the complexity is usually irrelevant, and even more irrelevant the implementation details, from that point of view is enough to show that it can be done systematically, and the focus is on how simple you can explain and prove that it is correct, it is very uncommon to find data structures mentioned in such a book, since that is usually out the book's scope.
