I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few nodes as possible in order to store them efficiently. All paths start from a root and end at a leaf node.
Below are a few examples:
Suppose the subset of paths chosen all start from the root node R. Then, I can describe all these paths with "all paths that start from R". This uniquely determines the paths that were selected. So I just need to store R and a flag that specifies that this node is a root.
A similar scenario, but for the case where all the paths end at a specific leaf node L. They can be described with "all paths that end at L". So I just need to store L and a flag that specifies that this node is a leaf.
A similar scenario, but for the case where all the paths pass through a specific intermediate node I. They can be described with "all paths that pass through I". So I just need to store I and a flag that specifies that this node is an intermediate node.
The problem could get more complicated if the paths need to be described with more than just a root/leaf/intermediate node. For example, I may need to specify many roots, leaves, and intermediate nodes. However, I want the description to contain as few nodes as possible.
Is there any known algorithm/heuristic that I can apply to my problem?
Thanks a lot.