Abstract
We study the κ -Colored Constrained Spanning Tree (κ -CCST) and the κ -Colored Out-Constrained Spanning Tree (κ -COCST) problems on edge-colored directed graphs. These problems target to find a spanning tree such that for each vertex, the number of incident edges (or, out-going edges) that share any specific color is bounded by some constant κ. We show that both problems are in general NP-hard, but for special cases, polynomial-time algorithms exist. In particular, when the input graph is a directed acyclic graph (DAG), κ -COCST can be solved via a maximum-flow-based algorithm. Furthermore, if the edges in the DAG are limited to use 2 colors and κ is restricted to 1, κ -CCST can be solved via dynamic programming.