Generalized Minimum Eccentricity Shortest Path Problem in Tree-Structured Graphs

Student: Rachel Walker

Mentor: Arne Leitert

Abstract

The primary objective of our research is to explore a problem in theoretical computer science related to finding particular paths within networks. Specifically, we are interested in finding a set of paths within very large networks such that the distance between any point within the network and one of these paths is as small as possible. This is a generalization of a previously researched problem called the Minimum Eccentricity Shortest Path (MESP) Problem. In this presentation, we give a formal introduction to the generalized version of this problem and its hardness. Additionally, we give an overview of how different classes of networks can have more efficient solutions when we take advantage of particular properties. Using this, we give an efficient +1-approximation algorithm to the generalized MESP Problem for a particular class of networks and describe how our approach could be generalized to work for a broader class of networks. Finally, we discuss the applications of this problem to biology and other areas of computer science.

Presentation

4 thoughts on “Generalized Minimum Eccentricity Shortest Path Problem in Tree-Structured Graphs”

  1. Hi Rachel! Can you please explain a little more about what an optimal solution looks like? It appears that the point is to find the minimum eccentricity, but why not just extend all of the paths? Basically, what does the balance look like between minimum eccentricity and shortest path? Thanks and great job!

    1. That’s a great question! In any possible solution set S, we require that every path in S is a shortest path. For both the original problem and the generalized problem, the “shortest path” aspect gives it applications to problems such as image compression, DNA sequencing, and transportation planning that would not be achieved otherwise. So to answer your question, a possible solution must consist of shortest paths, and the eccentricity of each of these possible solutions is what we are trying to minimize. An optimal solution to our problem would be one of these possible solutions with the smallest eccentricity.

      If we did want let go of the “shortest path” constraint completely, given p = 1, we would have the Hamiltonian Path problem. It could also be interesting to fix the eccentricity desired and the number of paths allowed, then approximate the length of the paths within the solution. This would be in line with what you mentioned, and it would add another parameter to the problem. However, I think this would make it much more difficult to find an approximate solution.

      I hope that answers your question! Thank you!

  2. Allyson Rogan-Klyve

    Great work with your project, and nice job working to make a rather technical topic more accessible to a general audience.

Leave a Reply

Your email address will not be published. Required fields are marked *