Routing Problems in Edge‐Colored Directed Acyclic Graphs

ABSTRACT

This paper analyzes multiple routing problems in edge‐colored directed acyclic graphs (CDAGs). Specifically, we investigate the ‐ variant of the Shortest Path Problem (SPP), the Longest Path Problem (LPP), and the Exact Path Problem (EPP) in CDAGs. Assume that we are given a colored DAG , where denotes the vertex set, denotes the edge set, and is the color function that assigns one color to each edge. In each problem, we are given a source vertex and a sink vertex . The objective is to discover a path from to satisfying certain requirements on the number of edges assigned certain colors. These problems are novel and require new insights. We show that these problems are NP‐complete if and only if the number of colors is unlimited (i.e., a part of the input). We also establish lower bounds for these problems using the Exponential Time Hypothesis. On the algorithmic front, we design polynomial‐time algorithms for these problems in CDAGs when the number of colors is fixed. The runtime complexity of our algorithms establishes that these problems are in XP with respect to the number of colors. We also demonstrate that these problems are in para‐NP , indicating that these problems are in XP para ‐. Finally, we prove that LPP, SPP, and EPP have polynomial‐space exact algorithms that run in time (An extended abstract of this work was presented at COCOA 2025).