5
$\begingroup$

I have an undirected weighted graph with $V$ vertices and $E$ edges. Weight of a path is a xor of weights of the edges on this path. Paths can pass through the same vertices and edges many times. Given two vertices $a$, $b$ and some number $x$ I want to tell if there exists a path of weight $x$. What is the fastest algorithm to solve this problem?

$\endgroup$
  • $\begingroup$ If exponential-time is OK, then you can use DP: let $f(v, y)$ be the length of the shortest path from $a$ to $v$ that gives weight exactly $y$, or $\infty$ if no such path exists. Then $f(v, y) = 1 + \min_{(u,v) \in E}f(u, y \oplus w(u, v))$, if $\oplus$ is XOR. $O(nx)$ time (which is exponential in the number of bits in $x$). $\endgroup$ – j_random_hacker Jan 18 '17 at 12:25
2
$\begingroup$

Arbitrary paths

If you want to know whether there exists a not-necessarily-simple path from $a$ to $b$ with weight $x$, here is a one-sided test:

Compute a cycle basis for the graph, $c_1,\dots,c_k$; this can be done in polynomial time. Let $p$ denote any simple path from $a$ to $b$. Let $W(p)$ denote its weight and $W(c_i)$ the weight of the cycle $c_i$. Then there exists a path of weight $x$ only if $x \oplus w$ is in the linear span of $W(c_1),\dots,W(c_k)$ (with all operations taken over $\mathbb{F}_2$). This condition can be tested in polynomial time.

Why does this work? If there exists a path from $a$ to $b$, then it can be written as the xor (symmetric difference) of $p$ and some subset of $c_1,\dots,c_k$. Thus, its weight is given by $W(p)$ xored with the selected $W(c_i)$ values.

However, the converse doesn't necessarily hold. If $x \oplus w$ is in the linear span of $W(c_1),\dots,W(c_k)$, there is no guarantee that there exists a path from $a$ to $b$. (The linear combination of $W(c_1),\dots,W(c_k)$ might correspond to a set of cycles that form a disconnected graph, and doesn't provide any way to form a path from $a$ to $b$.)

I don't know whether there is a polynomial-time algorithm or not.

Simple paths

If you want to require the path to be a simple path, then the problem is NP-complete, by reduction from Hamiltonian path.

Let $G$ denote your graph. Suppose it has $n$ vertices, with vertices numbered from $1$ to $n$. Modify it to replace each vertex $v$ with two copies $v_0$ and $v_1$, and add an edge between $v_0$ and $v_1$. For each edge $(u,v)$ in the original graph $G$, we'll introduce edges $(u_1,v_0)$ and $(v_1,u_0)$ in the new graph, with weight zero ($0^n$). Each the edge $(v_0,v_1)$ will have a weight from $\mathbb{F}_2^n$ that has the $v$th bit set and all other bits clear (i.e., its weight is $0^{v-1} 1 0^{n-v}$). Let $x$ denote a weight with all bits set (i.e., $1^n$).

Now there exists a simple path from $a_0$ to $b_1$ of weight $x$ in the new graph if and only if there exists a Hamiltonian path from $a$ to $b$ in the original graph. Therefore, any algorithm for your problem with paths restricted to simple paths immediately yields an algorithm for the Hamiltonian path problem, which is known to be NP-complete.

$\endgroup$

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.