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      dIs 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.
Finding the paths through a graph that reuse as many of the nodes as possible
graph algorithms;optimization
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-LinePrograms over GF(2) using SAT.There is a proof that this problem is MAXSNP-hard by Boyar, Matthews and Peralta, see here.