How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices may be different for each trail, although they need not be different. (I'd like the output to be the paths themselves, and of course trivially the number of trails too).
This type of question has a lot of variations when some additional assumptions are added. Most of them involve adding a source and terminal vertex. However, I haven't seen any proper treatment of the case for an arbitrary $s,t$, even under a specific topology (e.g. $k$-connected, co-graph or bounds on the degree of a vertex, etc).
- If set of source and terminal are given, $(s_i, t_i)$ it reduces to the canonical EDPs problem.
- If source and terminal are given, and paths need not be disjoint: How to find all paths of length up to k between two nodes in a directed graph?
- If graph $G$ is undirected: https://stackoverflow.com/questions/11622864/
Assume that the problem is well-posed. If someone could help me get started towards a way to find such edge-disjoint paths of equal length, it would be helpful. Even if we need to make some assumptions on the topology of the graph, e.g. bounded degree, connected, etc., that's fine for now and I can find a way to generalize from those if needed.