Given an edge-colored graph Gc , a set of p pairs of vertices (aᵢ,bᵢ) together with p numbers k₁,k₂, … kₚ associated with the pairs, can we find a set of alternating paths linking the pairs (a₁,b₁) , (a₂,b₂), … , in their respective numbers k₁,k₂,… kₚ ? Such is the question addressed in this paper. The problem being highly intractable, we consider a restricted version of it to edge-colored complete graphs. Even so restricted, the problem remains intractable if the paths/trails must be edge-disjoint, but it ceases to be so if the paths/trails are to be vertex-disjoint, as is proved in this paper. An approximation algorithm is presented in the end, with a performance ratio asymptotically close to 3/4 for a restricted version of the problem.
No takes yet. Share an insight, caveat, or question.
Rachid Saad (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: