Observability Properties of Colored Graphs
  A colored graph is a directed graph in which nodes or edges have been
assigned colors that are not necessarily unique. Observability problems in such
graphs consider whether an agent observing the colors of edges or nodes
traversed on a path in the graph can determine which node they are at currently
or which nodes were visited earlier in the traversal. Previous research efforts
have identified several different notions of observability as well as the
associated properties of graphs for which those observability properties hold.
This paper unifies the prior work into a common framework with several new
results about relationships between those notions and associated graph
properties. The new framework provides an intuitive way to reason about the
attainable accuracy as a function of lag and time spent observing, and
identifies simple modifications to improve the observability of a given graph.
We show that one form of the graph modification problem is in NP-Complete. The
intuition of the new framework is borne out with numerical experiments. This
work has implications for problems that can be described in terms of an agent
traversing a colored graph, including the reconstruction of hidden states in a
hidden Markov model (HMM).
