Metraipolis › archive › dc_d64e78b1b588

Complexity of finding color-avoiding connected components — arXiv:2610.39982

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.39982
License (as archived)
CC0-1.0
Archived
2026-11-01T02:38:02.481Z
SHA-256 of the archived text
d96088e351b9e38b34d4f36597120edbe41d4a4398a7b65cdd969c7c6563e53b
Stable URL of this page
https://metraipolis.com/documento/dc_d64e78b1b588

How to cite

Complexity of finding color-avoiding connected components — arXiv:2610.39982 — arXiv (en), https://arxiv.org/abs/2610.39982 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d64e78b1b588 (Metraipolis archive dc_d64e78b1b588, sha256 d96088e351b9e38b34d4f36597120edbe41d4a4398a7b65cdd969c7c6563e53b)
BibTeX
@misc{dcd64e78b1b588,
  title = {Complexity of finding color-avoiding connected components — arXiv:2610.39982},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.39982},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d64e78b1b588; sha256 d96088e351b9e38b34d4f36597120edbe41d4a4398a7b65cdd969c7c6563e53b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39982. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Two vertices of a (not necessarily properly) arc-colored digraph are called arc-$\ell$-color-avoiding strongly $k$-arc-connected if, after the removal of the arcs of any at most $\ell$ colors, they remain strongly $k$-arc-connected. The arc-$\ell$-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-$\ell$-color-avoiding strongly $k$-arc-connected in the graph. We investigate the problems of finding the arc-$\ell$-color-avoiding strongly $k$-arc-connected components and the maximal arc-$\ell$-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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.39982 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:28.286Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).