Shortest path with odd weight

Question

Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.

We are looking for an algorithm for finding the weight of the shortest odd path between any two vertices in the graph.

If possible, describe one algorithm that is reduction-based (that is, make some modification to the graph so that application of Floyd-Warshall, or any other "known" algorithm, and then deciphering the answer will give the result, see http://en.wikipedia.org/wiki/Reduction_(complexity)) and one that is "direct" (that is, make some modification to Floyd-Warshall in order for it to solve this problem).

Answer 1

Direct

I answered this here:

https://stackoverflow.com/questions/11900830/using-floyd-warshall-algorithm-to-determine-an-odd-matrix/11902296#11902296

Basically:

1. Run the algorithm twice (literally a for loop that runs 2 times around the F-W loops) because the path may be longer than the number of vertices
2. Save both the best odd and best even path costs for each pair of vertices - instead of cost[v1][v2] I use cost[v1][v2][evenness].

Proof that running the algorithm twice is sufficient: let's assume a path in the graph has more than 2V vertices -> at least one vertex C must appear 3 times -> it must appear at least twice with the same evenness-of-path-up-to-this-point E. So the path is of the form (with C(E) meaning "vertex C appearing with evenness E"):

P0 - C(E) - P1 - C(E) - P2

where P0, P1 and P2 are segments of the path (perhaps empty). But this path has the same evenness, initial and final state as:

P0 - C(E) - P2

And due to non-negative weights, the former path can't be shorter. So running the algorithm twice is sufficient.

Reduction

From G, create G' in the following way:

1. For each vertex Vi in G, add Vi_odd and Vi_even to G' (a simple implementation is: i_even := 2*i, i_odd := 2*i+1, and the inverse, i = i_either/2)

2. For each edge in G, let Vi be the source vertex, Vj the target vertex, W the weight. If W is odd, add edges (Vi_odd, Vj_even) and (Vi_even, Vj_odd) with weight W. If W is even, add edges (Vi_even, Vj_even) and (Vi_odd, Vj_odd) with weight W.

Run F-W on G'. The weight of the path from Vi_even (initial path weight is 0 = even) to Vj_odd in G' is the weight of the shortest odd path from Vi to Vj in G. The weight of the path from Vi_even to Vj_even is the shortest even path.

Answer 2

Homework? I start with hints. Integer values assumed.

Reduction. Make two copies of the vertices in the graph (odd and even) and rewire the graph such that each odd length edge of the graph is between the even and odd copies.

Direct. The algorithm keeps two values (for each pair of vertices): the length of the even length and odd length shortest paths. You can adapt Floyd if you realize that odd+odd = even (etc).

Answer 3

Sorry for digging up this old topic, but all proposed algorithms on this thread are wrong!

This problem is, in fact, NP-hard (and even NP-complete): The paper "Even Cycles in Directed Graphs" by Carsten Thomassen proves in Proposition 2.1 that the problem of finding an odd / even length directed cycle in a digraph through a given edge (!) is NP-complete. Now, we can in fact solve this problem using the algorithm described in this thread: Choose weight = 1 for every edge. Let e be the selected edge that an even cycle should pass through, say e = (v,w). Now, find an odd path from w to v. This path exists if and only if there exists an even cycle through e. This shows that this algorithm must be wrong.

I believe that the suggested algorithm does return an odd-length WALK though, but not a path (vertices may be repeated).

Please upvote this reply so people don't find false info on this thread!

For sake of completeness, I will state some info on this and similar problems: It is NP hard to find an odd or even length path in a digraph between two vertices. It is NP hard to find an odd or even length cycle going through a fixed edge in a directed graph. However, it is polynomial-time solvable to find an odd directed cycle in a digraph. The intuition behind this is the following: If we find an odd walk (repeated vertices), it must contain an odd cycle too. It's just not necessarily the case that this odd cycle runs through the edge we want it to run through. Finding a shortest odd-length cycle is also possible (algorithm can be found in the paper mentioned above). Regarding even-length cycles in digraphs: This problem is polynomial-time solvable but was, for a very long time, unsolved, see https://cstheory.stackexchange.com/questions/19703/finding-even-cycle-in-directed-graphs/19704 .