2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – R B Feb 20 '14 at 6:54
  • 3
    $\begingroup$ 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$. $\endgroup$ – R B Feb 20 '14 at 12:15
  • $\begingroup$ 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. $\endgroup$ – Andras Farago Feb 20 '14 at 13:05
6
$\begingroup$

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 to compute shortest paths with an even (odd) number of edges (Gröschel 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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Andras Farago May 31 '14 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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