Detect cycles of odd total weight in a graph with {0,1}-weighted edges

Question

Given an edge-weighted digraph $G = (V, E \subseteq V^2, w \in E \to \{0, 1\})$, is there an algorithm that returns TRUE if there is a cycle in this graph whose total weight is odd and FALSE otherwise, which runs faster than $O((|V| + |E|)(c + 1))$ (where $c$ is the number of simple cycles in the graph, which is of course $\Omega(2^{|V|})$)?

As the question implies, I already came up with an algorithm that runs in $O((|V| + |E|)(c + 1))$ time. This algorithm involves first running Johnson's simple cycle enumeration algorithm, which gives us all the simple cycles in the graph. Since even + even = even, and all cycles are made by adding together simple cycles, the graph contains a cycle of odd length iff it contains a simple cycle of odd length. Thus, we just compute the parity of the simple cycles and return TRUE if any of them are odd, and FALSE otherwise.

Can anyone come up with a more efficient approach? Ideally, one that is not just "replace Johnson's algorithm with another simple cycle enumeration algorithm that has slightly better asymptotics", since the graphs I'm dealing with really aren't that large, and constant factors may well dominate as a result.

Answer 1

You can solve this in $O(|V| \cdot |E|)$ time.

Construct a digraph with vertices of the form $\langle v,b\rangle$ where $v \in V$, $b \in \{0,1\}$, as follows: for each edge $v \stackrel{t}{\to} w$ in your graph, add the edges $\langle v,b \rangle \to \langle w,b + t \bmod 2 \rangle$ for each $b \in \{0,1\}$ to the new graph.

Then, for each $v \in V$, check whether there is a path from $\langle v,0 \rangle$ to $\langle v,1 \rangle$ or from $\langle v, 1\rangle$ to $\langle v,0 \rangle$ in this new graph. This can be done with two DFS searches per vertex $v \in V$; each DFS search takes $O(|E|)$ time, so the total running time is $O(|V| \cdot |E|)$ time. The search can be sped up by decomposing the new graph into strongly connected components once and then searching in the dag of components (the metagraph).

Answer 2

Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time.

What is happening here? Let us consider the original edge-vertex incidence matrix. Rows corresponding to cycles sum to zero, since each vertex appears in exactly two edges. Conversely, if we have a set of rows summing to zero, then the degree of each vertex is even. Starting at an arbitrary edge, we can trace a walk that will eventually close onto itself. We remove the corresponding cycle (which need not contain the original edge), and continue. In this way, we see that a set of rows summing to zero correspond to an edge-disjoint union of cycles.

By adding an additional $1$ column to the matrix, we are tracing the parity of the cycle. An odd cycles sums up to the vector $0,\ldots,0,1$. Conversely, if a set of rows sums to $0,\ldots,0,1$, then it corresponds to a set of cycles whose total length is odd, so one of the cycles is odd.

Finally, finding whether a vector is in the row space of the matrix is a standard problem in linear algebra, which can be solved using Gaussian elimination and related algorithms.