"Pathfinding" in a Category Suppose you are given the &quot;action&quot; of a morphism, some specification of what it does to elements; in $\textbf{Set}$ or related categories it would be the graph of a function. Is it possible to determine, in theory or practice, (whether there exists) a set of arrows whose composition matches the given action? If there are many such sets, is it possible to determine the one(s) requiring minimal compositions?
My intuition, stemming from the digraph axiomatization of a category, suggests that this is a simple example of pathfinding. However, most categories not only have infinite or large object sets, but infinite or large hom-sets. It's not clear how the standard algorithms would work on an infinite graph, let alone a graph with infinitely many edges between each vertex. I couldn't find any information on generalizations of pathfinding to such cases. However, it seems like this would be a common enough question in the subject to have been asked before. Is there something I'm missing?
There isn't a universal answer to this. Many problems (NP problems) could be easily written in such a formulation. For example : Hamiltonian cycle.

Your category is the set of nodes you've visited +
the node you're actually in. Your action is to move to a neighboring
vertex and mark it as visited. You have an Hamiltonian cycle iff the
shortest path from $\emptyset \times {x}$ to $V \times {x}$ is of
length exactly $|V|$)

So each answer will have to be designed specifically to the problem at hand, with the help of the geometry of the problem.
But this isn't a lost cause ! The edit distances (Levenshtein distance, tree edit distance, time-warp edit distance, etc) are generally defined as pathfinding distances on huge sets, but computed with dynamic algorithm that run in polynomial time of the input size.
If you can't find an &quot;analytic&quot; solution, maybe a pathfinding algorithm like A* can help you  find a solution faster. The idea is to have a lower-bound heuristic (&quot;the path from X to Y is at least n&quot;), and use this kind of bound to orient your search. This could help you explore the neighbors in an interesting order and not explore a huge part of the category.
There isn't a universal answer to this. Many problems (NP problems) could be easily written in such a formulation. For example : Hamiltonian cycle.

Your category is the set of nodes you've visited +
the node you're actually in. Your action is to move to a neighboring
vertex and mark it as visited. You have an Hamiltonian cycle iff the
shortest path from $\emptyset \times {x}$ to $V \times {x}$ is of
length exactly $|V|$)

So each answer will have to be designed specifically to the problem at hand, with the help of the geometry of the problem.
But this isn't a lost cause ! The edit distances (Levenshtein distance, tree edit distance, time-warp edit distance, etc) are generally defined as pathfinding distances on huge sets, but computed with dynamic algorithm that run in polynomial time of the input size.
If you can't find an &quot;analytic&quot; solution, maybe a pathfinding algorithm like A* can help you  find a solution faster. The idea is to have a lower-bound heuristic (&quot;the path from X to Y is at least n&quot;), and use this kind of bound to orient your search. This could help you explore the neighbors in an interesting order and not explore a huge part of the category.