PaperlayerView exact revision on arXiv

Source-linked AI summary

The road coloring problem

A. N. Trahtman

arXiv:0709.0099v4cs.DM

TL;DR

The road coloring problem asks whether a strongly connected directed graph with constant outdegree and cycle-length gcd one can be colored to yield a synchronizing automaton. The paper proves such a coloring exists for these graphs, constructing colorings with stable couples using a spanning subgraph of cycles and trees.

  • Problem

    The road coloring problem asks for a synchronizing edge coloring of a strongly connected directed graph with constant outdegree and cycle-length gcd one.

    Source: Introduction · p. 1

  • Method

    The paper constructs colorings with stable couples using a spanning subgraph of cycles and trees, then derives synchronizing colorings.

    Source: §2 · pp. 5, 7, 8

  • Results

    Every AGW graph has a synchronizing coloring, giving a positive solution to the road coloring problem.

    Source: Introduction · p. 2, §2 · p. 8

  • Takeaways & Limitations

    For finite strongly connected directed graphs with constant outdegree and cycle-length gcd one, the road coloring problem has a positive solution.

    Source: Introduction · p. 2

    The treatment concerns AGW graphs and excludes primitive cases with loops or only one color.

    Source: Introduction · p. 1, §1 · p. 3

Abstract

from arXiv · show

The synchronizing word of deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into deterministic finite automaton possessing a synchronizing word. The road coloring problem is a problem of synchronizing coloring of directed finite 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 over 30 years ago and evoked a noticeable interest among the specialists in theory of graphs, deterministic automata and symbolic dynamics. The problem is described even in "Wikipedia" - the popular Internet Encyclopedia. The positive solution of the road coloring problem is presented.

Introduction

The road coloring problem asks whether an unlabeled, strongly connected directed graph with constant outdegree and cycle-length gcd one can be edge-labeled to yield a synchronizing automaton. The paper proves that such a synchronizing coloring exists.

Introduction

  • The problem is to label the edges of a strongly connected directed graph with constant outdegree so its automaton has a synchronizing word.The graph must have cycle-length gcd one; the edges are initially unlabeled.Source: Introduction · p. 1
  • Cycle-length gcd one is necessary and is equivalent to the absence of a cyclic partition of the vertices respected by every edge.In such a partition, edges from each subset end in the next subset, cyclically.Source: Introduction · p. 1
  • A synchronizing word can reset an automaton to its original state after an input error.The problem also arose in symbolic dynamics.Source: Introduction · pp. 1–2
  • The paper proves a positive solution: every finite strongly connected directed graph with constant outdegree and cycle-length gcd one has a synchronizing coloring.The problem had been regarded as a notorious open problem and unfeasible,.Source: Introduction · p. 2

Preliminaries

The preliminaries define the graph class, state and subset notation, and concepts used to describe synchronization and the proof’s weight-based structure.

Preliminaries

  • An AGW graph is a finite strongly connected directed graph with constant outdegree and cycle-length gcd one.The name refers to Adler, Goodwyn and Weiss.Source: Preliminaries · p. 2
  • Bold letters denote graph vertices and automaton states; p s denotes the state reached from p by the word s.P s is the image of a state set P under s, while P s−1 is the largest set Q satisfying Qs ⊆ P.Source: Preliminaries · p. 2
  • A synchronizing word maps the automaton’s full state set to one state, and a synchronizing coloring makes the graph’s automaton possess such a word.The size of a state set P is denoted |P|.Source: Preliminaries · p. 2
  • A synchronizing pair merges under some word, whereas a deadlock pair never merges; a stable pair remains synchronizing after every word.A bunch is a vertex’s set of outgoing edges when all lead to one vertex.Source: Preliminaries · p. 2
  • Vertex weights come from a positive integer left eigenvector of the adjacency matrix, and an F-maximal set has maximal weight and is mapped to a singleton by some word.An F-clique is an image of the full state set whose distinct states are pairwise deadlocks.Source: Preliminaries · p. 3

1 Some properties of F-clique and of coloring free of stable pairs

This section develops properties of F-cliques and stable pairs for AGW graphs, establishing size and closure facts used in the proof. It also shows that two incoming bunches force a stable pair under every coloring.

1 Some properties of F-clique and of coloring free of stable pairs

  • The section assumes AGW graphs and excludes primitive cases with loops or only one color.It invokes prior results that the F-maximal sets partition the graph and that the stability relation is a congruence whose quotient is an AGW graph; synchronizing the quotient implies a synchronizing recoloring.Source: §1 · p. 3
  • Every F-clique has size w(Γ)/w, equal to the number of equal-weight F-maximal sets in the partition of Γ.The proof bounds the clique by allowing at most one of its states in each partition set, then uses the total weight of preimage sets to obtain equality.Source: §1 · p. 3
  • For any word s, Fs is an F-clique, and every state belongs to some F-clique.Deadlock pairs remain deadlocks under a word, and strong connectivity lets each state be reached from a state in F.Source: §1 · p. 4
  • Distinct F-cliques of size greater than one cannot differ by exactly one state on each side.Assuming one nonshared state on each side yields an image set larger than a clique, contradicting the partition into F-maximal sets.Source: §1 · p. 4
  • If a vertex has two incoming bunches, their source vertices form a stable pair under any coloring.Both sources transition to the same vertex on every letter.Source: §1 · p. 4

2 The spanning subgraph of cycles and trees with maximal number of edges in the cycles

The section builds a spanning-subgraph structure for AGW graphs, then uses a stable-couple coloring to obtain a synchronizing coloring.

  • A spanning subgraph contains every vertex and one outgoing edge per vertex, forming disjoint cycles and trees whose levels measure distance to a cycle root.Source: §2 · pp. 4–5
  • When a spanning subgraph consists only of cycles, another spanning subgraph can be found with exactly one vertex of maximal positive level.Source: §2 · p. 5
  • If no vertex has two incoming bunches, a spanning subgraph exists whose vertices of maximal positive level lie in one non-trivial tree.Source: §2 · p. 5
  • If a vertex has two incoming bunches, any coloring has a stable couple; otherwise, the proof uses the spanning subgraph from Lemma 7.Source: §2 · pp. 5, 7
  • Coloring the spanning-subgraph edges α and the others arbitrarily lets the proof use F-clique overlap to obtain a stable couple.A power of α maps an F-clique to one meeting the cycle vertices in all but one state; a common multiple of cycle lengths preserves those cycle states.Source: §2 · pp. 7–8
  • Every AGW graph has a synchronizing coloring, following from a coloring with stable couples and the stable-pair criterion.Source: §2 · pp. 7–8
Loading 0709.0099v4…