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?

New contributor
Omar R. is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\begingroup$ Are the paths in $P$ between the same endpoints? Can you define the score more precisely? $\endgroup$
    – Steven
    Oct 13 at 22:06
  • $\begingroup$ Can you formulate your problem more precisely? $\endgroup$ Oct 14 at 8:08
  • $\begingroup$ 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. $\endgroup$
    – Omar R.
    Oct 14 at 9:09

Your Answer

Omar R. is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.