Across the "arrays", the problem size is around 160k. What about the other dimension? How many different "path elements"?

In case the dimension of path elements is large, then the (bit)vectors to represent your sets are going to be very sparse (with up to 12 elements chosen). See Comparing two arrays for a treatment of a similar problem.