18
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ what happens when a vertex has two incident undirected edges, and no other edge? For instance in a undirected triangle. I mean do the rules above cover this case? $\endgroup$
    – Mateus de Oliveira Oliveira
    Commented Aug 24, 2015 at 18:34
  • $\begingroup$ You can't do anything about such a vertex until a different vertex applies the rule that orients one of the edges. If you get stuck with a situation where such vertices exist, and you can't apply any more rules, then your graph contains a cycle. $\endgroup$
    – David Eppstein
    Commented Aug 24, 2015 at 18:56
  • $\begingroup$ Maybe it would make it clearer to consider what happens in the case that your graph is undirected. One way to test whether it's a forest is to remove leaves (degree one vertices) and isolated vertices until you get either an empty graph (it's a forest) or a nontrivial 2-core (a subgraph in which all vertices have degree ≥ 2, which necessarily contains a cycle). The mixed graph algorithm degenerates to this in the undirected case (except that it orients the leaves rather than immediately removing them), just as it degenerates to a standard topological sorting algorithm in the directed case. $\endgroup$
    – David Eppstein
    Commented Aug 24, 2015 at 19:06
  • $\begingroup$ Not sure if you've seen: there's a post on cs.stackexchange that asks a similar question ref. The answerer gives an algorithm to find a cycle in a mixed graph by orienting undirected edges, rejecting the graph if it doesn't exist. There's also paper(s) on determining whether a mixed graph is strongly orientable ref but strangely, couldn't find anything on actually finding connected components in mixed graphs. $\endgroup$
    – Quanquan Liu
    Commented Aug 25, 2015 at 6:45
  • $\begingroup$ Thanks — no, I hadn't seen that. The "find an orientation to make the graph contain a directed cycle" question is definitely the same one, and the algorithm in the answer looks correct. But unlike the one I describe, it's not linear time. $\endgroup$
    – David Eppstein
    Commented Aug 25, 2015 at 7:08

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do any of those references even mention mixed graphs? I know about finding cycles in directed graphs. My question was about extensions of those algorithms to mixed graphs. $\endgroup$
    – David Eppstein
    Commented Aug 30, 2015 at 16:58
  • $\begingroup$ @DavidEppstein Finding mixed cycles in a mixed graph is equivalent to finding elementary cycles (of length >=3) in the corresponding directed graph. Finding a reference for that statement might be challenging, but proving this statement is straightforward. I now added the statement and its proof to the answer. (Also added a remark without proof that computing the block-cut tree allows to delete every possible vertex that can be deleted without affecting the elementary cycles.) $\endgroup$
    – Thomas Klimpel
    Commented Aug 30, 2015 at 20:01
  • $\begingroup$ Ok, but they're still also not linear-time. $\endgroup$
    – David Eppstein
    Commented Aug 30, 2015 at 23:33
  • $\begingroup$ @DavidEppstein The acyclicity testing itself is done in linear time. But you are right, the time any of those algorithms needs to find the first elementary circuit (of length >=3) is not linear (in the worst case). Worse, most available implementations of Johnson's algorithm seem to use more than O((n+e)(c+1)) time, when applied to a single directed circle (with n vertices, e=n edges, and c=1 elementary cycles). Still, this was intended to be a correct answer, because Johnson's paper seems to be the most quoted reference for "finding elementary circuits". $\endgroup$
    – Thomas Klimpel
    Commented Sep 1, 2015 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.