Theoretical Computer Science
cc.complexity-theory graph-algorithms
Updated Wed, 22 Jun 2022 08:14:53 GMT

Minimum Parity Weight Path - what is the complexity?

Consider an undirected graph, with non-negative weights on the edges, and two distinguished nodes $s\neq t$. If $P$ is a simple $s-t$ path in this graph, let $W_1(P)$ denote the sum of the weights on the path, but only adding up every other one, as we traverse the path from $s$ to $t$, starting the summation with the first edge. That is, we add up the first, third, fifth etc. weights on the path. Let us call it the parity weight of the path.

What is the complexity of finding the minimum parity weight $s-t$ path?

Solution

The problem can be solved in $O(n(m + n \log n))$ time. The solution below is based on one by Grtschel and Pulleyblank to compute shortest paths with an even (odd) number of edges (Grschel and Pulleyblank in turn contribute it to 'Waterloo-folklore'. Schrijver contributes their solution to J. Edmonds.) We'll solve the stronger problem of finding a minimum parity weight $s - t$ path with an odd (even) number of edges. The cheaper of the odd and even solutions is the minimum parity weight $s - t$ path.

Let $G=(V,E)$ be your input graph. Create a new graph $G'$. Graph $G'$ contains two copies of $G$ denoted $G_1$ and $G_2$. Every edge $e \in E$ retains its weight in $G_1$ but is given weight $0$ in $G_2$. Finally, for every vertex $v \in V$, $G'$ contains an edge of weight $0$ between $v$'s copies in $G_1$ and $G_2$. Let $v_i$ be the copy of $v$ in graph $G_i$. Find a minimum weight perfect matching $M$ in $G' - s_2 - t_2$ in $O(n(m + n \log n))$ time (Gabow [1990]). Let $P = (V,E')$ contain exactly the edges of $M$ that were copied from $G$ (possibly with multiplicity). One connected component of $P$ is a minimum parity weight $s - t$ path with an odd number of edges, and its parity weight is equal to $M$'s total weight.

To prove the claim, let $P$ a minimum parity weight $s - t$ path in $G$ with an odd number of edges. Let $M$ be the perfect matching of $G' - s_2 - t_2$ containing $G_1$'s copies of the first, third, etc. edges of $P$, $G_2$'s copies of the second, forth, etc. edges of $P$ and the $0$ weight edges between $v_1$ and $v_2$ for every vertex $v$ not in $P$. Matching $M$ has the same weight as $P$'s parity weight, so some perfect matching of $G'$ contains $P$ and has the appropriate weight.

Conversely, let $M$ be a perfect matching in $G' - s_2 - t_2$, and let $P = (V,E')$ contain exactly the edges of $M$ that were copied from $G$ (possibly with multiplicity). For every vertex $v \notin \{s,t\}$, either $v$ is incident to two edges copied from $G$ in $M$, or both copies of $v$ were matched along a $0$ weight edge not present in $G$. Vertices $s$ and $t$ have one matched copy in $M$. Therefore, every vertex of $P$ has degree $2$ or $0$ except for $s$ and $t$ which have degree $1$. Therefore, $s$ and $t$ lie in the same connected component of $P$, and that component is a path. Further, when tracing the edges of that path from $s$ to $t$ you find they come from $G_1$, then $G_2$, then $G_1$, etc. ending with $G_1$. There are an odd number of edges, and the parity weight of that path is the weight of those edges in $G'$. Every other component of $P$ must have non-negative weight, so $M$ is a perfect matching in $G' - s_2 - t_2$ with weight no less than $P$.

Finding a minimum parity weight $s - t$ path with an even number of edges is solved in exactly the same way, except you find a minimum weight perfect matching in $G' - s_2 - t_1$.

• +0 – Nice solution! I wonder what happens if we want to count the weight of not every other edge on the path, but, say, every 3rd edge. Generally, given an integer $k\geq 2$, we may want to add up the weight of every $k$th edge on the path. Let us call it mod $k$ weight. We now know it is solvable in polynomial time for $k=2$. What could be the complexity for $k>2$? Does it become NP-hard? — May 31, 2014 at 12:52