Efficiently find maximum XOR on a graph

We are given an undirected graph $G=(V,E)$, $|V| \leq 50$. We are also given a starting vertex $s$. Each vertex $v$ of the graph is associated with a natural number $N_v$. Initially our profit is $R=N_s$.

Now we have to traverse the graph beginning from $s$ in an order. We can visit each vertex or edge any number of times. Whenever we reach a vertex $v$, $R=R \operatorname{XOR} N_v$. (Note that if we visit $k$ times a vertex $v$, then we will XOR $k$ times with $N_v$.)

Find the maximum value of $R$ that can be obtained while traversing $G$.

Note: Here traversal means walk beginning from $s$.

• What are your thoughts on the question? – Yuval Filmus Nov 13 '16 at 7:46
• @YuvalFilmus At present time, I don't know how to approach this problem. From some other forum, I got this link just now, but haven't looked at it yet. – user3763284 Nov 13 '16 at 8:22
• Is this an ongoing programming competition? – Yuval Filmus Nov 13 '16 at 8:25
• No sir, this was from a previous online tests, which ended a week ago. – user3763284 Nov 13 '16 at 8:28
• Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Raphael Nov 13 '16 at 9:40

I'm going to first assume that your graph is connected; that is, every node of the graph is reachable from $s$. We'll relax this condition down the line, but for now, it simplifies the problem.

Now, let's start with what we know. If $G$ is connected, then we can visit every vertex; that is, there's some path $p$ that goes to each vertex $t$.

Let's examine such a path $p = (p_0 = s), p_1, \dots, p_{n-1}, (p_n = t)$. By definition, we know that the value of such a path is just $R(p_0, \dots, p_n) = \bigotimes_k N_{p_k}$. In addition, if at $p_n = t$, we immediately turn back and travel backwards on $-p$ (the reverse path of $p$), then we would eventually arrive back on $s$ with a value of \begin{align*} R(p, -p) &= R(s, \dots, p_{n-1}, t, p_{n-1}, \dots, s)\\ &= \left(\bigotimes_{0 \le k \le n} N_{p_k}\right) \otimes \left(\bigotimes_{0 \le k \le \bf n-1} N_{p_k}\right) \\ &= (N_{p_0} \otimes N_{p_0)} \otimes (N_{p_1} \otimes N_{p_1)} \otimes \dots \otimes (N_{p_{n-1}} \otimes N_{p_{n-1}}) \otimes N_t \end{align*}

Recall that xor has the property that $x \otimes x = 0$, the identity. therefore, any path from $s$ to $t$ and back to $s$ just gives a value of $N_t$. In fact, any conjunction of paths $$s \stackrel{p_1}{\to} v_1 \stackrel{-p_1}{\to} s \stackrel{p_2}{\to} v_2 \stackrel{-p_2}{\to} s \stackrel{p_3}{\to} \dots \stackrel{-p_n}{\to} s$$ gives a value of $$N_s^{n + 1} \otimes \bigotimes_k^n N_{v_k}$$ Furthermore, we can get rid of the $s^{n+1}$ term by deciding to stop the final path immediately before the terminal vertex if it falls on an even $n$.

In essence, this tells us that it is possible to construct a walk starting at $s$ such that the value of this walk is $\bigotimes_{v \in S \subseteq V(G)} N_v$ for any subset of vertices of $G$.

This then suggests that your problem reduces down to finding a subset of vertices $S \subseteq V(G)$ such that $\bigotimes_{s \in S} N_s$ is maximum over $V(G)$.

At first glance, this might seem like a non-trivial covering/knapsack problem. For one thing, the naive strategy here seems to be to try out every subset of $V(G)$. In addition, there doesn't seem to be any sort of monotonicity, continuity, or even some form of "optimal substructure" property for us to exploit.

Fortunately for us, this problem admits a relatively nice representation in terms of a linear algebraic system, and its solution process is equivalent to finding the rank of an induced matrix, or alternatively, Gaussian Elimination.

Now, suppose that we have a set of annotated vertices $N = \{N_v \mid v \in V(G)\}$, how do we represent this as a linear system?

Well, given an integer $N_v = 1011\cdots01_2$ in binary, then we can think of it as the column vector $$[\![N_v]\!] = \left(\begin{array}{c}1\\0\\ \vdots \\ 0 \\ 1\end{array}\right)$$ Now, let's consider the semi-ring $(+ = \otimes, \times = \max = \times_{\mathbb{N}})$ over bits (0, 1). Here the addition operation is bit xor and the multiplication operation is the usual integer multiplication, which also happens to be the $\max$ operation or the $\wedge$ conjunction operation.

We wish to find coefficients $c_0, c_1, \dots, c_n$ such that $$c_0 [\![N_{v_0}]\!] + \dots + c_n [\![N_{v_n}]\!]$$ is "maximized". In particular, we wish to analyze the $A_N: k \times n$ system $$\left(A_N = \left(\begin{array}{ccc}[\![N_{v_0}]\!] & \cdots & [\![N_{v_n}]\!]\end{array}\right)\right) \left(\begin{array}{c} c_0 \\ \vdots \\ c_n \end{array}\right)$$ where $k$ is the size of your bit-vectors (likely $32$ or $64$). Now, chances are, this system is over-determined (but also rank-deficient). Therefore, our first instinct will be to reduce this system to reveal its rank structure.

Doing this ends up giving us an efficient algorithm: Gaussian Elimination.

The idea is as follows. We try to solve the problem of $$A_N c = \left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)$$ through Gaussian Elimination. Now, I need to emphasize that we are only trying to solve this problem because, chances are, there is no solution! Think about it, $A_N c$ gives the bit-vector that corresponds to the final value of a walk, so if $A_n c = 1$ always has a solution, then it means that our problem is trivial: always return $2^{32} - 1$. In fact, in pretty much all interesting cases, there's no way to satisfy this attempted equality.

"What? Why are you doing this to me then?"

Simple, we actually inspect a trace of the algorithm rather than the final solution. In particular, at each iteration of Gaussian Elimination, we might find ourselves in one of two situations. Either everything still goes fine and dandy, and we can continue elimination, or we reach a contradictory state where we realize that we can't proceed. In the latter case, this corresponds to a case where you need to add a row of zeros and somehow magically pull a one out. In such cases, rather than aborting, we will just concede the impossibility and replace that row in the output with a zero.

More concretely, after $m$ iterations of elimination, we are left with a subproblem in which we only have to analyze the subsystem starting at the $m^{th}$ row. All of the prior rows will be zeros or part of the identity grid.

At the $m^{th}$ row, either there is some column $[\![N_{v_i}]\!]$ in our intermediate matrix that has a leading $1$ in that row, or it's impossible to fill that row in the output.

• In the former case, we will select one such column to pivot (and with a bit of thought, you should choose the largest column), and add (subtract, since the inverse of $\otimes$ is still $\otimes$) it from every other column that still has a leading $1$ in that row.
• Otherwise, we will be forced to concede that the only solution is to place a $0$ in the output at that row and move on.

This then gives an algorithm find a maximum subset with respect to $\otimes$:

for each i from 31 down to 0, do
if there's some maximal vertex v such that N(v) >= 2^i, then
select v as a pivot and remove it from future considerations
for every other vertex u such that N(u) >= 2^i, do
N(u) := N(u) xor N(v)
end for
else,
// Here, we can't possibly hope to fill this row with a one, so
do nothing
end if
end for


Now, the set of pivots that you have selected will give you the maximum xor-subset; just xor them together to find the maximum. The number of pivots also corresponds to the rank of your system, and if there are 32 pivots, then that immediately means that your maximum value is $2^{32} - 1$. If there are 31 pivots, then that means that there's a single 0 somewhere in your bit vector; 30 pivots means that there are two holes; etc.

Finally, we relax the restriction that our graph be connected. Rather, we will simply preprocess the graph and identify the connected component that contains the vertex $s$, and proceed similarly afterwards.

Best of luck!