0
$\begingroup$

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).

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.

$\endgroup$
4
  • $\begingroup$ Each of the edge-disjoint paths may have a different $s,t$. But they do not need to have different $s,t$. Added all of these details to the question. Thanks so much for your suggestions to help me clarify! $\endgroup$ Jul 7, 2023 at 17:42
  • 1
    $\begingroup$ So $s_i$ and $t_i$ are not the parts of the input. We are simply finding the maximum number of edge disjoint paths of length $k$ in the graph. Is that right? $\endgroup$ Jul 7, 2023 at 19:03
  • 1
    $\begingroup$ is it exactly $k$ or at most $k$? $\endgroup$ Jul 10, 2023 at 11:30
  • $\begingroup$ The original question was exactly $k$, so ideally we'd find a solution to that. But I'm realizing that's probably NP-Hard. So, at most $k$ would be a good starting point. $\endgroup$ Jul 10, 2023 at 16:09

1 Answer 1

0
$\begingroup$

This is not a complete solution. But the following reduction simplifies it.

The problem can be reduced to finding maximum number of edge disjoint paths of length $k$ between two vertices $s$ and $t$ in a directed graph. I am assuming that the given graph is unweighted. However, a similar reduction also works for weighted graphs.

Reduction: Given an instance graph $G = (V,E)$ for your problem. Add new vertices $s$ and $t$. Add $m$ multi directed edges from $s$ to every vertex in $V$ where $m = |E|$. Similarly, add $m$ multi directed edges from each vertex of $V$ to $t$. Then, for each edge $e = (u,v)$ in the graph, replace it with a new vertex $w_e$, and edges $(u,w_e)$ and $(w_e,v)$. Let this new graph be $G' = (V',E')$.

Claim: For any set of $\ell$ edge-disjoint paths of length $k$ in directed multi-graph $G$ there exists $\ell$ edge-disjoint paths of length $2(k+2)$ in directed graph $G'$ and vive-versa.

The proof easily follows from the construction.


If you want the edge disjoint paths of length at most $k$, then there exists efficient algorithms: see this. The authors state that the problem can be solved in polynomial time using linear programming for unit edge lengths. I believe that a similar solution might also work for paths of length exactly $k$. There is a more recent paper on a similar problem.

$\endgroup$
6
  • $\begingroup$ Right. I'm on it. Ouch I forgot to mention that the graph actually is weighted, but let's work with this and see if I can take it from here. Let me get back to you soon about whether this works. I'll try the proof. $\endgroup$ Jul 8, 2023 at 2:54
  • $\begingroup$ I tried a small example, but I'm not getting this to work out. When you say "Add $m$ multi directed edges from $s$ to every vertex...", it isn't clear to me how you can guarantee there are exactly $m$ of them. Is $|E|$ represent the duplicated arcs according to their multiplicity? Or does it count each unique arc $(u,v)$ only once? $\endgroup$ Jul 10, 2023 at 5:49
  • $\begingroup$ @IsalanOnkar Yes $|E|$ represents the duplicated arcs according to their multiplicity. So, if the input graph contains $5$ edges including duplicate edges, we add $5$ edges from $s$ to each vertex $v \in V$. This ensures that multiple edge disjoint paths can go through $s$ and $v$. $\endgroup$ Jul 10, 2023 at 6:15
  • $\begingroup$ Right, but it seems like you are assuming that the number of vertices in $|V|$ is exactly equal to the number of edges. E.g. if I have two vertices $u,v \in V$, and 5 edges between them, how do I connect the 5 arcs from $s$ to $u$ and $s$ to $v$? $\endgroup$ Jul 10, 2023 at 15:55
  • $\begingroup$ @IsalanOnkar These are multi edges. You can add as many as you want. $\endgroup$ Jul 10, 2023 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.