Reference for mixed graph acyclicity testing algorithm? A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction an orientation of a mixed graph is obtained by assigning a direction to each undirected edge. A set of edges forms a cycle in a mixed graph if it can be oriented to form a directed cycle. A mixed graph is acyclic if and only if it has no cycles.

This is all standard and there are many published papers mentioning acyclic mixed graphs. So the following algorithm for testing acyclicity of mixed graphs must be known:

Repeat the following steps:


Remove any vertex that has no incoming directed edges and no incident undirected edges, as it cannot be part of any cycle.
If any vertex has no incoming directed edges but it has exactly one incident undirected edge, then any cycle using the undirected edge must come in on that edge. Replace the undirected edge by an incoming directed edge.


Stop when no more steps can be performed. If the result is an empty graph, then the original graph must necessarily have been acyclic. Otherwise, starting from any vertex that remains, one can backtrack through the graph, at each step following backwards through an incoming edge or following an undirected edge that is not the one used to reach the current vertex, until seeing a repeated vertex. The sequence of edges followed between the first and second repetition of this vertex (in reverse order) forms a cycle in the mixed graph.

The Wikipedia article on mixed graphs mentions acyclic mixed graphs but doesn't mention how to test them, so I'd like to add to it something about this algorithm, but for that I need a published reference. Can someone tell me where it (or any other algorithm for testing acyclicity) appears in the literature?
Finding mixed cycles in a mixed graph is equivalent to finding elementary directed cycles (of length >=3) in the corresponding directed graph. The corresponding directed graph is obtained from the mixed graph by replacing each undirected edge by two directed edges pointing in opposite directions. Proof: (1) Each elementary directed cycle (of length >=3) in the digraph corresponds directly to a mixed cycle in the mixed graph. (2) Each mixed cycle in the mixed graph contains an elementary mixed cycle of length >=3, and each such cycle corresponds directly an elementary directed cycle (of length >=3) in the directed graph. (1) and (2) together prove both directions of the statement, qed. So we are looking for references how to compute (all?) elementary cycles (of length >=3) in a directed graph.

The comments indicate that cs.stackexchange contains some answers to this question, but it is unclear how to organize the results into a concise answer. This blog post seems to nicely summarize the (most?) important references:


  Algorithm by R. Tarjan
  
  The earliest algorithm that I included was published by R. Tarjan in 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

  
  Algorithm by D. B. Johnson
  
  The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

  
  In the worst case, Tarjan's algorithm has a time complexity of O(n⋅e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph.
  
  Algorithm by K. A. Hawick and H. A. James
  
  The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

  
  In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices.


The acyclicity testing itself seems to be easy: Compute the strongly connected components of the graph. Any (elementary) cycle is completely contained in a strongly connected component. A strongly connected component contains an elementary cycle iff it is not an undirected tree.

David Eppstein's proposed algorithm additionally computes one elementary cycle as evidence, and the above algorithms enumerate all elementary cycles. Any vertex or edge not contained in an elementary cycle could be deleted as a preprocessing step to improve the speed of the above algorithms. David Eppstein's algorithm could be used for that purpose, but even if only used on the strongly connected components, it won't delete every possible vertex or edge that can be deleted. But even if it could be extended to do so (computing the block-cut tree at least allows to delete every possible vertex that can be deleted), it is unclear whether this would really improve the speed of the above algorithms.