The Universal Property of the Algebraic Path Problem

Abstract: The algebraic path problem generalizes the shortest path problem, which studies graphs weighted in the positive real numbers, and asks for the path between a given pair of vertices with the minimum total weight. This path may be computed using an expression built up from the "min" and "+" of positive real numbers. The algebraic path problem generalizes this from graphs weighted in the positive reals to graphs weighted in an arbitrary commutative semiring $R$. With appropriate choices of $R$, many well known problems in optimization, computer science, probability, and computing become instances of the algebraic path problem.

In this talk we will show how solutions to the algebraic path problem are computed with a left adjoint, and this opens the door to reasoning about the algebraic path problem using the techniques of modern category theory. When $R$ is "nice", a graph weighted in $R$ may be regarded as an $R$-enriched graph, and the solution to its algebraic path problem is then given by the free $R$-enriched category on it. The algebraic path problem suffers from combinatorial explosion so that solutions can take a very long time to compute when the size of the graph is large. Therefore, to compute the algebraic path problem efficiently on large graphs, it helps to break it down into smaller sub-problems. The universal property of the algebraic path problem gives insight into the way that solutions to these sub-problems may be glued together to form a solution to the whole, which may be regarded as a "practical" application of abstract category theory.

category theory

Audience: researchers in the topic

Em-Cats