Complexity of finding color-avoiding connected components

@misc{fekete2026complexity,
  title = {{Complexity of finding color-avoiding connected components}},
  author = {Panna Tímea Fekete and Roland Molontay and Kitti Varga},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.39982},
  eprint = {2610.39982},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39982},
  note = {CC0},
}

TY  - UNPB
TI  - Complexity of finding color-avoiding connected components
AU  - Panna Tímea Fekete
AU  - Roland Molontay
AU  - Kitti Varga
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.39982
UR  - https://arxiv.org/abs/2610.39982
AB  - Two vertices of a (not necessarily properly) arc-colored digraph are called arc-ℓ-color-avoiding strongly k-arc-connected if, after the removal of the arcs of any at most ℓ colors, they remain strongly k-arc-connected. The arc-ℓ-color-avoiding strongly k-arc-connected components are maximal sets of vertices such that any two of those vertices belonging to the set are arc-ℓ-color-avoiding strongly k-arc-connected in the graph. We investigate the problems of finding the arc-ℓ-color-avoiding strongly k-arc-connected components and the maximal arc-ℓ-color-avoiding strongly k-arc-connected subgraphs of an arc-colored digraph. We also consider possible generalizations to k-vertex-connectivity and to vertex-colored digraphs. We show that despite the seemingly minor differences in definitions, the complexity of these problems varies significantly: some can be solved in polynomial time, while others are NP-hard. It also turns out that in some cases the problem is NP-hard when multiple colors can be assigned to each vertex, but the problem becomes polynomial-time solvable when each vertex is single-colored.
ER  -