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 &amp;=&amp; x_0 \oplus x_4 \oplus x_7 \oplus x_{10} \oplus x_{12} \oplus x_{14} \oplus x_{15} \\
x_{1} &amp;=&amp; x_1 \oplus x_4 \oplus x_{11} \oplus x_{12} \oplus x_{15} \\
x_{2} &amp;=&amp; x_2 \oplus x_5 \oplus x_8 \oplus x_9 \oplus x_{12} \\
x_{3} &amp;=&amp; x_3 \oplus x_6 \oplus x_9 \oplus x_{10} \oplus x_{13} \\
x_{4} &amp;=&amp; x_0 \oplus x_3 \oplus x_4 \oplus x_8 \oplus x_{10} \oplus x_{11} \oplus x_{14} \\
x_{5} &amp;=&amp; x_0 \oplus x_5 \oplus x_8 \oplus x_{11} \oplus x_{15} \\
x_{6} &amp;=&amp; x_1 \oplus x_6 \oplus x_8 \oplus x_{12} \oplus x_{13} \\
x_{7} &amp;=&amp; x_2 \oplus x_7 \oplus x_9 \oplus x_{13} \oplus x_{14} \\
x_{8} &amp;=&amp; x_2 \oplus x_4 \oplus x_6 \oplus x_7 \oplus x_8 \oplus x_{12} \oplus x_{15} \\
x_{9} &amp;=&amp; x_3 \oplus x_4 \oplus x_7 \oplus x_9 \oplus x_{12} \\
x_{10} &amp;=&amp; x_0 \oplus x_1 \oplus x_4 \oplus x_{10} \oplus x_{13} \\
x_{11} &amp;=&amp; x_1 \oplus x_2 \oplus x_5 \oplus x_{11} \oplus x_{14} \\
x_{12} &amp;=&amp; x_0 \oplus x_2 \oplus x_3 \oplus x_6 \oplus x_8 \oplus x_{11} \oplus x_{12} \\
x_{13} &amp;=&amp; x_0 \oplus x_3 \oplus x_7 \oplus x_8 \oplus x_{13} \\
x_{14} &amp;=&amp; x_0 \oplus x_4 \oplus x_5 \oplus x_9 \oplus x_{14} \\
x_{15} &amp;=&amp; 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.
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.