Shortest path that traverses all regions

Question

I have a computational problem where, given a set of observations, I want to determine the minimum set of phenomena (explanations) that account for all observations. Phenomena can cause one another, that is all phenomena can be represented as an unweighed directed graph with causal relationships as edges.

I am given the following:

• An exhaustive list of all possible observations O_1 ... O_N
• An exhaustive list of all possible phenomena (causes/explanations) C_1, ... C_N
• For each observation O_N, a list of the phenomena that can cause it
• For each phenomenon C_N, a list of the other phenomena that can cause it

The problem is represented below in graph form (sorry for the quality of the picture). Each node is a phenomenon, and each edge represents a causal relationship between phenomena. Edges are unweighted. Each region outlined by a bigger "bubble" represents a possible observation, with all phenomena lying within the bubble being the subset of phenomena that are known to cause that observation.

The problem, restated, is to find the shortest path that crosses all regions in the graph. (For simplicity, assume there is a unique path that explains all observations - no branching, no need for multiple paths).

My questions are as follows:

1. Is this a known computational problem, or a variant of a known computational problem?
2. Are there known algorithms for solving this specific problem (beyond just "use existing shortest path" algorithms)?
3. If not, how should I approach this problem? Specifically, how do I decompose the problem into simpler (i.e. simple shortest path) problems?

If it helps regarding computational feasibility, the number of observations is on the order of 10,000 and the number of possible phenomena on the order of 100,000.

Answer 1

This is a set-cover probem combined with Hamiltonian path problem. Let me explain: Since each phenomena is related to a group of observations, you can look at each phenomena as a set in the set-cover problem. We need to check each group of phenomena which together cover all observations, to see if a Hamiltonian path exists for this group, that is - there is a simple path which includes all the phenomena in the group.

One approach is to find the smallest set cover (=group of phenomena) and check if a Hamiltonian Path exists for this group. Then continue to the next (equal or larger) set cover, and do the same check, and so on until we find a set cover which has a hamiltonian path. This will be the smallest group of phenomena, which cover all observations, and that has a simple path going over all phenomena in the group.

Answer 2

An phenomenon that causes neither observation nor another phenomenon won't appear in any minimal answer, so we can assume there aren't any of them. In other words, pass one of any algorithm is get rid of these "useless" phenomena.

With that assumption, we treat observations just like any other vertex. Since observations cause nothing, all observations are leaf vertices. Since all phenomenon cause something (see step 1), no phenomenon is a leaf vertex. Thus we can simplify the problem statement and simply talk about the leaf vertices of a directed graph.

In general, there's going to be no single path that hits at least one branch vertex of each leaf. Instead, a better way of posing the problem is seek some kind of minimal graph that spans all the leaf vertices, but need not span the phenomena.

This a variation on the Steiner Tree Problem on graphs. It's NP-complete. Most variations are also NP-complete. The best hope you've got is something good enough, that is, an approximation algorithm.

You don't state this assumption explicitly, but it seems like you're assuming that there's no cyclic causation of phenomena (such as A causes B causes C causes A again). In this case your problem is on a directed acyclic graph, but that doesn't help. The directed problem is as hard as the undirected one.