<p>The problem can be solved in $O(n(m + n \log n))$ time. The solution below is based on one by <a href="http://www.sciencedirect.com/science/article/pii/0167637781900201" rel="nofollow">Grötschel and Pulleyblank</a> to compute shortest paths with an even (odd) number of edges (Gröschel and Pulleyblank in turn contribute it to 'Waterloo-folklore'. <a href="http://www.springer.com/mathematics/applications/book/978-3-540-44389-6" rel="nofollow">Schrijver</a> 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.</p>

<p>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 (<a href="http://dl.acm.org/citation.cfm?id=320229" rel="nofollow">Gabow [1990]</a>). 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.</p>

<p>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 <em>some</em> perfect matching of $G'$ contains $P$ and has the appropriate weight.</p>

<p>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$.</p>

<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$.</p>

CC BY-SA 3.0
2014-05-31T12:52:50.583Z
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?
Andras Farago
CC BY-SA 3.0
2014-05-29T15:00:26.053Z
2014-05-29T19:11:02.293Z
2014-05-29T19:11:02.293Z
Kyle Fox
<p>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 <strong>parity weight</strong> of the path. </p>

<p>What is the complexity of finding the minimum parity weight $s-t$ path? </p>

CC BY-SA 3.0
2014-02-20T06:54:15.630Z
Is finding a **simple** path part of the requirement or just a minimum parity weight path?

Even if the weights are non-negative, it seems that the minimal path might not be simple (think of a triangle of weight 0 connected to an edge leading to $t$ of weight 10).
R B
CC BY-SA 3.0
2014-02-20T12:15:10.943Z
If there is no requirement for the path to be simple, the problem is in $P$:

Create two copies of the graph $G_1,G_2$, such that there are no edges within $G_1,G_2$ but there are between the graphs.
Set the weights to be 0 from $G_2$ to $G_1$ and their original weights from $G_1$ to $G_2$.

Now search for a path from the copy of $s$ in $G_1$ to either copy of $t$.
R B
CC BY-SA 3.0
2014-02-20T13:05:14.290Z
Yes, if the path does not have to be simple, then the problem is indeed in $P$. It is not clear, however, what happens if we insist to finding a simple path that cannot intersect itself. I would tend to think that this requirement makes the problem NP-hard, but I am not sure.
Andras Farago
<cc.complexity-theory><graph-algorithms>
Minimum Parity Weight Path - what is the complexity?
Andras Farago
# Minimum Parity Weight Path - what is the complexity?

(Asked by: username_0 on 2014-02-20)

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?

**Tags:** cc.complexity-theory, graph-algorithms

> **Comments:**
> **username_1**: Is finding a **simple** path part of the requirement or just a minimum parity weight path?  Even if the weights are non-negative, it seems that the minimal path might not be simple (think of a triangle of weight 0 connected to an edge leading to $t$ of weight 10).  
> **username_1**: If there is no requirement for the path to be simple, the problem is in $P$:  Create two copies of the graph $G_1,G_2$, such that there are no edges within $G_1,G_2$ but there are between the graphs. Set the weights to be 0 from $G_2$ to $G_1$ and their original weights from $G_1$ to $G_2$.  Now search for a path from the copy of $s$ in $G_1$ to either copy of $t$.  
> **username_0**: Yes, if the path does not have to be simple, then the problem is indeed in $P$. It is not clear, however, what happens if we insist to finding a simple path that cannot intersect itself. I would tend to think that this requirement makes the problem NP-hard, but I am not sure.  

---

## 1 answers

### Answer by username_2 on 2014-05-29. Score: 6 | Accepted answer

The problem can be solved in $O(n(m + n \log n))$ time. The solution below is based on one by [Grötschel and Pulleyblank](http://www.sciencedirect.com/science/article/pii/0167637781900201) to compute shortest paths with an even (odd) number of edges (Gröschel and Pulleyblank in turn contribute it to 'Waterloo-folklore'. [Schrijver](http://www.springer.com/mathematics/applications/book/978-3-540-44389-6) 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]](http://dl.acm.org/citation.cfm?id=320229)). 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$.

> **Comments:**
> **username_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?  

---

