# How to describe a set of paths in a graph with as few nodes as possible?

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:

1. 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.

2. 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.

3. 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.

• Does the "description" need to simply include all chosen paths, or does it need to only include the chosen paths? i.e. in scenario 2, if you chose 3 paths all ending in L, but there was also an un-chosen path ending in L would it still be ok to say "all paths that end in L"? Jul 5, 2016 at 19:24
• There should be a one-to-one mapping between the description and the chosen paths. As a result, the description should only include the chosen paths.
– Matt
Jul 5, 2016 at 22:22