The Road Coloring Problem

A.N.Trahtman??

Bar-Ilan University,Dep.of Math.,52900,Ramat Gan,Israel

Abstract

A synchronizing word of a deterministic automaton is a word in the

alphabet of colors(considered as letters)of its edges that maps the au-

tomaton to a single state.A coloring of edges of a directed graph is

synchronizing if the coloring turns the graph into a deterministic?nite

automaton possessing a synchronizing word.

The road coloring problem is the problem of synchronizing coloring of

a directed?nite strongly connected graph with constant outdegree of all

its vertices if the greatest common divisor of lengths of all its cycles is

one.The problem was posed by Adler,Goodwyn and Weiss over30years

ago and evoked noticeable interest among the specialists in the theory of

graphs,deterministic automata and symbolic dynamics.

The positive solution of the road coloring problem is presented. Keywords:road coloring problem,graph,deterministic?nite automaton,syn-chronization.

Introduction

The road coloring problem originates in[?]and was stated explicitly in[?]for a strongly connected directed?nite graph with constant outdegree of all its vertices where the greatest common divisor(gcd)of lengths of all its cycles is one.The edges of the graph are unlabeled.The task is to?nd a labelling of the edges that turns the graph into a deterministic?nite automaton possessing a synchronizing word.So the road coloring problem is connected with the problem of existence of synchronizing word for deterministic complete?nite automaton.

The condition on gcd is necessary[?],[?].It can be replaced by the equivalent property that there does not exist a partition of the set of vertices on subsets V1,V2,...,V k=V1(k>1)such that every edge which begins in V i has its end in V i+1[?],[?].The outdegree of the vertex can be considered also as the size of an alphabet where the letters denote colors.

The road coloring problem is important in automata theory:a synchronizing coloring makes the behavior of an automaton resistant against input errors since, after detection of an error,a synchronizing word can reset the automaton back ?Email:trakht@macs.biu.ac.il

?http://www.cs.biu.ac.il/～trakht

1

to its original state,as if no error had occurred.The problem appeared?rst in the context of symbolic dynamics and is important also in this area.

Together with theˇCerny conjecture[?],[?],the road coloring problem be-longs to the most fascinating problems in the theory of?nite automata.The problem is discussed even in”Wikipedia”-the popular Internet Encyclopedia. However,at the same time it was considered as a”notorious open problem”[?], [?]and”unfeasible”[?].

For some positive results in this area see[?],[?],[?],[?],[?],[?],[?],[?],[?];

a detailed history of investigations can be found in[?].

The concept of Friedman[?]of the weight of a vertex and the concept of a stable pair of states[?],[?]of Culik,Karhumaki and Kari with corresponding results and consequences are used below.

We prove that the road coloring problem has a positive solution.So a?nite directed strongly connected graph with constant outdegree of all vertices and with gcd of the lengths of all its cycles equal to one has a synchronizing coloring. Preliminaries

A?nite directed strongly connected graph with constant outdegree of all its vertices where the gcd of lengths of all its cycles is one will be called AGW graph as aroused by Adler,Goodwyn and Weiss.

The bold letters will denote the vertices of a graph and the states of an automaton.

If there exists a path in an automaton from the state p to the state q and the edges of the path are consecutively labeled byσ1,...,σk,then for s=σ1...σk∈Σ+let us write q=p s.

Let P s be the map of the subset P of states of an automaton by help of s∈Σ+and let P s?1be the maximal set of states Q such that Qs?P.For the transition graphΓof an automaton letΓs denote the map of the set of states of the automaton.

|P|-the size of the subset P of states from an automaton(of vertices from a graph).

A word s∈Σ+is called a synchronizing word of the automaton with tran-sition graphΓif|Γs|=1.

A coloring of a directed?nite graph is synchronizing if the coloring turns the graph into a deterministic?nite automaton possessing a synchronizing word.

A pair of distinct states p,q of an automaton(of vertices of the transition graph)will be called synchronizing if p s=q s for some s∈Σ+.In the opposite case,if for any s p s=q s,we call the pair deadlock.

A synchronizing pair of states p,q of an automaton is called stable if for any word u the pair p u,q u is also synchronizing[?],[?].

We call the set of all outgoing edges of a vertex a bunch if all these edges are incoming edges of only one vertex.

Let u be a left eigenvector with positive components having no common divi-sor of adjacency matrix of a graph with vertices p1,...,p n.The i-th component

2

u i of the vector u is called the weight of the vertex p i and denoted by w(p i). The sum of the weights of the vertices from a set D is denoted by w(D)and is called the weight of D[?].

The subset D of states of an automaton(of vertices of the transition graph Γof the automaton)such that w(D)is maximal and|Ds|=1for some word s∈Σ+let us call F-maximal as introduced by Friedman[?].

The subsetΓs of states(of vertices of the transition graphΓ)for some word s such that every pair of states from the set is deadlock will be called an F-clique. 1Some properties of F-clique and of coloring free of stable pairs

The road coloring problem was formulated for AGW graphs[?]and only such graphs are considered below.We exclude from the consideration also the prim-itive cases of graphs with loops and of only one color[?],[?].Let us formulate two important results from[?]and[?]in the following form:

Theorem1[?]There exists a partition ofΓon F-maximal sets(of the same weight).

Some side conditions on the AGW graph stated in[?]were not used in the proof of this statement.

Let us recall that a binary relationρon the set of the states of an automaton is called c ongruence ifρis equivalence and for any word u from pρq follows p uρq u.

Theorem2[?]Let us consider a coloring of AGW graphΓ.Stability of states is a binary relation on the set of states of the obtained automaton;denote this relation byρ.Thenρis a congruence relation,Γ/ρpresents an AGW graph and synchronizing coloring ofΓ/ρimplies synchronizing recoloring ofΓ.

The last theorem shows that if every AGW graph has a coloring with a stable pair,then every AGW graph has a synchronizing coloring.

Lemma1Let w be the weight of F-maximal set of the AGW graphΓvia some coloring.Then the size of every F-clique of the coloring is the same and equal to w(Γ)/w(the size of partition ofΓon F-maximal sets).

Proof.Two states from an F-clique could not belong to one F-maximal set because this pair is not synchronizing.By Theorem??there exists a partition ofΓon F-maximal sets of weight w.So the partition consists from w(Γ)/w F-maximal sets and to every F-maximal set belongs at most one state from F-clique.Consequently,the size of any F-clique is not greater than w(Γ)/w.

LetΓs be an F-clique.The sum of the weights q s?1for all q∈Γs is the weight ofΓ.So

w(Γ)= q∈Γs w(q s?1)

3

The number of addends(the size of the F-clique)is not greater than w(Γ)/w. The weight of the set q s?1for every q∈Γs is not greater than w.Therefore q s?1is an F-maximal set of weight w for every q∈Γs and the size of any F-clique is w(Γ)/w,the number of F-maximal sets in the corresponding partition ofΓ.

Lemma2Let F be F-clique via some coloring of AGW graphΓ.For any word s the set F s is also an F-clique and any state[vertex]p belongs to some F-clique.

Proof.Any pair p,q from an F-clique F is a deadlock.To be deadlock is a stable binary relation,therefore for any word s the pair p s,q s from F s also is a deadlock.So all pairs from F s are deadlocks.

For the F-clique F there exists a word t such thatΓt=F.ThusΓts=F s, whence F s is an F-clique.

For any r from a strongly connected graphΓ,there exists a word u such that r=p u for p from the F-clique F,whence r belongs to the F-clique F u.

Lemma3Let A and B(|A|>1)be distinct F-cliques via some coloring without stable pairs of the AGW graphΓ.Then|A|?|A∩B|=|B|?|A∩B|>1.

Proof.Let us assume the contrary:|A|?|A∩B|=1.By Lemma??,|A|=|B|. So|B|?|A∩B|=1,too.The pair of states p∈A\B and q∈B\A is not stable.Therefore for some word s the pair(p s,q s)is a deadlock.Any pair of states from the F-clique A and from the F-clique B as well as from F-cliques As and Bs is a deadlock.So any pair of states from the set(A∪B)s is a deadlock. One has|(A∪B)s|=|A|+1>|A|.

In view of Theorem??,there exists a partition of size|A|(Lemma??)of Γon F-maximal sets.To every F-maximal set belongs at most one state from (A∪B)s because every pair of states from this set is a deadlock and no deadlock could belong to an F-maximal set.This contradicts the fact that the size of (A∪B)s is greater than|A|.

Lemma4Let some vertex of AGW graphΓhave two incoming bunches.Then any coloring ofΓhas a stable couple.

Proof.If a vertex p has two incoming bunches from vertices q and r,then the couple q,r is stable for any coloring because qα=rα=p for any letter(color)α∈Σ.

2The spanning subgraph of cycles and trees with maximal number of edges in the cycles D′e?nition1Let us call a subgraph S of the AGW graphΓa s panning sub-graph ofΓif to S belong all vertices ofΓand exactly one outgoing edge of every vertex.

4

A maximal subtree of the spanning subgraph S with root on a cycle from S and having no common edges with cycles from S is called a t ree of S .

The length of path from a vertex p through the edges of the tree of the span-ning set S to the root of the tree is called the l evel of p in S .

Remark 1Any spanning subgraph S consists of disjoint cycles and trees with roots on cycles;any tree and cycle of S is de?ned identically,the level of the vertex from cycle is zero,the vertices of trees except root have positive level,the vertex of maximal positive level has no incoming edge from S .

Lemma 5Let N be a set of vertices of level n from some tree of the spanning subgraph S of AGW graph Γ.Then in a coloring of Γwhere all edges of S have the same color α,any F -clique F satis?es |F ∩N |≤1.

Proof.Some power of αsynchronizes all states of given level of the tree and maps them into the root.Any couple of states from an F -clique could not be synchronized and therefore could not belong to N .

Lemma 6Let AGW graph Γhave a spanning subgraph R of only disjoint cycles (without trees).Then Γalso has another spanning subgraph with exactly one vertex of maximal positive level.

Proof.The spanning subgraph R has only cycles and therefore the levels of all vertices are equal to zero.In view of gcd =1in the strongly connected graph Γ,not all edges belong to a bunch.Therefore there exist two edges u =p →q ∈R and v =p →s ∈R with common ?rst vertex p but such that q =s .Let us replace the edge v =p →s from R by u .Then only the vertex s has maximal level L >0in the new spanning subgraph.

Lemma 7Let any vertex of an AGW graph Γhave no two incoming bunches.Then Γhas a spanning subgraph such that all its vertices of maximal positive level belong to one non-trivial tree.

Proof.Let us consider a spanning subgraph R with a maximal number of vertices

[edges]in its cycles.In view of Lemma ??,suppose that R has non-trivial trees and let L >0be the maximal value of the level of a vertex.

Further consideration is necessary only if at least two vertices of level L belong to distinct trees of R with distinct roots.

Let us consider a tree T from R with vertex p of maximal level L and edge ˉb from vertex b to the tree root r ∈T on the path of length L from p .Let the root r belong to the cycle H of R with the edge ˉc =c →r ∈H .There exists also an edge ˉa =a →p that does not belong to R because Γis strongly connected and p has no incoming edge from R .c c c c c c c ''e e u ?? c p r a d c b E E ··················

'ˉa ˉw ˉc ˉb H T 5

Let us consider the path from p to r of maximal length L in T.Our aim is to extend the maximal level of the vertex on the extension of the tree T much more than the maximal level of vertex of other trees from R.We plan to use the following three changes:

1)replace the edgeˉw from R with?rst vertex a by the edgeˉa=a→p,

2)replace the edgeˉb from R by some other outgoing edge of the vertex b,

3)replace the edgeˉc from R by some other outgoing edge of the vertex c.

If one of the ways does not succeed let us go to the next assuming the situation in which the previous way fails and excluding the successfully studied cases.So we diminish the considered domain.We can use sometimes two changes together.Let us begin with

1)Suppose?rst a∈H.If a belongs to a path in T from p to r then a new cycle with part of the path and edge a→p is added to R extending the number of vertices in its cycles in spite of the choice of R.In opposite case the level of a in the new spanning subgraph is L+1and the vertex r is a root of the new tree containing all vertices of maximal level(in particular,the vertex a or its ancestors in R).

So let us assume a∈H and supposeˉw=a→d∈H.In this case the vertices p,r and a belong to a cycle H1with new edgeˉa of a new spanning subgraph R1.So we have the cycle H1∈R1instead of H∈R.If the length of path from r to a in H is r1then H1has length L+r1+1.A path to r from the vertex d of the cycle H remains in R1.Suppose its length is r2.So the length of the cycle H is r1+r2+1.The length of the cycle H1is not greater than the length of H because the spanning subgraph R has maximal number of edges in its cycles.So r1+r2+1≥L+r1+1,whence r2≥L.If r2>L,then the length r2of the path from d to r in a tree of R1(and the level of d)is greater than L and the level of d(or of some other ancestor of r in a tree from R1)is the desired unique maximal level.

So assume for further consideration L=r2and a∈H.Analogously,for any vertex of maximal level L with root in the cycle H and incoming edge from a vertex a1the proof can be reduced to the case a1∈H and L=r2for the corresponding new value of r2.

2)Suppose the set of outgoing edges of the vertex b is not a bunch.So one can replace in R the edgeˉb from the vertex b by an edgeˉv from b to a vertex v=r.

The vertex v could not belong to T because in this case a new cycle is added to R and therefore a new spanning subgraph has a number of vertices in the cycles greater than in R.

If the vertex v belongs to another tree of R but not to cycle,then T is a part of a new tree T1with a new root of a new spanning subgraph R1and the path from p to the new root is extended.So only the tree T1has states of new maximal level.

If v belongs to some cycle H2=H from R,then together with replacingˉb byˉv,we replace also the edgeˉw byˉa.So we extend the path from p to the new root v at least by the edgeˉa=a→p and by almost all edges of H.Therefore

6

the new maximal level L1>L has either the vertex d or its ancestors from the old spanning subgraph R.

Now there remains only the case when v belongs to the cycle H.The vertex p also has level L in new tree T1with root v.The only di?erence between T and T1(just as between R and R1)is the root and the incoming edge of the root.The new spanning subgraph R1has also a maximal number of vertices in cycles just as R.Let r3be the length of the path from d to the new root v∈H.

For the spanning subgraph R1,one can obtain L=r3just as it was done on the step1)for R.From v=r follows r3=r2,though L=r3and L=r2.

So for further consideration suppose that the set of outgoing edges of the vertex b is a bunch to r.

3)The set of outgoing edges of the vertex c is not a bunch to r because r has another bunch from b.

Let us replace in R the edgeˉc by an edgeˉu=c→u such that u=r. The vertex u could not belong to the tree T because in this case the cycle H is replaced by a cycle with all vertices from H and some vertices of T whence its length is greater than|H|.Therefore the new spanning subgraph has a number of vertices in its cycles greater than in spanning subgraph R in spite of the choice of R.

So remains the case u∈T.Then the tree T is a part of a new tree with a new root and the path from p to the new root is extended at least by a part of H from the former root r.The new level of p therefore is maximal and greater than the level of any vertex in some another tree.

Thus anyway there exists a spanning subgraph with vertices of maximal level in one non-trivial tree.

Theorem3Any AGW graphΓhas a coloring with stable couples.

Proof.By Lemma??,in the case of vertex with two incoming bunchesΓhas a coloring with stable couples.In opposite case,by Lemma??,Γhas a spanning subgraph R such that the vertices of maximal positive level L belong to one tree of R.

Let us give to the edges of R the colorαand denote by C the set of all vertices from the cycles of R.Then let us color the remaining edges ofΓby other colors arbitrarily.

By Lemma??,in a strongly connected graphΓfor every word s and F-clique F of size|F|>1,the set F s also is an F-clique(of the same size by Lemma ??)and for any state p there exists an F-clique F such that p∈F.

In particular,some F has non-empty intersection with the set N of vertices of maximal level L.The set N belongs to one tree,whence by Lemma??this intersection has only one vertex.The wordαL?1maps F on an F-clique F1of size|F|.One has|F1\C|=1because the sequence of edges of colorαfrom any tree of R leads to the root of the tree,the root belongs to a cycle colored byαfrom C and only for the set N with vertices of maximal level holds NαL?1?C. So|NαL?1∩F1|=|F1\C|=1and|C∩F1|=|F1|?1.

Let the integer m be a common multiple of the lengths of all considered cycles from C colored byα.So for any p from C as well as from F1∩C holds pαm=p.

7

Therefore for an F-clique F2=F1αm holds F2?C and C∩F1=F1∩F2.

Thus two F-cliques F1and F2of size|F1|>1have|F1|?1common vertices. So|F1\(F1∩F2)|=1.Consequently,in view of Lemma??,there exists a stable couple in the considered coloring.

Theorem4Every AGW graphΓhas synchronizing coloring.

The proof follows from Theorems??and??.

References

[1]R.L.Adler,L.W.Goodwyn,B.Weiss.Equivalence of topological Markov

shifts,Israel J.of Math.27(1977),49-63.

[2]R.L.Adler,B.Weiss.Similarity of automorphisms of the torus,Memoirs

of the Amer.Math.Soc.,Providence,RI,98(1970).

[3]G.Budzban,A.Mukherjea.A semigroup approach to the Road Coloring

Problem,Probability on Algebraic Structures.Contemporary Mathematics, 261(2000),195-207.

[4]A.Carbone.Cycles of relatively prime length and the road coloring problem,

Israel J.of Math.,123(2001),303-316.

[5]K.Culik II,J.Karhumaki,J.Kari.A note on synchronized automata and

Road Coloring Problem,Developments in Language Theory(5th Int.Conf., Vienna,2001),Lecture Notes in Computer Science,2295(2002),175-185.

[6]J.Friedman.On the road coloring problem,Proc.of the Amer.Math.Soc.

110(1990),1133-1135.

[7]E.Gocka,W.Kirchherr,E.Schmeichel,A note on the road-coloring con-

jecture.Ars Combin.49(1998),265-270.

[8]R.Hegde,K.Jain,Min-Max theorem about the Road Coloring Conjecture

EuroComb2005,DMTCS proc.,AE,2005,279-284.

[9]N.Jonoska,S.Suen.Monocyclic decomposition of graphs and the road col-

oring problem,Congressum numerantium,110(1995),201-209.

[10]J.Kari.Synchronizing?nite automata on Eulerian digraphs,Springer,Lect.

Notes in Comp.Sci.,2136(2001),432-438.

[11]D.Lind,B.Marcus.An Introduction of Symbolic Dynamics and Coding,

Cambridge Univ.Press,1995.

[12]A.Mateescu,A.Salomaa,Many-Valued Truth Functions,ˇCerny’s Conjec-

ture and Road Coloring,Bull.of European Ass.for TCS,68(1999),134-148.

[13]G.L.O’Brien.The road coloring problem,Israel J.of Math.,39(1981),145-

154.

8

[14]D.Perrin,M.P.Schˇu tzenberger.Synchronizing pre?x codes and automata,

and the road coloring problem,In Symbolic Dynamics and Appl.,Contemp.

Math.,135(1992),295-318.

[15]J.E.Pin.On two combinatorial problems arising from automata theory,

Annals of Discrete Math.,17(1983),535-548.

[16]A.N.Trahtman.Notable trends concerning the synchronization of graphs

and automata,CTW06,El.Notes in Discrete Math.,25(2006),173-175.

9