Laurent Gourvès
email: laurent.gourves@lamsade.dauphine.fr

Adria Lyra
email: adrialyra@ufrrj.br

Carlos A Martinhon

Jérôme Monnot
email: monnot@lamsade.dauphine.fr

On paths, trails and closed trails in edge-colored graphs

Keywords: Edge-colored graphs, properly edge-colored closed trails and cycles, properly edge-colored paths and trails, monochromatic paths

In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G c , we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in G c , we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp., trails) in G c with endpoints in S. Further, if G c contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles.

, the determination of two or more vertex disjoint PEC s-t paths can be done in polynomial time. Finally, if G c is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.

Introduction

In the last few years a great number of applications have been modelled as problems in edge-colored graphs. To solve them, we can explore some interesting connections between edge-colored graphs and the theory of cycles and paths in directed and undirected graphs, matching theory, and other branches of graph theory [START_REF] Bang-Jensen | Alternating cycles and paths in edge-coloured multigraphs: a survey[END_REF][START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. Among the applications are problems in molecular biology [START_REF] Pevzner | DNA physical mapping and alternating eurelian cycles in colored graphs[END_REF][START_REF] Pevzner | Computational Molecular Biology: An Algorithmic Approach[END_REF], transportation and connectivity problems [START_REF] Gamvros | Satellite network design, optimization and management[END_REF][START_REF] Gourvès | The minimum reload s-t path/trail/walk problems[END_REF][START_REF] Wirth | Reload cost problems: minimum diameter spanning tree[END_REF] (where connection costs are associated to pair of colors at adjacent edges), social sciences [START_REF] Chou | Paths through fixed vertices in edgecolored graphs[END_REF] and graph models for conflict resolution [START_REF] Xu | A matrix-based approach to searching colored paths in a weighted colored multidigraph[END_REF][START_REF] Xu | Using matrices to link conflict evolution and resolution in a graph model[END_REF].

Given a graph G = (V, E), a walk ρ from s to t in G (called s-t walk) is a sequence ρ = (v 0 , e 0 , v 1 , e 1 , . . . , e k , v k+1 ) where v 0 = s, v k+1 = t and e i = v i v i+1 ∈ E for i = 0, . . . , k. A trail from s to t in G (called s-t trail) is a walk ρ from s to t where e i = e j for i = j. Analogously, a path from s to t is a trail where v i = v j for 0 ≤ i < j ≤ k and 1 ≤ i < j ≤ k + 1. If ρ is a path (resp., trail) with v 0 = v k+1 then ρ defines a cycle (resp., closed trail). We define V (ρ) = (v 0 , v 1 , . . . , v k+1 ) and E(ρ) = (e 0 , e 1 , . . . , e k ). The length of a path, trail or walk is the number of its edges. We say that a path (resp., cycle) ρ defines a Hamiltonian path (resp., Hamiltonian cycle) if all vertices of V are visited exactly once.

Let I c = {1, 2, . . . , c} be a set of given colors, with c ≥ 2. In this work, G c denotes a simple graph whose edges are colored by colors of I c and with no parallel edges linking the same pair of vertices. The vertex and edge sets of G c are denoted by V (G c ) and E(G c ), respectively, where | V (G c ) |= n and | E(G c ) |= m. For a given color i, E i (G c ) denotes the set of edges of G c colored by i. If H c is a subgraph of G c then N i H c (x) denotes the set of Laurent Gourvès, Adria Lyra, Carlos A. Martinhon, Jérôme Monnot vertices of H c , linked to x with edges colored by i. The degree of x in G c is d G c (x) = i∈Ic |N i G c (x)| or just d(x) when no confusion arises. An edge between two vertices x and y is denoted by xy, its color by c(xy) and its weight by w(xy), if any. Also, given an induced subgraph Q of a graph G, a contraction of Q in G consists of replacing Q by a new vertex z Q , so that each vertex x in G -Q is connected to z Q by an edge, if and only if, there exists an edge xy of G for some vertex y of Q.

From now on, we denote properly edge-colored by just PEC, for short. A subgraph of G c containing at least two edges is said to be a PEC subgraph if any two adjacent edges differ in color. A PEC path (resp., PEC trail) is a path (resp., trail) such that any two successive edges have different colors. Given two vertices s, t ∈ V (G c ), we call PEC s-t path (resp., PEC s-t trail) a path (resp., trail) that begins at s and finishes at t. The vertices s and t will be denoted endpoints of the path or trail. In addition, observe that the edges in a PEC trail need not to form a PEC subgraph since we can have adjacent but not successive edges with the same color.

A PEC path or trail in G c is said to be closed if its endpoints coincide and its first and last edges differ in color. They are also refereed, respectively, as PEC cycle and PEC closed trail. We say that a cycle (resp., closed trail) ϑ x with vertices V (ϑ x ) = (x, v 1 , . . . , v k , x) with x = v i for i = 1, . . . , k is an almost PEC cycle (resp., closed trail) through x in G c if c(xv 1 ) = c(xv k ) and both paths (resp., trails) with at least two edges from x to v 1 and from x to v k are properly edge-colored. Note that, if c(xv 1 ) = c(xv k ) then we have a PEC cycle (resp., closed trail) through x. Further, to simplify our notation, if G c contains no PEC and almost PEC cycles (resp., closed trails) through vertex x, we say that G c contains no (almost) PEC cycles (resp., closed trails) through x in G c . A monochromatic path in G c contains all its edges colored with the same color.

We also deal with the concept of k-(PEC path)-(PEC cycle) subgraph F k of G c (see [START_REF] Bang-Jensen | Alternating cycles and paths in edge-coloured multigraphs: a survey[END_REF][START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]). The subgraph F k denotes an union of k PEC paths and an arbitrarily number of PEC cycles in G c , all vertex disjoint. If k = 0, the subset F 0 will be called PEC cycle subgraph. A k-(PEC path)-(PEC cycle) subgraph F k of G c is maximum if F k has maximum number of vertices among all k-(PEC path)-(PEC cycle) subgraphs F k of G c . Here, we extend this concept and introduce the definition of k-(PEC trail)-(PEC closed trail) subgraph. We say that F k defines a k-(PEC trail)-(PEC closed trail) subgraph of G c if it is composed by an union of k PEC trails with non-coincident endpoints (i.e., if some PEC trail of F k begins or finishes at some vertex x of G c then the remaining PEC trails in F k cannot begin or finish at x, if any) and an arbitrarily number number of maximal PEC closed-trails, all edge disjoint. We say that F k is maximum if F k has maximum number of edges among all k-(PEC trail)-(PEC closed trail) subgraphs of G c . Moreover, we say that a vertex x is visited or covered by a PEC trail or closed trail ρ ∈ F k if x ∈ V (ρ). We denote by α(x) = d F k (x)/2 , the total number of visits at x ∈ V ( F k ). If k = 0, the subset F 0 will be called PEC closed trail subgraph (note that d F0 (x) is always even for every x). Further, notice that F0 with α(x) = 1 for every x of F 0 defines a PEC cycle subgraph.

Finally, we introduce the concept of S-restricted PEC path (resp., trail). Given G c and a subset S ⊆ V (G c ) with |S| ≥ 2, we say that a PEC x-y path (resp., trail) ρ with x = y and x, y ∈ S is S-restricted, if there are no vertices of S belonging to V (ρ) \ {x, y}.

Some related work

Given an arbitrary c-edge-colored graph G c , the determination of one PEC cycle or closed trail through a subset Ψ of vertices is NP-complete even for |Ψ| = 2 and c = Ω(n 2 ) (see [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF][START_REF] Benkouar | Alternating cycles through given vertices in edge-colored graphs[END_REF]). When restricted to c-edge-colored complete graphs K c n with c ≥ 2, Benkouart et. al. [START_REF] Benkouar | Alternating cycles through given vertices in edge-colored graphs[END_REF] present efficient algorithms for finding PEC cycles through a given subset of vertices. In the work of Das and Rao [START_REF] Das | Alternating eulerian trails with prescribed degrees in two edge-colored complete graphs[END_REF], they characterize those 2-edge-colored complete graphs which contain a PEC closed trail visiting each vertex x of K c n (for c = 2) exactly α(x) > 0 times. Generalizing this last problem Bang-Jensen and Gutin [START_REF] Bang-Jensen | Alternating cycles and trails in 2-edge-coloured complete multigraphs[END_REF] solved the problem of determining the length of a longest PEC closed trail visiting each vertex x in 2-edge-colored complete multigraphs at most α(x) > 0 times.

The determination of PEC s-t paths (for Ψ = ∅) over arbitrary c-edge-colored graphs was first solved by Edmonds for two colors (see Lemma 1.1 in [START_REF] Manoussakis | Properly edge-colored paths in edge-colored complete graphs[END_REF]) and then extended by Szeider [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF] to include any number of colors. In Abouelaoualim et al. [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF], the authors also deal with PEC trails and present polynomial time procedures for several versions of the s-t path/trail problem: as the shortest PEC s-t path/trail on general c-edge-colored graphs and the longest PEC path (resp., trail) for graphs with no PEC cycles (resp., closed trails). Recently, Feng et. al. [START_REF] Feng | Characterization of edge-colored complete graphs with properly colored Hamilton paths[END_REF], showed how to determine in polynomial time a Hamiltonian PEC path in K c n (for c ≥ 2), provided that one exists. If G c is an arbitrary 2-edge-colored graph and Ψ a non-empty subset of V (G c ) \ {s, t}, Chou et. al. [START_REF] Chou | Paths through fixed vertices in edgecolored graphs[END_REF] show that the determination of one PEC s-t path passing by all vertices of Ψ is NP-complete even for |Ψ| = 1 (actually, this result can be easily extended to include any number of colors). They also present an efficient algorithm for this problem over 2-edge-colored complete graphs.

A polynomial characterization of c-edge-colored graphs with no PEC cycles was first presented by Yeo [START_REF] Yeo | A note on Alternating Cycles in Edge-coloured Graphs[END_REF] and generalized in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF] for PEC closed trails. In addition, the authors in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF] prove that deciding whether there exist k pairwise vertex (resp., edge) disjoint PEC s-t paths (resp., trails) over arbitrary c-edge-colored graphs G c is NPcomplete even for k = 2 and c = Ω(n 2 ). Moreover, they prove that these problems remain NP-complete for c-edge-colored graphs containing no PEC cycles (resp., closed trails) and c = Ω(n). They conclude their paper with some approximation results for the associated maximization problems together with polynomial results for c-edge-colored graphs with no (almost) PEC cycles or closed trails through s or t.

Some interesting questions regarding monochromatic paths can be found in the literature [START_REF] Gyárfás | Vertex coverings by monochromatic paths and cycles[END_REF][START_REF] Jin | The complexity for partitiong graphs by monochromatic trees, cycles and paths[END_REF][START_REF] Sands | On monochromatic paths in edge-coloured digraphs[END_REF]. For instance, the authors in [START_REF] Jin | The complexity for partitiong graphs by monochromatic trees, cycles and paths[END_REF], show that it is NP-hard to find the minimum number of vertex disjoint monochromatic paths which cover the vertices of the graph G c . They also show that there is no constant factor approximation algorithm for this problem unless P = NP.

In Gourvès et al. [START_REF] Gourvès | The minimum reload s-t path/trail/walk problems[END_REF], the authors consider s-t paths, trails and walks with reload costs between colors. In this case, given a c-edge-colored graph, whenever a vertex is crossed by a walk, there is an associated non-negative reload costs r i,j , with i and j denoting, respectively, successive edge colors in this walk. In the minimum reload s-t path/trail/walk problem the objective is to find an s-t path/trail/walk with minimum reload cost. As discussed in [START_REF] Gourvès | The minimum reload s-t path/trail/walk problems[END_REF], reload s-t paths in edge-colored graphs may be converted into PEC or monochromatic s-t paths by conveniently choosing reload costs between each pair of colors. Other results regarding reload costs can be found in [START_REF] Gamvros | Satellite network design, optimization and management[END_REF][START_REF] Wirth | Reload cost problems: minimum diameter spanning tree[END_REF].

Contributions

In Section 2 in the Fundamental Lemma we deal with the construction of PEC closed trails subgraphs F0 and show how to find in polynomial time, if any, a subset of PEC closed trails visiting all vertices of G c a prescribed number of times defined by an interval associated to each vertex. This result generalizes both works of Benkouar et. al. [START_REF] Benkouar | Alternating cycles through given vertices in edge-colored graphs[END_REF] and Das and Rao [START_REF] Das | Alternating eulerian trails with prescribed degrees in two edge-colored complete graphs[END_REF] only restricted to K c n . As one of its consequences, given a subset S of vertices in G c , we show how maximize in polynomial time the total number of S-restricted PEC paths/trails with non-coincident endpoints in S. In Section 3, we deal with the determination of one s-t trail visiting a non-empty subset Ψ of V (G c ) \ {s, t}. We show how to polynomially solve this problem over graphs containing no PEC closed trails and prove that it becomes NP-complete over graphs containing no PEC cycles (note that PEC closed trails are allowed in this case). Graphs with no PEC cycles or closed trails are interesting since they constitute, in a certain sense, the edge-colored counterpart of non-colored acyclic digraphs. We also show how to determine in polynomial time, if any, an s-t trail visiting a subset E ⊆ E(G c ).

In Section 4 we deal with graphs containing no PEC cycles or closed trails through s or t. We prove that to check whether G c contains two PEC s-t paths/trails with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum vertex degree equal to 3. Further, also based on the Fundamental Lemma, we present an approximation algorithm for computing k vertex/edge disjoint PEC s-t paths/trails so that the maximum path/trail length is no more than k times the PEC path/trail length in an optimal solution. Moreover, if L denotes the length of a shortest PEC s-t path/trail in G c , we consider the problem of computing k vertex/edge disjoint PEC s-t paths/trails of sizes at most L, L + 1 and L + 2, respectively. We also prove that finding two vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since as proved in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF], the problem of finding two PEC s-t paths (resp., trails) in graphs with no PEC cycles (resp., closed trails) through s or t can be solved in polynomial time.

In Section 5, we deal with arbitrary c-edge-colored graphs and prove that finding 2 vertex disjoint monochromatic s-t paths with different colors is NP-complete even for graphs with maximum degree 4. Finally, we conclude in Section 6 by presenting some final remarks and future directions. Some related problems are also proposed at the end of each section.

2 Determination of a PEC closed trail subgraph visiting vertices a prescribed number of times

In this section we extend some of the results and concepts presented in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF] and present our Fundamental Lemma which will be useful in the proof of other important polynomial time procedures in this paper. Initially, recall that for arbitrary c-edge-colored graphs (see Subsection 1.1), the determination of one PEC cycle or closed trail through a subset with two or more vertices is NP-complete. Here, we want to determine a subset of PEC closed trails (or a PEC closed trail subgraph F 0 ) satisfying a non-negative function α over V (G c ) denoting the total number of visits at each vertex in G c . Formally, given two mappings α min and α max from V (G c ) to N such that 0 ≤ α min (x) ≤ α max (x) ≤ d G c (x)/2 for every x ∈ V (G c ), we show how to find in polynomial time, if any, a subset of PEC closed trails whose the total number of visits at x is equal to α(x) for some α(x) ∈ I α (x) = {α min (x), . . . , α max (x)}. Here, we show that this can be accomplished by using the concept of Edmonds-Szeider graph and trail-path graph [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF][START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF] in a modified manner.

For completeness, we recall the definition of Edmonds-Szeider graph as discussed in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF]. Given G c and vertices x ∈ V (G c ), we first construct subgraphs or gadgets G x with:

V (G x ) = i∈Ic {x i , x i | N i G c (x) = ∅} ∪ {x a , x b } E(G x ) = {x a x b } ∪ ( {i∈Ic|x i ∈V (Gx)} ({x i x i } ∪ ( j=a,b {x i x j }))).
See the gadgets G a , G b , G c and G d in the example of Figure 1. The former graph G will be called Edmonds-Szeider graph and is constructed as follows:

V (G) = ( x∈V (G c ) V (G x )) E(G) = i∈I c {x i y i | xy ∈ E i (G c )}} ∪ { x∈V (G c ) E(G x )}.
To illustrate this concept, we can use the Edmonds-Szeider graph G associated with G c to obtain a subset of vertex disjoint PEC cycles (or PEC cycle subgraph F 0 ). To do that, given a perfect matching M in G (which always exists in this case) a possibly empty subset of PEC cycles in G c can be easily obtained after coloring all edges x i y i ∈ (E(G) ∩ M ) with color i and then contracting all subgraphs G x of G into a single vertex x. In addition, we can easily determine if all vertices of G c can be covered or not by a disjoint subset of PEC cycles. To do that, we assign unitary costs w(x i y i ) = 1 for every x i y i ∈ E(G) and cost zero for the remaining edges of E(G). In this way, the non-colored graph G contains a maximum perfect weighted matching M * with total edge cost cost(M * ) = |V (G c )|, if and only if, each vertex of G c is visited exactly once by some PEC cycle in F 0 . See the example of Figure 1. Now, given intervals I(α x ) associated to each x of G c and conveniently adapting the concepts of Edmonds-Szeider graph and trail-path graph as described in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF], we can establish the following result for the determination of a PEC closed trail subgraph satisfying α.

Lemma 1 : (Fundamental Lemma) Consider an arbitrary G c and I α (x) = {α min (x), . . . , α max (x)} for each x ∈ V (G c ). Then, we can find within polynomial time, if any, a subset of PEC closed trails visiting all vertices of G c exactly α(x) times for α(x) ∈ I α (x).

Proof: Initially, given G c and I α (x) for every x ∈ V (G c ), we show how to construct a c-edge-colored graph H c (I α ), denoted here by α-trail-path graph. The construction of H c (I α ) can be done into three steps and extends the definition of a trail-path graph presented in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF]: Denote by

(a) Replace each vertex x of G c by a subset S x = {x 1 , . . . , x αx } of vertices with α x = α max (x).
V = {v xy , u xy |xy ∈ E(G c )}, the subset of all vertices of H c (I α ) associated to edges xy in G c . Now, given H c (I α ) as above, select at random a subset S x = {x i1 , . . . , x i βx } of S x with β x = α min (x) for each x in G c .
In the sequel, construct the (non-colored) Edmonds-Szeider graph associated to H c (I α ) and contract all gadgets associated to vertices of V . Let us denote by H this new non-colored graph. Note that, we have an associated noncolored gadget H z of H for every z ∈ S x (see Figures 2(a) and 2(b)). In the Figure 2(a) we are assuming z ≡ x i for some i ∈ {1, . . . , α x }. Now, for every z ∈ S x and their associated H z , delete edges z a z b (see Figure 2(c)) and relabel all these gadgets by H z . We call modified Edmonds-Szeider graph, denoted by H, the resulting non-colored graph obtained in this way.

color i color j color l (a) (b) (c) z z ′′ a z i z ′′ b z ′ j z j z l z ′ l z ′ i z i z j z ′ j z ′ l z ′′ a z ′′ b z l z ′ i Fig. 2: (a) Vertex z of Sx in H c (Iα); (b) Gadget Hz associated to z ∈ Sx \ S x (c) Gadget H z associated to z ∈ S x .
The idea, provided that a subset of PEC closed trails satisfying function α in G c exists, is to find an associated subset of PEC cycles in H c (I α ) by forcing the visit exactly once of all vertices z ∈ S x , the remaining vertices z ∈ S x \ S x may be visited or not by these cycles. Since |S x | = α min (x) and |S x | = α max (x), after contracting all subgraphs induced by S x , vertex x will be visited by PEC closed trails exactly α(x) times in G c for some α(x) ∈ I α (x). Note that PEC cycles in the α-trail-path graph H c (I α ) will correspond to PEC closed trails satisfying α in G c and vice-versa. This may be accomplished by just finding a perfect matching M * in H, if any.

Thus, in the case M * exists, we can determine the associated PEC closed trail subgraph F0 satisfying α as in the sequel. Initially, for all pairs of edges z k v xy , u xy w k of M * ⊆ E( H) for some z ∈ S x and w ∈ S y in H c (I α ), we pick edge xy of G c , colored k. Further, note that if z ∈ S x , we have two edges of M * not belonging to E(H z ) and incident with exactly two different vertices of H z . Thus, vertex z must be visited exactly once in H c (I α ). Since |S x | = α min (x) and |S x | = α max (x), we have at least α min (x) and at most α max (x) visits at vertex x in G c . Therefore, the set of picked edges in G c defines a PEC closed trail subgraph satisfying α. Reciprocally, given a set of PEC closed trail subgraphs satisfying α, we can easily determine an associated set of PEC cycles in H c (I α ) and a corresponding perfect matching M * in H.

2

Therefore, as one of the consequences of the Fundamental Lemma we have the following result.

Theorem 2 Let G c be an arbitrary c-edge-colored graph and S a subset of V (G c ). Then, the problem of maximizing the number of S-restricted vertex disjoint PEC paths (resp., edge disjoint PEC trails) with non-coincident endpoints in S can be solved in polynomial time.

Proof: Initially, to avoid paths of unitary length between pairs of S (since PEC paths/trails contains at least two edges), we delete all edges xy ∈ E(G c ) with x, y ∈ S. Note that these edges do not eliminate any S-restricted PEC path (or trail) between two vertices of S. Thus, w.l.o.g., consider G c with no edges between pairs of S. Here, we only deal with the problem of maximizing the number of edge disjoint S-restricted PEC trails with endpoints of S, the PEC path case is analogous and is omitted here. To accomplish our goal, given G c and S ⊂ V (G c ) we first construct an edge-colored graph G c v with a new vertex v and c colors with

I c = I c ∪ {(c + 1), . . . , (c + |S|)}. We define V (G c v ) = V (G c ) ∪ {v}, E(G c v ) = E(G c ) ∪ {vx : x ∈ S} and color all |S| edges vx with a new different color of I c \ I c . Basically, for a given set of intervals I α (x) with x ∈ V (G c
v ) (to be defined later), we construct the α-trail-path graph H c v (I α ) and the associated modified Edmonds-Szeider graph Hv as detailed in the Fundamental Lemma. In addition, for all edges p k v xy , u xy q k of Hv , associated to edges xy of E(G c v ) colored k (with p ∈ S x and q ∈ S y in H c v (I α )), we assign weights w(p k v xy ) = w(u xy q k ) = 1/2, and weight zero for the remaining edges of Hv . In this way, note that if edge xy belongs to some PEC closed trail in G c v , we have exactly two edges (each of them with cost 1/2) in the associated perfect matching M in Hv and vice versa. However, if xy does not belong to any PEC closed trail then edge v xy u xy (with cost zero) will be selected to M .

Essentially, the idea is to construct an interval of integer values I α (x) associated to each x of V (G c v ) and determine, if any, a subset of PEC closed trails F0 with the maximum number of visits at v and minimum number of edges. It is important to note that, even if we have no edges xy between pairs of S, we can have non S-restricted PEC trails between two endpoints of S (see the PEC path ρ 3 in the example of Figure 3). Thus, to avoid that, each PEC closed trail of F0 passing by v must correspond to a shortest S-restricted PEC trail in G c with endpoints in S. Therefore, to maximize the number of S-restricted s-t trails among vertices of S we construct the following polynomial time algorithm: (3) Now, as described in the Fundamental Lemma determine, if possible, a subset of ᾱv PEC closed trails visiting v with the minimum number of edges. To accomplish that, solve the minimum perfect matching problem over the weighted (non-colored) Hv .

(4) If such a minimum perfect matching M * exists we are done. Use M * to determine F0 in G c v . Otherwise, set ᾱv ← ᾱv -1.

(5) If ᾱv = 0 (there are no PEC trails among vertices of S) then we stop. Else, set α min (v) = α max (v) = ᾱv , update the weighted Hv , and return to step 3. Fig. 3: Graph G c v with endpoints S = {s1, s2, s3}. The PEC paths ρ1 and ρ2, respectively, with V (ρ1) = (s1, a, s2) and V (ρ2) = (s2, b, s3) are S-restricted while the PEC path ρ3 with V (ρ3) = (s1, a, s2, b, s3) is non S-restricted.

Note in the

Step 3 above that the total number of edges in the PEC closed trail subgraph of G c v is equal to the cost of the minimum perfect matching M * computed over Hv . This will ensure the presence of ᾱv S-restricted shortest PEC trails among vertices of S in G c and avoiding non S-restricted PEC trails. To see that, suppose we have a non S-restricted PEC x-y trail with x, y ∈ S and an associated minimum perfect matching M * in Hv . Since ρ is non S-restricted, there is at least one vertex z of S belonging to V (ρ) \ {x, y}. Now, we can take a shorter S-restricted PEC trail ρ with endpoints x and z, which always exists in this case. Therefore, we can easily construct a perfect matching M (associated to ρ ) with cost(M ) < cost(M * ), leading to a contradiction. 2

We conclude the section with the following related problem:

Problem 1 Consider G c and a subset S of V (G c ).
Can the problem of maximizing the number of (non necessarily S-restricted) vertex disjoint PEC paths (resp., edge disjoint PEC trails) with endpoints in S be solved in polynomial time?

In the Problem 1 above we can include another constraint. For instance, whether or not the endpoints of two different PEC trails can coincide. In both cases, the problem seems harder when compared to the S-restricted case discussed here.

3 Determination of a PEC s-t path/trail visiting a subset Ψ of vertices Let G c be an arbitrary c-edge-colored graph and Ψ a non-empty subset of V (G c ) \ {s, t}. As discussed in Subsection 1.1, the determination of one PEC s-t path visiting all vertices of Ψ is NP-complete even for |Ψ| = 1 (see [START_REF] Chou | Paths through fixed vertices in edgecolored graphs[END_REF]). Here, we show how to find in polynomial time, if any, a PEC s-t trail visiting all vertices of Ψ restricted to c-edge-colored graphs with no PEC closed trails. We also consider a slightly more general class of graphs and prove that the same problem over c-edge-colored graphs with no PEC cycles is NP-complete. Note that PEC closed trails are allowed in this case.

Graphs with no PEC closed trails

We begin with the following auxiliary lemma:

Lemma 3 Consider G c with no PEC closed trails and vertices s, t ∈ V (G c ). Further, assume that there exists a PEC trail ρ between s and t in G c . Then, there are no vertices of ρ which are visited three times or more.

Proof: Suppose a vertex x of ρ with at least 3 visits (i.e., α(x) ≥ 3). Without loss of generality, assume α(x) = 3 and c = 2. In this case we have two possibilities as illustrated in the Figure 4. In the first case (resp., second case), the first and last edges of ρ incident to x 1 have different colors (resp., the same color). In the s-t trail ρ of Figure 4(a), one can easily observes that subsequence ρ of ρ with V (ρ ) = (x 1 , x 4 , x 5 , x 1 , x 2 , x 3 , x 1 ) defines a PEC closed trail in G c , leading to a contradiction. Analogously, in the s-t trail ρ of Figure (4(b)), the subsequence ρ with V (ρ ) = (x 1 , x 6 , x 5 , x 4 , x 1 ) defines a PEC cycle, which is also Therefore, if we find a perfect matching over H v , provided that one exists, we can easily determine a PEC closed trail in G c v visiting all vertices of W and all edges of E . Note that, since G c contains no PEC closed trails, the PEC closed trail subgraph in G c v is composed by exactly one PEC closed trail containing W and E ⊆ E, respectively. Thus, after deleting vertex v, this will correspond to a PEC s-t trail visiting all vertices of E in G c . 2

a PEC closed-trail in G c . 2 (a) (b) color j color i s t x 1 x 2 x 3 x 5 x 4 x 6 x 5 s t x 1 x 3 x 2 x 4

Graphs with no PEC cycles

Here, we consider PEC s-t paths and trails over c-edge-colored graphs with no PEC cycles. Note that PEC closed trails are allowed in this case. We begin with the following result:

Theorem Let G c = (V, E) be a c-edge-colored graph with no PEC cycles, s, t ∈ V and a non-empty subset Ψ of V \ {s, t}. Then, the problem of finding a PEC s-t path visiting all vertices of Ψ can be solved in polynomial time.

The proof of Theorem 6 is analogous to Theorem 4 above and is omitted here. As an immediate consequence we have the following result:

Corollary 7 The problem of finding a Hamiltonian PEC s-t path in G c with no PEC cycles can be solved in polynomial time.

Proof: It suffices to set Ψ = V (G c ) \ {s, t}. 2
Now, we are interested in to find a PEC s-t trail visiting a given vertex w of V (G c ) \ {s, t}. Surprisingly, if no s-t paths visiting w exist, we prove that the determination of one PEC s-t trail passing by w in G c is NP-complete.

Theorem 8 Consider G c with no PEC cycles, c ≥ 2 and s, t, w ∈ V (G c ). Then, the problem of finding a PEC s-t trail visiting w is NP-complete.

Proof: Clearly, our problem belongs to NP. To prove that it is NP-complete, we construct a polynomial time reduction from the Local Path Problem (LPP): given a non-colored digraph D = (V, A) and three vertices p, q, v ∈ V , the objective in the LPP is to find, if any, a directed p-q path through vertex v in D (i.e., each vertex in the path, other than p and q, has exactly one incoming and one outgoing arc). The LPP is known to be NP-complete (see Fortune et. al. [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]). Without loss of generality, let D be a digraph with no incoming arcs at p and with no outgoing arcs from q. In the sequel, we show how to polynomially construct a 2-edge-colored graph G c with no PEC cycles and vertices s, t and w in V (G c ), such that we have a directed p-q path visiting v in D, if and only if, we have an s-t trail visiting w in G c .

For each vertex x ∈ V (D)\{p, q}, create the following gadget G x , with vertices V (G x ) = {x a , x b , x c , x d , x e , x} and edges x e x b , x b x, x c x d all colored j and edges x b x c , x b x d , xx a all colored i, with i = j. In the sequel, change p, q ∈ V , respectively, by s = p a and t = q e in V (G c ). Now, for each arc e = xu of A (with x, u ∈ V (D)) add vertex z xu and edges x a z xu and z xu u e (gadget G e ) with colors j and i, respectively. This construction is obviously polynomial. See the example of Figure 6. Observe that G c contains no PEC cycles since all circuits (or directed cycles) of D, if any, are mapped to PEC closed trails in G c . Actually, any PEC closed trail ρ in G c visiting gadget G x for some x must visit twice vertex x b . Thus, ρ never defines a PEC cycle. Further, notice that in all gadgets G x (associated to x ∈ V (D) \ {p, q}), vertex x can be visited at most once (otherwise, both edges incident at x would be visited twice). Thus, if we have a p-q path in D passing by v, we have a PEC s-t trail passing by w = v in G c and vice-versa. 4 Finding k ≥ 2 PEC s-t paths/trails in graphs with no (almost) PEC closed trails through s or t

In this section we deal with a number of results regarding the determination of two or more PEC s-t paths/trails over c-edge-colored graphs with no (almost) PEC closed trails through s or t. In the general case, it is proved in Abouelaoualim et. al. [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF] that deciding whether an arbitrary c-edge-colored graph G c on n vertices contains two vertex/edge disjoint PEC s-t paths/trails is NP-complete even for graphs with Ω(n 2 ) colors. In addition, they show that if G c contains no (almost) PEC cycles (resp., closed trails) through s or t then the problem of maximizing the number of vertex (resp., edge) disjoint PEC s-t paths (resp., s-t trails) can be solved in polynomial time.

Here, given G c with no (almost) PEC closed trails through s or t, we define the MIN-MAX k-PEC s-t path (resp., trail) problem whose objective is to find k vertex/edge disjoint PEC s-t paths (resp., trails) such that size of the maximum PEC s-t path (resp., trail) is minimized. We show that these problems are NP-hard even for k = 2 and present a k-approximation algorithm based on the Fundamental Lemma. Further, we prove that the problem of maximizing the number of shortest PEC s-t paths/trails, say of size L, can be solved in polynomial time, and it becomes NP-complete for PEC s-t paths/trails of size at most L + 2 for c = 2 and L + 1 for c ≥ 3. These results generalize the work of Tragoudas and Varol [START_REF] Tragoudas | Computing Disjoint Path with Length Constraints[END_REF] only restricted to non-colored graphs. In addition, as a consequence of the NP-hardness of the MIN-MAX 2-PEC s-t path (see Theorem 9 below) we can prove that deciding whether there exists 2-vertex disjoint s-t paths ρ 1 and ρ 2 such that ρ 1 is a PEC s-t path is NP-complete. This result is interesting since the determination of two PEC s-t paths/trails can be done in polynomial time as detailed in [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF].

Therefore, we first consider the following decision version associated to the MIN-MAX 2-PEC s-t path problem. The proof can be easily extended to handle trails instead of paths.

Theorem 9 Let G c be a c-edge-colored graph with no (almost) PEC closed trails through s or t, and a constant L > 0. Then, the problem of finding 2 vertex/edge disjoint PEC s-t paths, each having at most L edges in G c is NP-complete in the strong sense, even for graphs with maximum vertex degree equal to 3.

Proof:

The vertex-disjoint case follows immediately from the edge-disjoint case and its proof is omitted. Initially, we consider I c = {1, 2}. Here, we prove that the (3, B2)-SAT problem can be polynomially reduced to the problem of finding two edge disjoint PEC s-t paths, each having at most L edges. An instance I of (3, B2)-SAT consists of n variables X = {x 1 , . . . , x n } and m clauses C = {c 1 , . . . , c m }. Each clause has exactly three literals. Each variable appears four times, twice negated and twice unnegated. Deciding whether I is satisfiable is NP-complete [START_REF] Berman | Hardness of Short Symmetric Instances of MAX-3SAT[END_REF].

We say that c j is the h-th clause of x i , if and only if, x i appears in c j and x i appears in exactly h -1 other clauses c j with j < j. We say that x i is the -th variable of c j , if and only if, x i and exactly -1 other variables x i with i < i appear in c j .

Let us show how to build a 2-edge-colored graph G c upon I with no (almost) PEC closed trails through s or t and maximum vertex degree equal to 3. For each x i ∈ X (resp., c j ∈ C) we build a gadget G xi (resp., G cj ) as depicted on the left (resp. right) of Figure 7. The gadget of a variable x i has 18 vertices. It consists of a right part (vertices t k ia , t k i b for k = 0, . . . , 3 and edges t 0

u 3 j v 3 j u 2 j v 2 j v 1 j u 1 j q j w j v ′′ u ′′ u ′ v ′ b i (a) (b) f 0 ia f 0 ib f 1 ia f 1 ib f 2 ia f 2 ib f 3 ia f 3 ib t 0 ia t 2 ia t 1 ib t 1 ia t 2 ib t 3 ia t 3 ib a i t 0 ib color 2 color 1
i b t 1 ia , t 1 i b t 2 ia , t 2 i b t 3 ia ) a left part (vertices f k ia , f k i b for k = 0, . . . , 3 and edges f 0 i b f 1 ia , f 1 i b f 2 ia , f 2 i b f 3 ia ), an entrance a i , an exit b i and edges a i t 0 ia , a i f 0 ia , t 3 i b b i , f 3 i b b i .
The left (resp., right) part of this gadget corresponds to the case where x i is set to false (resp., true). Note that each edge of G xi has color 2 (see Figure 7(a)). As discussed later, some other edges with color 1 will be also included in G xi . The gadget of a clause c j (containing 12 vertices) consists of an entrance q j , an exit w j with three edges u 1 j v 1 j , u 2 j v 2 j , and u 3 j v 3 j (all with color 2) corresponding to the first, second and third variables of c j , respectively. We also have 4 edges q j u , q j u , v q j and v q j with color 2 and 6 edges u u 1 j , u u 2 j , u u 3 j , v 1 j v , v 2 j v and v 3 j v all with color 1 (see Figure 7(b)). We add 2 vertices s and t and we link the gadgets as follows (see Figure 8(a)):

• sa 1 , b 1 a 2 , b 2 a 3 , . . . , b n-1 a n and b n t, all of them with color 1 (thin);

• sq 1 , w 1 q 2 , w 2 q 3 , . . . , w m-1 q m , w m t, all of them with color 1 (thin).

w1 q2 qm q1 w2 wm c 1 c 3 c 2 c 4 (a) s a 1 a 2 a n b 1 b 2 b n t (b) a 2 b 2 L v L c L c L c L c 1 1 1 1 1 color 2 color 1
= (x2 ∨ x3 ∨ x5), c2 = (x2 ∨ x3 ∨ x6), c3 = (x1 ∨ x2 ∨ x4) and c4 = (x1 ∨ x2 ∨ x5).
For each pair x i , c j such that x i is the -th variable of c j and c j is the h-th clause of x i we proceed as follows. If x i appears negated in c j then add edges

t h-1 ia u j , t h-1 i b v j and f h-1 ia f h-1 i b , all colored 1 (thin). If x i appears unnegated in c j then add f h-1 ia u j , f h-1 i b v j and t h-1 ia t h-1
i b , all colored 1 (thin). See the example of Figure 8. Each vertex's degree is at most 3 and every edge incident to vertices a i and b i (resp., q j and w j ), inside G xi (resp., G cj ) has color 2 and every edge incident to s or t has color 1. Thus, it is easy to see that G c contains no (almost) PEC closed trails through s and t.

In order to simplify the proof, we deal with the version where the edges have an odd and polynomially bounded length. Then, we can replace each edge e of integer length (e) by a PEC path ρ e made of (e) edges (initial and terminal edges of ρ e have color c(e)). We complete the construction of G c by assigning a length L c = 18n -5 to the edges w 1 q 2 , w 2 q 3 , . . . , w m-1 q m , w m t, and a length L v = 18n(m -1) + 1 to sa 1 . The remaining edges of G c have length 1 (see Figure 8(a)).

The graph contains 18n+12m+2 vertices: 18 per variable gadget, 12 per clause gadget, s and t. Its construction is clearly done within polynomial time. An instance I of our problem consists of an weighted 2-edge-colored G c as above and L = 18nm + 1. We claim that a truth assignment for I, instance of (3, B2)-SAT, corresponds to 2 edge disjoint PEC s-t paths in I , each with total length at most L = 18mn + 1 and vice-versa.

An s-t path with first edge sa 1 and last edge b n t is called a variable path and it is denoted by ρ v . An s-t path with first edge sq 1 and last edge w m t is called a clause path and it is denoted by ρ c .

Suppose that we have 2 paths ρ v and ρ c , associated to I . If ρ v uses an edge of length L c then its total length (of size at least L c + L v + 6) exceeds L. Therefore it never passes through a vertex q j or w j (1 ≤ j ≤ m). Since ρ v is an s-t path, it must visit each variable gadget G xi . Thus, each vertex a i is visited by ρ v . Since ρ v and ρ c are edge-disjoint, ρ c cannot go through a i , i = 1, . . . , n. Then, ρ c must visit each clause gadget G cj to reach t. Further, both ρ v and ρ c have length L.

Thus, if we have 2 PEC s-t paths, each of weight L in G c (resp., variable and clause paths) then we have a truth assignment for I. For instance, if an edge u k j v k j of the gadget G cj is used by a clause path and variable x i (appearing in the k-th position of c j ) is in the negated form (resp., unnegated form) then variable x i must be false (resp., true) and clause c j will be true in the assignment. Therefore, using the clause and the variable s-t paths (of weight L) we can uniquely determine a truth assignment for I.

Conversely, suppose we have a truth assignment, solution to I. To build a variable path ρ v , we take the right (resp., left) part if and only if x i is true (resp., false) (see Figure 8(b)). Then the total length of ρ v is L v + 14n < L. Each clause c j is satisfied so there is an edge u k j v k j of G cj not used by ρ v . The clause path can use it to reach t. In this case ρ c has total length m(L c + 5) + 1 = L.

Finally, we show how to extend our result for graphs with c = Ω(n 2 ) colors. To do that, it suffices to define a complete graph K c n with I c ⊆ I c and edge xy with x ∈ V (K c n ), y ∈ V (G c ) and some color c(xy) ∈ I c . Thus, the resulting c -edge-colored graph

G c α with V (G c α ) = V (G c ) ∪ V (K c n ) and edges E(G c α ) = E(G c ) ∪ E(K c n
) ∪ {xy} will contains, resp., 2n vertices and at most n(n-1) 2 different edge colors, completing our proof.

2

Corollary 10 Let s and t be two vertices in a c-edge-colored graph G c with maximum vertex degree equal to 3 and with no (almost) PEC closed trails through s or t. Then, it is NP-complete to decide whether there exist 2 vertex/edge disjoint s-t paths such that exactly one of them is a PEC s-t path.

Proof: Again, the vertex disjoint case follows immediately from the edge-disjoint case. Analogously, given an instance I of the (3, B2)-SAT problem, we show how to construct a c-edge-colored graph G c with no (almost) PEC closed trails through s or t and maximum vertex degree equal to 3. In this case G c is non-weighted and the variable and clause gadgets are constructed exactly as in the proof of Theorem 9 except for the color of clause gadgets. Now, all edges of c j for j = 1, ..., m are colored blue (color 2). Using the same arguments as above, we can easily see that there will exist two s-t paths in G c with exactly one PEC s-t path, if and only if, instance I is true at some truth assignment. 2

Note that Corollary 10 above can be easily extended to handle trails instead of paths. Now, using the Fundamental Lemma we can establish the following approximation result for the MIN-MAX k-PEC s-t path/trail problem:

Theorem 11 Consider a fixed constant k ≥ 2 and a c-edge-colored graph G c with no (almost) PEC cycles (resp., closed trails) through s or t. Then, the problem of finding k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is minimized has performance ratio equal to k.

Proof: Here, we only deal with the edge disjoint case, the vertex disjoint case is analogous. Therefore, given G c as above, assign weights w(xy) = 1 for every edge xy of E(G c ). In the sequel, add a new vertex v and 2k vertices S = {s 1 , . . . , s k } and T = {t 1 , . . . , t k }, respectively. Further, define Φ = {s, t, v} ∪ S ∪ T . Now, color edges {s 1 s, . . . , s k s} and {t 1 t, . . . , t k t} with a new color c + 1, all edges {vs 1 , . . . , vs k } with a new color c + 2 and all edges {vt 1 , . . . , vt k } with a new color c + 3 (see the Figure 9). Finally, assign weight w(xy) = 0 to all edges xy of E(Φ). Let us denote by G c Φ this new weighted c -edge-colored graph. Note that G c Φ contains n + 2k + 1 vertices and c = c + 3 colors. In the sequel, define intervals α min (x) = α max (x) = k for every x ∈ {s, t, v}, α min (x) = α max (x) = 1 for every x ∈ S ∪ T and α min (x) = 0 and α max (x) = k for every x ∈ V (G c Φ ) \ Φ (note that x can be visited at most k times in the edge disjoint case). Finally, construct a weighted modified Edmonds-Szeider graph HΦ (associated to H c Φ (I α )) as discussed in the Fundamental Lemma, i.e., for all edges p v xy , u xy q of HΦ associated to edges xy with color in E(G c Φ ) (with p ∈ S x and q ∈ S y in H c Φ (I α )) assign weights w(p v xy )=w(u xy q )=w(xy)/2, resp., and assign weight zero for the remaining edges of HΦ . ... ...

s k s 1 s t v color c + 2 color c + 3 color c + 1 color c + 1 Graph G c k pec s-t trails t 1 t k
Fig. 9: Construction of a minimum PEC closed trail subgraph with α(v) = k.

Our algorithm proceed as follows. Initially, find a minimum perfect matching M * with total edge weight equal to cost(M * ) in HΦ , if any. Then, determine the associated PEC closed trail subgraph satisfying α in G c Φ . Since we have no (almost) PEC closed trails through s or t, each of the k PEC closed trails passing by v in G c Φ will be associated to a PEC s-t trail in G c . Let Ξ be the set of k PEC s-t trails in G c obtained in this way. Note that cost(M * ) = ξ∈Ξ length(ξ). Now, denote by z H (ξ k ) the length of the maximum PEC s-t trail ξ k of Ξ. Then, we claim that z H (ξ k ) ≤ k.Opt(G c ), with Opt(G c ) denoting the k-th longest trail of minimum length in G c . Initially, note that z H (ξ k ) ≤ cost(M * ). Since M * is a minimum perfect matching, it follows that cost(M * )/k ≤ Opt(G c ) and z H (ξ k ) ≤ k.Opt(G c ), which proves our result.

2

Theorem 12 Consider G c with no (almost) PEC closed trails through s or t in V (G c ). Then, the problem of maximizing the number of vertex/edge disjoint PEC s-t paths (resp., trails) with shortest path (resp., trail) length can be solved in polynomial time.

Proof: Similarly to Theorem 11, we will only consider the edge-disjoint case. Further, we only deal with trails instead of paths. Therefore, initially construct a shortest PEC s-t trail in G c (see [START_REF] Abouelaoualim | Paths and trails in edge-colored graphs[END_REF] for details) and denote its length by L > 0 (w.l.o.g., we assume the existence of at least one PEC s-t trail in G c of size L). Construct the weighted c -edge-colored graph G c Φ as in the previous theorem and define intervals α min (x) = α max (x) = k with x ∈ {s, t, v} and some integer k > 0 (to be defined later), α min (x) = α max (x) = 1 for every x ∈ S ∪ T , α min (x) = 0 and α max (x) = k for every Since G c contains no (almost) PEC closed trails through s or t, the determination of a minimum perfect matching M * in HΦ (k), if any, will be associated with k PEC closed trails in G c Φ passing by s, t and v, resp., each of them associated to a PEC s-t trail in G c . Further, if cost(M * ) = kL we have exactly k PEC s-t trails with minimum length L in G c . 2

x ∈ V (G c Φ ) \ Φ.
The following results regard PEC s-t paths in c-edge-colored graphs with no (almost) PEC cycles through s or t. They can be easily extended to handle PEC s-t trails in graphs with no (almost) PEC closed trails through s or t (the details are omitted and left to the reader). Initially, consider the following auxiliary result restricted to 2-edge colored graphs:

Lemma 13 Consider G c with c = 2 and with no (almost) PEC cycles through s or t. If a shortest PEC s-t path has size L then G c contains no other vertex disjoint PEC path between s and t of size L + 1.

Proof: Suppose α and β two vertex disjoint PEC s-t paths of size L and L + 1, respectively. Without loss of generality, consider the first and last edges of α colored red, incident respectively to s and t. Further, since β has size L + 1 its first and last edges must have different colors, for instance, a red edge incident to s and a blue edge incident to t. In this case, we would have an almost PEC cycle passing by s and containing vertex t, resulting in a contradiction.

2

Theorem 14 Consider G c with c = 2 and with no (almost) PEC cycles through s or t in V (G c ). If L > 0 denotes the length of a shortest PEC s-t path, the problem of finding k vertex disjoint PEC s-t paths in G c with length at most L + 2 is NP-complete.

Proof: This problem is obviously in NP. The reduction is based on the Theorem 3 of [START_REF] Tragoudas | Computing Disjoint Path with Length Constraints[END_REF] (restricted to non-colored graphs). Here, we deal with a different version of the 3-SAT problem. We prove that the (3,B2)-SAT problem can be reduced to the problem of finding k = m + 2n vertex disjoint PEC s-t paths with length at most L + 2 in G c , where G c has no (almost) PEC cycles through s or t.

Let I be an instance of (3, B2)-SAT with X ={x 1 , x 2 , ..., x n } and C={c 1 , c 2 ..., c m } denoting the variable and clause sets, respectively. We will construct a 2-edge-colored graph G c , as follows:

• For each x i ∈ X , we build a combined gadget G xi (see Figures 10(a • Graph G xi has three components: one α G xi and two

β k G xi , 1 ≤ k ≤ 2.
• Any two β k G xi gadgets share vertex s. Gadgets β k G xi and α G xi share vertices s, u ik and ūik for k = 1, 2.

• In gadget α G xi there will be vertices:

s, t, w i1 , w i2 , W i1 , W i2 , u i1 , ūi1 , u i2 , ūi2 , U i1 , Ūi1 , U i2 , Ūi2 , y i1 , y i2 , z i1 , z i2 , Z i1 and Z i2 (1 ≤ i ≤ n).
• In gadget β k G xi there will be vertices: s, a ik , a ik , b ik , b ik , u ik and ūik (1 • G c will have the following edges:

≤ i ≤ n and 1 ≤ k ≤ 2) b ik b ′ ik a ′ ik a ik ūik u ik s (b) (a) W i2 ūi2 Ūi2 y i2 z i2 Z i2 z i1 t W i1 u i1 U i1 y i1 Z i1 ūi1 u i2 Ūi1 U i2 w i1 w i2 s α G xi β k G xi
sw i1 , sw i2 , W i1 u i1 , W i1 ūi2 , W i2 ūi1 , W i2 u i2 , U i1 y i1 , Ūi1 y i1 , U i2 y i2 , Ūi2 y i2 , z i1 Z i1 , z i2 Z i2 and sa ik , b ik u ik , b ik ūik , b ik a ik for k = 1, 2 (all colored blue) and w i1 W i1 , w i2 W i2 , u i1 U i1 , ūi1 Ūi1 , u i2 U i2 , ūi2 Ūi2 , y i1 z i1 , y i2 z i2 , Z i1 t, Z i2 t and a ik b ik , a ik b ik for k = 1, 2 (all colored red).
• Finally, G c will contain additional vertices c j for j = 1, .., m and edges c j t, 1 ≤ j ≤ m, colored red, as well as U ik c j (resp., Ūik c j ), colored blue, if the k th occurrence of x i (resp. xi ) is in the j th clause. See Figure 11 for a graph G c associated with an instance of the (3, B2)-SAT problem.

(x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) of the (3,B2)-SAT problem
Note that G c contains no (almost) PEC cycles through s and t and a minimum shortest PEC path from s to t has size L = 6. Further, observe that the degree of t is m + 2n, so every edge incident to t must participate in a path of size at most L + 2 (in the case instance I is true at some assignment). In addition, every s-t path that contains edges of a β k G xi gadget must also contain some vertex c j , otherwise its length would be greater than L + 2.

Initially, consider G c as above with 2n + m PEC s-t paths of size at most L + 2. Clearly, 2n paths must contain a PEC sub-path from w ik to Z ik in α G xi and every α G xi contributes with exactly 2 paths. Then all paths of α G xi contain only vertices u ik or ūik , 1 ≤ k ≤ 2. The other m paths contain a vertices c j , 1 ≤ j ≤ m, and a vertex u ik (or ūik ) that is not in any of the first 2n paths. If u ik (resp., ūik ) is on the same path as the vertex c j , the j th clause c j is satisfied by assigning x i to true (resp., x i to false). In this way, we can easily obtain a truth assignment for I satisfying all clauses. See the example of Figure 11.

Reciprocally, if x i (resp., xi ) of c j is true at some truth assignment of I, there will be m PEC s-t paths of size L + 2 in G c passing by gadgets β k G xi , vertices u ik (resp., ūik ), U ik (resp., Ūik ) and c j (where k denotes the k th occurrence of x i (resp., xi )). The remaining 2n PEC paths of size L + 2 will pass by gadgets α G xi , two paths per gadget, and use vertices u ik or ūik not used by the previous m PEC paths. In this case, we can easily see that 2n + m PEC s-t paths of size at most L + 1 in G c will be associated to satisfiable truth assignments for I and vice-versa. 5 Monochromatic s-t paths in edge-colored graphs

2 t Z i2 Z i1 W i2 xi2 Xi2 y i2 W i1 x i1 y i1 xi1 x i2 w i1 w i2 s α ′ G xi β ′ k G xi (b) b ik xik x ik s (a) a ′ ik a ik X i2 X i1 Xi1
Here, we deal with monochromatic s-t paths in c-edge-colored graphs. We show that finding k vertex disjoint monochromatic s-t paths with different colors is NP-complete even for k = 2. As an immediate consequence, the same problem over c-edge-colored digraphs is also NP-complete. Notice that finding one monochromatic s-t path in G c or 2 monochromatic edge disjoint s-t paths in G c (with the same color) can be easily solved in polynomial time (by using for each i ∈ I c , a polynomial algorithm for finding one s-t path in (V, E i (G c ))). However if the color of both paths are different, we have the following result:

Theorem 16 Let G c be a c-edge-colored graph with s, t ∈ V (G c ) with c ≥ 2 and maximum vertex degree equal to 4. The problem of finding two vertex disjoint monochromatic s-t paths with different colors in G c is NP-complete.

Proof: This proof is similar to the one of Theorem 9, i.e., we reduce an instance I of the (3, B2)-SAT to the existence of two monochromatic s-t paths with different colors in G c for c = 2. Then we use the same notations and only describe how G c is built upon I.

The graph G c will be composed by clause components G cj (for j = 1, . . . , m) and variable components G xi (for i = 1, . . . , n). For each x i ∈ X we build an identical gadget as depicted on the left of Figure 7 (also colored 2 -bold). Similarly to Theorem 9, the right (resp., left) part of this gadget corresponds to the case where x i is set to true (resp., false). The gadget of a clause c j consists of an entrance q j , an exit w j and 3 vertices u 1 j , u 2 j , and u 3 j corresponding to the first, second and third variables of c j , respectively. We conclude the construction of G cj by adding 6 edges q j u k j for k = 1, 2, 3 and u k j w j for k = 1, 2, 3, all of them with color 1 (thin). Now, we add vertices s, t and link all gadgets G xi (resp., G(c j )) by adding the following edges as described in the Figure 13(a):

• sa 1 , b 1 a 2 , b 2 a 3 , . . . , b n-1 a n and b n t, all of them with color 2 (bold);

• sq 1 , w 1 q 2 , w 2 q 3 , . . . , w m-1 q m , w m t, all of them with color 1 (thin). For each pair x i , c j such that x i is the -th variable of c j and c j is the h-th clause of x i we proceed as follows. If x i appears negated in c j then add edges t h-1 ia u j , t h-1 i b u j and f h-1 ia f h-1 i b , all colored 2 (bold). If x i appears unnegated in c j then add f h-1 ia u j , f h-1 i b u j and t h-1 ia t h-1 i b , all colored 2 (bold). Clearly, the construction of G c can be done in polynomial time in the size of X and C. Further, observe that truth assignments for an instance I of the (3, B2)-SAT problem are associated to 2 vertex disjoint monochromatic s-t paths of colors 1 and 2, respectively. To construct the path with color 2 (bold), whenever a variable x i is true (resp., false), we take the sub-path between vertices a i and b i by using the right (resp., left) side of G xi (see Figure 13(b)). The unvisited vertices u j of c j can be used at random, to construct the path colored 1 (thin) between s and t. Reciprocally, if we have 2 vertex disjoint monochromatic s-t paths of colors 1 and 2 then we have a truth assignment for I. For instance, if a vertex u j of the component G cj is visited by some path colored 1 and variable x i (appearing in the -th position of c j ) is in the negated form (resp., unnegated form) then variable x i must be false (resp., true) and clause c j will be true in the assignment. Therefore, by using both monochromatic s-t paths with colors 1 and 2 we can uniquely determine a truth assignment for I, which completes the proof for c = 2.

The generalization of our proof for graphs containing c ≥ 3 colors is identical to Theorem 9 above and will be omitted here.

2

Note that if G c has maximum degree equal to 3, the determination of two vertex disjoint monochromatic s-t paths with different colors can be easily solved in polynomial time. To do that, it suffices to delete all edges xy of E(G c ), say colored i, with x, y ∈ V (G c ) \ {s, t} and such that xy is the unique edge with color i incident to x or y (since we cannot have monochromatic s-t paths through these edges). Finally, we delete all edges sx (resp., yt), say colored i, if sx (resp., yt) is the unique edge with color i incident to vertex x (resp., y).

We conclude with the following related problem: Problem 4 Consider a planar c-edge-colored graph G c and 2 vertices s, t ∈ V (G c ). Does the problem of finding 2 monochromatic s-t paths with different colors NP-complete?

Conclusions and final remarks

A number of problems defined over arbitrary c-edge-colored graphs and regarding one or more PEC s-t paths, trails and closed trails are hard to solve (see Subsection 1.1). As a consequence, we have restricted ourselves to problems defined over some particular classes of graphs such as graphs containing no PEC cycles or closed trails or just graphs with no (almost) PEC cycles or closed trails through s or t. These classes are interesting since they constitute, in a certain sense, the edge-colored counterpart of non-colored acyclic digraphs. Moreover, through the use of different graph techniques, we have extended some of the paths and trails problems defined over non-colored graphs and digraphs [START_REF] Tragoudas | Computing Disjoint Path with Length Constraints[END_REF].

As a future direction a possible question is to study PEC paths and trails restricted to other classes of c-edgecolored graphs, such as regular, planar and serial parallel graphs. Another possibility is to investigate the Fundamental Lemma (Lemma 1) and its consequences through the adoption of different gadgets (such as the XP and BJGP-gadgets) as discussed in [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF][START_REF] Gutin | Properly coloured cycles and paths: results and open problems[END_REF]. In this case, one should analyze their impact in the proofs and complexity of the proposed algorithms. Finally, an interesting subject is to consider the MAX-MIN k-PEC s-t path/trail problem whose objective is to determine k vertex/edge disjoint PEC s-t paths/trails so that the minimum path/trail length is maximized.

Fig. 1 :

 1 Fig. 1: Graph G c (a) and its associated Edmonds-Szeider graph G (b). Note that the perfect matching M in G (bold lines) is associated with a PEC cycle, say ρ, with vertices V (ρ) = (a, b, d, c) in G c .

  (b) For each edge xy of G c , say colored k, add two new vertices v xy and u xy and add edges x i v xy , u xy y j , for i = 1, . . . , α x and j = 1, . . . , α y , all of them colored by k. (c) Add edge v xy u xy with a new unused color k ∈ {1, . . . , c} with k = k.

( 1 )

 1 Initially, define α min (x) = 0 and α max (x) = d G c v (x)/2 , for every x ∈ V (G c v ) \ (S ∪ {v}). (2) Define α min (x) = 0 and α max (x) = 1, for every x ∈ S and set α min (v) = α max (v) = ᾱv = |S|/2 .

Fig. 4 :

 4 Fig. 4: PEC closed trails visiting vertex x1 exactly 3 times: (a) The first and last edges of ρ incident to x1 have different colors and (b) The first and last edges of ρ incident to x1 have the same color

Fig. 5 :

 5 Fig. 5: (a) Edge xy ∈ E in G c ; (b) Subgraph Hxy of H c v (Iα) associated to xy; (c) Non-colored subgraph of H v (associated to Hxy).

2

 2

Fig. 6 :Problem 2

 62 Fig. 6: (a) Arc e = xu of A, (b) Gadgets Gx and G e associated with vertex x and arc e, respectively.

Fig. 7 :

 7 Fig. 7: Gadgets for a variable xi (a) and a clause cj (b).

Fig. 8 :

 8 Fig. 8: (a) Linking gadgets Gx i and Gc j , respectively. (b) x2 appears in the clauses c1= (x2 ∨ x3 ∨ x5), c2 = (x2 ∨ x3 ∨ x6), c3 = (x1 ∨ x2 ∨ x4) and c4 = (x1 ∨ x2 ∨ x5).

  Finally, construct the weighted modified Edmonds-Szeider graph, denoted here by HΦ (k) and associated to H c Φ (I α ) and k, respectively. Now, we proceed as follows: (a) Set k = |E(G c )|/L (maximum number of PEC s-t trails with length L) and compute HΦ (k) as above; (b) Find a minimum perfect matching M * over HΦ (k), if one exists; (c) If M * exists and cost(M * ) = kL we are done (return k). Otherwise, set k ← k -1, update HΦ (k) and return to step (b).

  ) and 10(b)). Vertices u ik (resp. ūik ) of α G xi correspond to the k th occurrence of x i (resp., xi ) in I for k = 1, 2.

color 2 color 1 Fig. 10 :

 110 Fig. 10: Gadgets α Gx i (a) and β k Gx i (b).

Fig. 11 :

 11 Fig. 11: The graph G c associated with the instance(x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) of the (3,B2)-SAT problem

2 Corollary 15

 215 Consider a c-edge-colored graph G c with c ≥ 3 and with no (almost) PEC cycles through s or t in V (G c ). If L > 0 denotes the length of a shortest PEC s-t path, the problem of finding k vertex disjoint PEC s-t paths (resp., trails) in G c with length at most L + 1 is NP-complete. Proof: In this case, it suffices to change the combined gadget of Figures 10.(a) and 10.(b), respectively, by a new combined gadget α G xi , β k G xi for 1 ≤ k ≤ 2, as described in the Figure 12.

Fig. 12 :Problem 3

 123 Fig. 12: Gadgets α Gx i (a) and β k Gx i (b).

Fig. 13 :

 13 Fig. 13: (a) Linking components Gx i and Gc j , respectively. (b) Variable x2 appears in the clauses c1= (x2 ∨ x3 ∨ x5), c2 = (x1 ∨ x2 ∨ x6), c3 = (x1 ∨ x2 ∨ x4) and c4 = (x2 ∨ x3 ∨ x6).

Acknowledgements

We are very grateful to Prof. Fábio Protti and the anonymous referees for their insightful comments and to Prof. Rachid Saad for providing us with reference [5]. We are also grateful to CNPq\Brazil and FAPERJ\Brazil for their partial financial support.

Now, as a consequence of the Fundamental Lemma and Lemma 3 above we have the following result:

Theorem Let G c be a c-edge-colored graph with no PEC closed trails, s, t ∈ V (G c ) and a non-empty subset Ψ of V (G c ) \ {s, t}. Then, we can find within polynomial time, if any, a PEC s-t trail visiting all vertices of Ψ.

Proof: Given G c , introduce an additional vertex v and construct a new c -edge-colored G c v as discussed in the Theorem 2 above. Now consider W = {s, t, v} and define intervals I α (x) associated to vertices x ∈ V (G c v ) as in the sequel. Initially, set α min (x) = α max (x) = 1, for every x of W . Since G c contains no PEC closed trails, we conclude from Lemma 3 that arbitrary s-t trails in G c , if any, contain vertices visited at most 2 times. Therefore, we set α max (x) = 2 for every x of V (G c v ) \ W . Now, since all vertices of Ψ must be visited at least once, we define α min (x) = 1 for every x of Ψ and α min (x) = 0 for every

In the sequel, construct the associated modified Edmonds-Szeider graph Hv as detailed in the Fundamental Lemma. After finding a perfect matching over Hv , provided that one exists, we can easily determine a PEC closed trail in G c v visiting all vertices of W ∪ Ψ and such that function α is satisfied. This will correspond to a PEC s-t trail visiting all vertices of Ψ in G c . 2

In the sequel, we show how to extend the Fundamental Lemma in order to force the visit of a given subset E of edges. Formally: E) be a c-edge-colored graph with no PEC closed trails and E ⊆ E. Then, we can find within polynomial time, if any, a PEC s-t trail visiting all edges of E .

Proof:

Initially, construct G c v and function α exactly in the same way as described in the first paragraph of Theorem 4 and define α min


Manuel E Lladser
email: manuel.lladser@colorado.edu

† Primož Potočnik

‡ Jozef Širáň

Mark C Wilson

Random Cayley digraphs of diameter 2 and given degree

Keywords: Random digraph, Cayley digraph, degree, diameter

We consider random Cayley digraphs of order n with uniformly distributed generating sets of size k. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as n → ∞ and k = f (n), focusing on the functions f (n) = n δ and f (n) = cn . In both instances we show that this probability converges to 1 as n → ∞ for arbitrary fixed δ ∈ ( 1 2 , 1) and c ∈ (0, 1 2 ), respectively, with a much larger convergence rate in the second case and with sharper results for Abelian groups.

Introduction

It is well known that almost all graphs and digraphs have diameter two [START_REF] Bollobás | Graph Theory, An Introductory Course[END_REF]. This result has been generalized and strengthened in various directions, of which we shall be interested in restrictions to Cayley graphs and digraphs.

In [START_REF] Meng | The diameters of almost all Cayley digraphs[END_REF] it was proved that almost all Cayley digraphs have diameter two, and in [START_REF] Meng | Almost all Cayley graphs have diameter 2[END_REF] this was extended to Cayley graphs. The random model used in [START_REF] Meng | The diameters of almost all Cayley digraphs[END_REF][START_REF] Meng | Almost all Cayley graphs have diameter 2[END_REF] is the most straightforward one: in terms of Cayley digraphs for a given group G of order n, one chooses a random generating set by choosing its elements among the non-identity elements of G independently and uniformly, each with probability 1/2. Observe that such generating sets have size at least n/2 with probability at least 1/2, in which case a simple counting argument shows that the corresponding Cayley digraphs have diameter at most two. The less trivial part of [START_REF] Meng | The diameters of almost all Cayley digraphs[END_REF] therefore concerns random Cayley digraphs in which the number of generators is at most half of the order of the group. This motivates a study of random Cayley digraphs in which the number of generators is restricted. In this case one cannot use the model of [START_REF] Meng | The diameters of almost all Cayley digraphs[END_REF]. Instead, we let every generating set of the Cayley digraph of a fixed degree appear with equal probability. The fundamental question here is: For which functions f is it true that the diameter of a random Cayley digraph of an arbitrary group of order n and of degree f (n) is asymptotically almost surely equal to 2 as n tends to infinity? By the well-known Moore bound for graphs or digraphs of diameter two we know that f has to increase at least as fast as √ n. A study of the behaviour of the problem for functions of the form f (n) = n δ for the powers δ satisfying 1/2 ≤ δ < 1 is therefore natural in this context. However, even the case when f (n) = cn for a constant c seems not to have been investigated before and, as we shall see, leads to an interesting asymptotic analysis.

The probability that a random Cayley digraph of (in-and out-) degree k on a group of order n has diameter 2 will be estimated in Section 3 in terms of a certain combinatorial function the asymptotic analysis of which yields the following main results, proved in Section 4:

• For every c such that 0 < c < 1/2, the probability of a random Cayley digraph of degree cn on a given group of order n having diameter 2 is at least 1 -O(exp(-c 2 n/2)).

• For every δ such that 1/2 < δ < 1, the probability of a random Cayley digraph of degree n δ on a given group of order n having diameter 2 is at least

1 -O(exp(-n 2δ-1 /2)).
• There is a constant c 1 such that for every function µ defined on positive integers, with µ(n) → ∞ as n → ∞, the probability of a random Cayley digraph of degree 2n ln(c 1 nµ(n)) on a group of order n having diameter 2 tends to 1 as n → ∞.

• There is a positive constant c 2 < 1 such that for every ε with 0 < ε < c 2 the probability of a random Cayley digraph of degree 2n ln(c 2 /ε) on an Abelian group of order n having diameter 2 has limes superior not exceeding 1 -ε.

The model

Throughout, let G be a finite group of order n and let k be a positive integer not exceeding n -2. The set of non-trivial elements of G will be denoted by G * . For a set A and an integer r, the symbol A r stands for the set of all subsets of A of size r.

For S ∈ G * k , the Cayley digraph on G relative to S, denoted by Cay(G, S), is the k-valent digraph with vertex set G and arc set {(g, gs) : g ∈ G, s ∈ S}. The distance ∂ S (g, h) from the vertex g to the vertex h in Cay(G, S) is the length of the shortest directed path from g to h in Cay(G, S). The diameter diam(Cay(G, S)) is the smallest integer d such that for every ordered pair (g, h) the distance from g to h is at most d.

We are now ready to introduce our model for random Cayley digraphs of a given valence. Let P(G, k) be the probability space (B, 2 B , Pr) where B = G * k , 2 B is the power set of B, and Pr is the uniformly distributed probability measure on B.

Since |B| = n-1 k , Pr({S}) = n-1 k -1 for all S ∈ B.
More generally, for every subset L ⊆ G * of size , the probability that a random set S ∈ B contains L as a subset is given by

Pr(S ⊇ L) = Pr S ∈ G * k : L ⊆ S = n -1 - k - n -1 k -1
.

(1)

Before proceeding, note that one could think of a seemingly easier model, where each element of G * is chosen to be a member of S independently and with probability k/(n -1). This model may well be equivalent to our model and it may well be possible to prove their equivalence in a way similar to arguments about the equivalence of the two standard models of random graphs (cf. Chapter 2 of [START_REF] Bollobás | Graph Theory, An Introductory Course[END_REF]). In view of the length of the arguments of Chapter 2 of [START_REF] Bollobás | Graph Theory, An Introductory Course[END_REF], however, research into a possible equivalence of the two models should be the object of a separate article, which is the reason why we chose not to pursue this direction.

Let Diam : B → R be the random variable on the space P(G, k) defined by letting, for every S ∈ G * k , Diam(S) = diam(Cay(G, S)).

(2)

The main goal of this article is to derive bounds on the probability of the event Diam(S) > 2 and study the asymptotic behavior of the bounds. Since Cayley digraphs are vertex-transitive, the diameter of Cay(G, S) coincides with the maximum value of ∂ S (1, y) over all y ∈ G * . Clearly, ∂ S (1, y) ≤ 2 if and only if y ∈ S, or there exists x ∈ S such that (1, x, y) is a directed path from 1 to y of length 2. The latter is equivalent to requiring that {x, x -1 y} ⊆ S; in particular, the events in the following definition play an important role in the analysis.

Definition 2.1 For x, y ∈ G * , let T (x, y) = S : S ∈ G * k , {x, x -1 y} ⊆ S and X(y) = x∈G * \{y} T (x, y).
If S is an arbitrary element of G * k and Diam(S) ≤ 2 then, for each y ∈ G * , y ∈ S or S ∈ X(y). Hence Pr(Diam ≤ 2) ≤ min y∈G * Pr(y ∈ S or S ∈ X(y)). In particular, if Pr(X(y) | y / ∈ S) denotes the conditional probability of the complement X(y) of X(y) given that y / ∈ S, we have:

Pr(Diam > 2) ≥ max y∈G * Pr(y / ∈ S and S / ∈ X(y)) = (1 - k n -1 ) • max y∈G * Pr(X(y) | y / ∈ S),
where the last identity is a direct consequence of (1). On the other hand, if Diam(S) > 2 then there exists y ∈ G * such that y / ∈ S and S / ∈ X(y). This results in

Pr(Diam > 2) ≤ y∈G * Pr(X(y) | y / ∈ S) • Pr(y / ∈ S) ≤ (n -k -1) • max y∈G * Pr(X(y) | y / ∈ S) .
These inequalities immediately lead to the following result:

Proposition 2.2 The random variable Diam satisfies

(1 - k n -1 ) • M ≤ Pr(Diam > 2) ≤ (n -k -1) • M , (3)
where

M = max y∈G * Pr(X(y) | y / ∈ S) . (4)
Notice that the upper and lower bounds in (3) differ by a linear factor of order n. These bounds will be used in Section 4 for asymptotic estimates on the probability of the event [Diam > 2].

Probability estimates

We begin with an auxiliary result on groups that we will need later. If G is a group and y ∈ G, we say that z ∈ G is a square root of y if z 2 = y. Lemma 3.1 Let G be a finite group. If the order of G is odd, then every y ∈ G has a unique square root in G. If the order of G is even, then there exists at least one element y ∈ G with no square root in G.

Proof: Consider the mapping s : G → G, x → x 2 . Suppose first that |G| = 2m + 1 is odd; in particular, x 2m+1 = 1, for all x ∈ G, due to Lagrange's theorem. Hence, for every x, y ∈ G, we see that x 2 = y 2 implies that x = x 2m+2 = y 2m+2 = y. So s is a bijection and therefore each y ∈ G has a unique square root in G if the group has odd order. On the other hand, if |G| is even, G has a non-trivial involution x. Since s(x) = 1 = s(1), s is not a bijection. Since G is finite, it follows that s is not surjection, and so there is an element y ∈ G with no square root in G.

2

The basis for our estimates on the probability Pr(Diam > 2) is provided by a bound on M which we state and prove next.

Proposition 3.2 For each group G of order n ≥ 3 and every k such that 1 ≤ k ≤ n -2 we have M ≤ 2 k t k n -2 k -1 where t = (n -2)/2 , (5)
with equality if G is Abelian.

Proof: If y ∈ G * , we will use the symbol G * y to denote the set G * \{y}. For each y ∈ G * let X (y) = {S ∈ G * y k : {x, x -1 y} ⊂ S for all x ∈ G * y }. We claim that M = χ • n -2 k -1
where χ = max y∈G * |X (y)| . By Lemma 3.1 we know that if G is odd, then for every y ∈ G * there exists a unique x = x y ∈ G such that x 2 = y. For each y ∈ G * we let W y = G * y if |G| is even, and W y = G * \{y, x y } if |G| is odd. It can be checked that for every fixed y ∈ G * the mapping x → γ y (x) given by γ y (x) = x -1 y is a permutation of this newly introduced set W y . Notice that the size of W y is always even. Further, observe that for all y ∈ G * we have S ∈ X (y) if and only if S ⊂ W y , |S| = k, and S ∩ γ y (S) = ∅. Letting w(γ y ) = |{S ⊂ W y : |S| = k, S ∩ γ y (S) = ∅}|, this observation combined with (6) gives

χ = max y∈G * w(γ y ) . (7)
To estimate w(γ y ) we will extend the definition of w to arbitrary permutations by letting, for an arbitrary permutation α y of the set W y ,

w(α y ) = |{S ⊂ W y : |S| = k, S ∩ α y (S) = ∅}| . (8)
Our strategy will be to show that for every y ∈ G * there exists an involution β y on the set W y such that w(γ y ) ≤ w(β y ) = t k 2 k . We will construct β y by defining it on every orbit O ⊂ W y of γ y successively. Since the construction will work for all y ∈ G * we will suppress subscripts on permutations and let W y = W , γ y = γ and β y = β in the description of the construction. Suppose first that |O| is even. The restriction of γ on O is a cyclic permutation; let O 1 and O 2 be the two orbits of γ 2 on O. Define the restriction of β on O by letting

β(z) = γ(z) if z ∈ O 1 and β(z) = γ -1 (z) of z ∈ O 2 . It is easy to check that for each subset T ⊂ O the condition T ∩ γ(T ) = ∅ implies that T ∩ β(T ) = ∅.
The case of orbits of odd size requires more attention. Since |W | is even, γ has an even number of orbits of odd size on W . Let us partition the set of odd-sized orbits of γ into ordered pairs and let (O 1 , O 2 ) be such a pair. Then, γ induces cyclic permutations, say, (u 1 , . . . , u 2r+1 ) and (v 1 , . . . , v 2s+1 ), of O 1 and O 2 , respectively, for some r, s ≥ 0. Define the restriction of

β on O 1 ∪ O 2 by letting β = (u 2r+1 u 2r ) . . . (u 3 u 2 )(u 1 v 1 )(v 2 v 3 ) . . . (v 2s v 2s+1 ). Let T be a subset of O 1 ∪ O 2 such that T ∩ γ(T ) = ∅.
We construct a new set T o out of T as follows. If u 1 , u 3 , v 1 , v 3 ∈ T , we take the smallest i and j such that both u 2i+1 and v 2j+1 lie outside T ; the condition T ∩ γ(T ) = ∅ implies that such i and j exist and 2 ≤ i ≤ r -1 and 2 ≤ j ≤ s -1. In this situation we let

T o = (T \{u 1 , v 1 }) ∪ {u 2i+2 , v 2j+2 }, and it is obvious that T o ∩ β(T o ) = ∅. If u 1 , u 3 , v 1 ∈ T but v 3 / ∈ T , we let T o = (T \{u 1 }) ∪ {u 2i+2 }
, where i is defined as before. In the case when v 1 , v 3 , u 1 ∈ T but u 3 / ∈ T we proceed symmetrically, swapping u and v (with appropriate subscripts). If

u 1 , v 1 ∈ T but u 3 , v 3 / ∈ T , we let T o = (T \{u 1 }) ∪ {v 2 }.
In all these cases it is easy to check that T o ∩ β(T o ) = ∅. In all the remaining cases we let

T o = T , noticing again that T o ∩ β(T o ) = ∅.
Finally, let S be a subset of W such that |S| = k and S ∩ γ(S) = ∅. We define S by letting S ∩ O = S ∩ O for every even-sized orbit O of γ, and

S ∩ (O 1 ∪ O 2 ) = (S ∩ (O 1 ∪ O 2 )) o for each ordered pair (O 1 , O 2 ) of
odd-sized orbits of γ from our fixed pairing of such orbits, as introduced above.

The key point to observe is that the assignment S → S is injective. Moreover, the facts about the sets T and T o listed in the previous two paragraphs imply that S ∩ β(S ) = ∅.

The above arguments prove that w(γ y ) ≤ w(β y ) for all y ∈ G * . Further, since β y is a product of t = (n -2)/2 cycles of length 2, the quantity w(β y ) defined in (8) is equal to t k 2 k since a set S ⊂ W y with |S| = k such that S ∩ β y (S) = ∅ arises precisely by choosing k cycles of β y length 2 out of t such cycles and choosing one of the two elements in each chosen 2-cycle. These facts combined with (7) and (6) imply the bound in our Proposition for general groups.

If G is Abelian, choose y ∈ G * arbitrarily if G has odd order, and let y ∈ G * be an element with no square root if the order of G is even. Then the permutation γ y of W y is an involution with no fixed point and hence β y = γ y in this case, implying equality for Abelian groups.

2

In combination with Proposition 2.2 this gives the following consequence.

Proposition 3.3 Letting t = (n -2)/2 and a(n, k) = 2 k t k n-2 k -1 , the random variable Diam satisfies 1 -(n -k -1)a(n, k) ≤ Pr(Diam ≤ 2)
for general groups, and

1 -(n -k -1)a(n, k) ≤ Pr(Diam ≤ 2) ≤ 1 -(1 - k n -1 )a(n, k)
for Abelian groups. 2

Asymptotic analysis

In the context of Proposition 3.3 with t = (n -2)/2 we write

a(n, k) = b(t, k)c(t, k), (9)
where

b(t, k) = 2 k t k 2t k -1 and c(t, k) = 1 if n is even, c(t, k) = 2t -k + 1 2t + 1 if n is odd.
For the asymptotic analysis of the behaviour of binomial coefficients appearing in b(t, k) we use Stirling's approximation. To state the result of the corresponding routine calculations in a concise form, for

0 < λ < 1 let R(λ) = (2 -λ) ln(1 -λ/2) -(1 -λ) ln(1 -λ) , P (λ) = 2 -λ 2 -2λ 1/2
, and

C(t, λ) = 1 + O(t -1 ) + O((tλ) -1 ) + O((t(1 -λ)) -1 ) as t → ∞.
Then, writing k = λt, routine calculation with the help of Stirling's approximation yields

b(t, k) = exp(tR(λ)) P (λ) C(t, λ) ; (10)
the terms R, P and C represent the exponential rate, the leading coefficient, and the correction term. The exponential rate R(λ) is easily seen to be negative for 0 < λ < 1. Furthermore C(t, λ) tends to 1 for each fixed λ ∈ (0, 1) as t → ∞. Note also that

R(λ) = (2 -λ) ln(1 -λ/2) -(1 -λ) ln(1 -λ) = -λ 2 /4 + O(λ 3 ) for 0 < λ < 1. (11)
Our first result about the behaviour of Pr(Diam ≤ 2) in the case of general groups deals with the situation where k ≈ cn for some c < 1/2. In our asymptotic calculations for n → ∞ we may then replace λ = k/t for t = (n -2)/2 with the value 2c. Combining now (9), (10) and (11). with the lower bound of Proposition 3.3 we arrive at the following result: Theorem 4.1 For each c such that 0 < c < 1/2, the probability of a random Cayley digraph on a group of order n and degree cn having diameter 2 is at least

1 -O(n • exp(-c 2 n/2)).
2

We now turn to the case where k ≈ n δ with 1/2 < δ < 1. For k = λt with λ = o(1) as t → ∞, the approximation (11) is still valid, and we also have C(t, λ) = 1 + O(λ). Thus, if k grows at least as fast as n δ with δ > 1/2, for asymptotic computation we may replace k with 2n δ-1 t and set λ = 2n δ-1 . Then, the exponent tR(λ) in (10) may be replaced with -n 2δ-1 /2, which implies exponential decay if δ > 1/2. Using the lower bound of Proposition 3.3 again, we have the following conclusion.

Theorem 4.2 For every δ such that 1/2 < δ < 1, the probability of a random Cayley digraph on a group of order n and degree n δ having diameter 2 is at least 1 -O(n • exp(-n 2δ-1 /2)).

It is natural to ask what happens when k ≈ √ n. By the Moore bound for diameter two, the probability of a random Cayley digraph of degree k and order n (for a general group) having diameter 2 is zero if k < √ n . It is interesting to note that if the right-hand side is increased by a factor of 2, then for an arbitrary n of the form n = 2 2d there exists a Cayley (di)graph of order n and degree k = 2 √ n = 2 • 2 d on an elementary Abelian group of order n, which has diameter 2. Indeed, representing vertices of the graph as 2d-dimensional 0-1 vectors, it is sufficient to consider a generating set of the form S 1 ∪ S 2 where S 1 and S 2 consists of all non-zero vectors having the first d and the last d coordinates equal to zero, respectively. It follows that the probability that a random Cayley (di)graph on an elementary Abelian 2-group of order n and degree k = 2 √ n has diameter 2 is positive. This, of course, does not allow to make any conclusion as to how large this probability might be.

However, our approximation above shows that if k = c √ n , then the lower bound from Proposition 3.3 tends to negative infinity as n → ∞, while the upper bound for Abelian groups converges to 1exp(-c 2 /2). In particular, this shows that, when restricted to Cayley graphs on Abelian groups of order n and valence c √ n, the probability Pr(Diam ≤ 2) does not tend to 1 as n → ∞, for any value of c. This brings us to the question in the Introduction concerning the threshold for k = f (n) at which the asymptotic value of the upper bound on Pr(Diam ≤ 2) undergoes a phase transition, switching abruptly from 0 to 1 as k increases. Our previous findings allow us to give a more precise information about the transition.

Theorem 4.3 Let G be a finite group of order n and let P (n, k) denote the probability that a random Cayley digraph of degree k = f (n) on G has diameter at most 2.

• There is a constant c 1 > 0 such that for an arbitrary function µ defined on positive integers, with

µ(n) → ∞ as n → ∞, we have: if f (n) ≥ 2n ln(c 1 nµ(n)), then lim n→∞ P (n, k) = 1.
• In the case of Abelian groups, there is a positive constant c 2 < 1 such that for every ε with 0 < ε < c 2 we have: if f (n) ≤ 2n ln(c 2 /ε), then lim sup n→∞ P (n, k) ≤ 1 -ε.

Proof: To simplify the asymptotic calculations we may replace t with n/2 and λ = k/t with 2k/n. Moreover, by (11), (10) and other findings accumulated at the beginning of this Section, together with the fact that the coefficient at λ 3 in the O(λ 3 ) term in (11) is positive, for sufficiently large n and for k = o(n 2/3 ) we have an upper bound on a(n, k) of the form exp(-k 2 /(2n)) ≤ a(n, k) ≤ c 1 •exp(-k 2 /(2n)) for some positive constant c 1 that absorbs the multiplication effect of the term e tO(λ 3 ) = e O(k 3 /n 2 ) appearing in (11) and of the terms P (λ), C(t, λ) from (10). Combining this with Proposition 3.3 we obtain, for k ≥ √ n and k = o(n 2/3 ),

Pr(Diam ≤ 2) ≥ 1 -c 1 • n • exp(-k 2 /( 2n
)) for general groups, and

Pr(Diam ≤ 2) ≤ 1 -c 2 • exp(-k 2 /(2n)) for Abelian groups, (12)
where the positive constant c 2 < 1 absorbs the effect of multiplication by 1 -k/(n -1) appearing in Proposition 3.3; note that for k = o(n 2/3 ) this constant can be chosen arbitrarily close to 1 for sufficiently large n.

Clearly it is sufficient to prove the statement in the case when µ has polynomial growth. Routine limit calculation using this assumption show that if k = 2n ln(c 1 nµ(n)) , then c 1 n exp(-k 2 /(2n)) • µ(n) → 1 as n → ∞. Thus, for every ε > 0 there exists an n(ε) such that for all n > n(ε) we have c 1 n exp(-k 2 /(2n)) < (1 + ε)/µ(n). Since µ(n) → ∞ as n → ∞, for the same ε we have µ(n) > 1 + 1/ε for n sufficiently large. The last two inequalities with (12) yield P (n, k) > 1 -ε for all sufficiently large n (depending on ε). Consequently, for k ≥ 2n ln(c 1 nµ(n)) we have P (n, k) → 1 as n → ∞.

In the Abelian case, for every positive ε < c 2 let k = 2n ln(c 2 /ε) . For such a function k we have exp(-k 2 /(2n)) → ε/c 2 as n → ∞. By (13) this means that lim sup n→∞ P (n, k) ≤ 1 -ε for all k ≤ 2n ln(c 2 /ε) . 2

It is possible to derive still a slightly more detailed information about P (n, k) by further asymptotic analysis of the inequalities (12) and ( 13), but for the sake of conciseness we chose to highlight just the two items contained in Theorem 4.3. We remark, however, that substantial refinements would require improvements on the bounds of Proposition 3.3 which differ by a factor of n -1.

Although our asymptotic analysis answers a number of natural questions about the probability of a random Cayley digraph of a fixed degree having diameter 2, some questions still remain. For example, the case k ∼ c √ n is not settled by our analysis for general groups, nor is the exact asymptotic order of the phase transition where Pr(Diam ≤ 2) switches from almost impossible to almost inevitable. We know that this order is at most √ n ln n and definitely exceeds √ n, and we conjecture that for both Abelian and general groups,

√

n ln n is the correct order.

  each y ∈ G * , the distribution of S when the condition on the event [y / ∈ S] is uniform over the set G * y k . In particular, Pr(X(y) | y / ∈ S) = n-2 k -1 |X (y)|, and the claim now follows from the definition of M in (4).

Acknowledgements

Work on this paper begun at the University of Auckland, New Zealand, when the second author was visiting the third author thanks to the support of the local Department of Mathematics and NZIMA. Their enquiries about asymptotic analysis led from Auckland to Slovenia (M. Petkovšek) to Pennsylvania (H. Wilf) and then via Robin Pemantle to the first and the fourth author, the latter being blissfully unaware in Auckland of the existence of the work going on in the same building! The authors also thank Jana Šiagová from Slovak University of Technology, Bratislava, Slovakia, who was originally involved in discussions on the topic and decided to withdraw at a later stage.

The second author was partially supported by the ARRS Grant J1-0540. Research of the third author was supported by the VEGA Research Grant 1/0781/11, APVV Research Grants 0104-07 and 0223-10, and the APVV support as part of the EUROCORES Programme EUROGIGA, project GREGAS, ESF-EC-0009-10, financed by the European Science Foundation.