Some Polynomial Subclasses of the Eulerian Walk Problem for a Multiple Graph

In this paper, we study undirected multiple graphs of any natural multiplicity $$k > 1$$ . There are edges of three types: ordinary edges, multiple edges, and multi-edges. Each edge of the last two types is a union of $$k$$ linked edges, which connect 2 or $$(k + 1)$$ vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of $$k$$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. We study the problem of finding the Eulerian walk (the cycle or the trail) in a multiple graph, which generalizes the classical problem for an ordinary graph. The multiple Eulerian walk problem is NP-hard. We prove the polynomiality of two subclasses of the multiple Eulerian walk problem and elaborate the polynomial algorithms. In the first subclass, we set a constraint on the ordinary edges reachability sets, which are the subsets of vertices joined by ordinary edges only. In the second subclass, we set a constraint on the quasi-vertices degrees in a graph with quasi-vertices. The structure of this ordinary graph reflects the structure of the multiple graph, and each quasi-vertex is determined by $$k$$ indices of the ordinary edges reachability sets, which are incident to some multi-edge.