Counting Vertex-Disjoint Shortest Paths in Graphs

Abstract

Finding a shortest path in a graph is at the core of many combinatorial search problems. A closely related problem refers to counting the number of shortest paths between two nodes. Such problems are solvable in polynomial time in the size of the graph. However, more realistic problem formulations could additionally specify constraints to satisfy. We study the problem of counting the shortest paths that are vertex disjoint and can satisfy additional constraints. Specifically, we look at the problems of counting vertex-disjoint shortest paths in edge-colored graphs, counting vertex-disjoint shortest paths with directional constraints, and counting vertex-disjoint shortest paths between multiple source-target pairs. We give a detailed theoretical analysis, and show formally that all of these three counting problems are NP-complete in general.