# Finding the paths through a graph that reuse as many of the nodes as possible

I'm implementing an encryption algorithm which does a bunch xor operations to mix up the columns. Because I want to find the lower bound of the number of xor operations, I'm trying to figure out the best way to reuse intermediate results. I've created a graph with all the intermediate results and now want to find the paths through that graph that reuse the most nodes.

Simplified example: I want to calculate $abc$ and $bcd$ from $a,b,c,d$. I can only combine two variables at a time. Combining is commutative: the order does not matter. I've created a graph with all the possible intermediate results ($ab, bc, cd$). Obviously the best way to calculate $abc$ and $bcd$ is to do it like $abc = a (bc)$ and $bcd = d (bc)$. This way you can reuse the result of $bc$ and you end up doing 3 operations, instead of the 4 operations if you would do something like $abc = (ab)c$ and $bcd = (bc)d$.

In other words, I want fo find these paths:

       abc         bcd
|           |
+-----+--+--------+
|        |        |
| ab     bc   cd  |
|        |        |
|      +-+-+      |
|      |   |      |
a      b   c      d


Is there an algorithm suitable for finding this, or is there an algorithm that I can adapt to find this? (If there is an approach that doesn't use graphs, I'd like to learn of it as well).

Actual problem: I have 16 inputs $x_0 \cdots x_{15}$ which are xored like this:

$$\begin{array}{rcl} x_0 &=& x_0 \oplus x_4 \oplus x_7 \oplus x_{10} \oplus x_{12} \oplus x_{14} \oplus x_{15} \\ x_{1} &=& x_1 \oplus x_4 \oplus x_{11} \oplus x_{12} \oplus x_{15} \\ x_{2} &=& x_2 \oplus x_5 \oplus x_8 \oplus x_9 \oplus x_{12} \\ x_{3} &=& x_3 \oplus x_6 \oplus x_9 \oplus x_{10} \oplus x_{13} \\ x_{4} &=& x_0 \oplus x_3 \oplus x_4 \oplus x_8 \oplus x_{10} \oplus x_{11} \oplus x_{14} \\ x_{5} &=& x_0 \oplus x_5 \oplus x_8 \oplus x_{11} \oplus x_{15} \\ x_{6} &=& x_1 \oplus x_6 \oplus x_8 \oplus x_{12} \oplus x_{13} \\ x_{7} &=& x_2 \oplus x_7 \oplus x_9 \oplus x_{13} \oplus x_{14} \\ x_{8} &=& x_2 \oplus x_4 \oplus x_6 \oplus x_7 \oplus x_8 \oplus x_{12} \oplus x_{15} \\ x_{9} &=& x_3 \oplus x_4 \oplus x_7 \oplus x_9 \oplus x_{12} \\ x_{10} &=& x_0 \oplus x_1 \oplus x_4 \oplus x_{10} \oplus x_{13} \\ x_{11} &=& x_1 \oplus x_2 \oplus x_5 \oplus x_{11} \oplus x_{14} \\ x_{12} &=& x_0 \oplus x_2 \oplus x_3 \oplus x_6 \oplus x_8 \oplus x_{11} \oplus x_{12} \\ x_{13} &=& x_0 \oplus x_3 \oplus x_7 \oplus x_8 \oplus x_{13} \\ x_{14} &=& x_0 \oplus x_4 \oplus x_5 \oplus x_9 \oplus x_{14} \\ x_{15} &=& x_1 \oplus x_5 \oplus x_6 \oplus x_{10} \oplus x_{15} \\ \end{array}$$

I want to find groups such as $\{x_0, x_4\}$, $\{x_1, x_4\}$ and $\{x_{0}, x_{4}, x_{10}\}$ that are contained in several of these multiplications.

• What you are asking is likely not what you want. Why exclude cancellations? – Kristoffer Arnsfelt Hansen Dec 3 '14 at 14:10
• What do you mean by cancellations? $a \oplus b \oplus a = b$? – Thom Wiggers Dec 3 '14 at 14:12
• since it is commutative, it seems it suffices to take the intersection of the multiset of letter used, at least in the case where you have $2$ outputs to compute. If you have more, it requires more thinking. – Denis Dec 3 '14 at 15:31
• I have 16 outputs, so yeah. – Thom Wiggers Dec 3 '14 at 15:39

You are looking for the shortest straight-line program to compute a set of formulas involving xor.

This is NP-hard. There are papers on how to efficiently solve this problem with SAT solver. For example, Fuhs and Schneider-Kamp had this recent paper on Synthesizing Shortest Linear Straight-Line Programs over GF(2) using SAT.

There is a proof that this problem is MAXSNP-hard by Boyar, Matthews and Peralta, see here.

• The paper you linked indeed states that the problem is known to be MaxSNP-hard, but it does not give any reference. Do you have one? – Tsuyoshi Ito Dec 7 '14 at 22:44
• Good call, updated with a reference. – Chao Xu Dec 7 '14 at 22:57
• Too bad Fuhs and Schneider-Kamp haven't published the software/method they used to generate the input to the SAT programs. Going from a linear form to the propositional logic isn't trivial, for me at least. I think I will use the heuristic in the paper by Boyar, Matthews and Peralta for now. – Thom Wiggers Dec 24 '14 at 15:32

It seems the following algorithm gives you the optimal procedure:

Your memory is a set of current targets $t_1,\dots t_k$ together with a set of partial products $p_1,\dots, p_n$ initally empty. Additionally, each partial product is marked by a subset of $\{1,k\}$, which is the set of current targets which strictly contain this product.

1. For each letter, count in how many of the targets it appears. Let $a$ be the letter appearing in the maximal number of targets.
2. Add $a$ to all partial products that point at one of these targets, producing new partial products. If some target containing $a$ was not marked by any partial product, create a new partial product with $a$.
3. Update targets containing $a$ by removing one occurrence of it.
4. Update the marking of the partial products.

Loop these steps until all your targets are empty.

You should end up with the minimal set of partial products you need to compute.

Notice that this algorithm produces an optimal output, but may not be optimal in complexity.

• This seems promising. A bad complexity is ok, the result is only used to help me write faster assembly code. – Thom Wiggers Dec 3 '14 at 15:47
• Yes I got the impression this was the spirit of your question. – Denis Dec 3 '14 at 15:51
• I'm having a bit of trouble with the generation of (new) partial products and the adding of a to partial products. If I generate all possible partial products, how can I end up with the minimal set? How are possibilities eliminated? – Thom Wiggers Dec 3 '14 at 17:08
• You don't general them all, only those who are reached by this order. Run the algorithm on your example, you will see that the only partial product of length $2$ generated is $bc$. – Denis Dec 4 '14 at 12:38
• More precisely at the beginning your set of partial products is empty. Then every time you process a letter, if some target $i$ where it appears was not marked by any partial product, then you add the single letter $a$ as a new partial product. (I edit the answer) – Denis Dec 4 '14 at 13:07