Two vertices of a (not necessarily properly) vertex-colored digraph are called vertex-ℓ-
color-avoiding strongly k-arc-connected if, after the removal of the vertices of any
at most
ℓ colors, either at least one of the two vertices is removed, or they remain strongly
k-arc-
connected. The vertex-ℓ-color-avoiding strongly k-arc-connected components are maximal
sets of vertices such that any two vertex belonging to the set is vertex-ℓ-color-avoiding
strongly k-arc-connected in the graph.
We show that finding these components is NP-hard in general, but this problem be-
comes solvable in polynomial time when each vertex is single-colored. We also investigate
the problem of finding the maximal vertex-ℓ-color-avoiding strongly k-arc-connected
sub-graphs. We prove that this problem is likewise NP-hard in general but becomes
solvable in polynomial time when each vertex is single-colored. In addition, we explore
possible generalizations to k-vertex-connectivity and to arc-colored digraphs.
