patternMinor
Path in a graph with a given xor of weights of edges
Viewed 0 times
xorpathedgesgraphwithweightsgiven
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#68892, answer score: 2
Revisions (0)
No revisions yet.