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?

  • $\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

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.