# Optimal graph representative of a set of paths

We have a set of paths $$P=\{p_1,p_2, .. p_n\}$$ from a directed weighted graph $$G$$. The paths $$p_i$$ may have different lengths, start and end points. The problem is to construct the best representative graph $$G^*$$ of $$P$$. By best, we mean that $$G^*$$ maximizes the sum of scores of $$p_i, i\in[|1,n|]$$ with upper bound constraints on the number of vertices and edges of $$G^*$$. One way to define a score of $$p_i$$ in $$G^*$$ is $$score(p_i,G^*) = \big(\frac{x}{|p_i|}-\alpha y-\beta\frac{z}{|p_i|}\big)^+,$$ with $$x$$ is the number of shared vertices between $$G^*$$ and $$p_i$$, $$y$$ is the number of vertices of $$p_i$$ not in $$G^*$$, $$z$$ is the number of edges of $$p_i$$ not in $$G^*$$, $$|p_i$$| is the number of vertices of $$p_i$$, and $$\alpha$$, $$\beta$$ are weighting factors. This score is equal to one if $$p_i$$ is included in $$G^*$$. Do you know if this problem is known in graph theory and/or its applications?

• Are the paths in $P$ between the same endpoints? Can you define the score more precisely? Oct 13 at 22:06
• Can you formulate your problem more precisely? Oct 14 at 8:08
• Paths of $P$ do not have necessary the same endpoints. A formula for the score is given, but I guess, other ways to define the score are possible also. Oct 14 at 9:09