Complexity of finding color-avoiding connected components
math.CO
Submitted: 2026-10-29
Updated: 2026-10-29
License: http://creativecommons.org/publicdomain/zero/1.0/
The gist: 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…
Abstract
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.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality