Finding the paths through a graph that reuse as many of the nodes as possible
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.