Finding a Path in Group-Labeled Graphs with Two Labels Forbidden

The parity of the length of paths and cycles is a classical and well-studied topic in graph theory and theoretical computer science. The parity constraints can be extended to the label constraints in a group-labeled graph, which is a directed graph with a group label on each arc. Recently, paths and cycles in group-labeled graphs have been investigated, such as finding non-zero disjoint paths and cycles.

In this paper, we present a solution to finding an

$$s$$

s

–

$$t$$

t

path in a group-labeled graph with two labels forbidden. This also leads to an elementary solution to finding a zero path in a

$${\mathbb Z}_3$$

Z

3

-labeled graph, which is the first nontrivial case of finding a zero path. This situation in fact generalizes the 2-disjoint paths problem in undirected graphs, which also motivates us to consider that setting. More precisely, we provide a polynomial-time algorithm for testing whether there are at most two possible labels of

$$s$$

s

–

$$t$$

t

paths in a group-labeled graph or not, and finding

$$s$$

s

–

$$t$$

t

paths attaining at least three distinct labels if exist. We also give a necessary and sufficient condition for a group-labeled graph to have exactly two possible labels of

$$s$$

s

–

$$t$$

t

paths, and our algorithm is based on this characterization.