Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Complexity of Road Coloring with Prescribed Reset Words   By the Road Coloring Theorem (Trahtman, 2008), the edges of any aperiodic
directed multigraph with a constant out-degree can be colored such that the
resulting automaton admits a reset word. There may also be a need for a
particular reset word to be admitted. For certain words it is NP-complete to
decide whether there is a suitable coloring of a given multigraph. We present a
classification of all words over the binary alphabet that separates such words
from those that make the problem solvable in polynomial time. We show that the
classification becomes different if we consider only strongly connected
multigraphs. In this restricted setting the classification remains incomplete.

19
The categories of this paper are: eess
14
The categories of this paper are: math-ph
5
The categories of this paper are: gr-qc
4
The categories of this paper are: cond-mat
10
The categories of this paper are: q-bio
17
The categories of this paper are: q-fin
21
The categories of this paper are: adap-org
27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th
3
The categories of this paper are: physics
22
The categories of this paper are: chao-dyn
34
The categories of this paper are: chem-ph
6
The categories of this paper are: astro-ph
24
The categories of this paper are: dg-ga
32
The categories of this paper are: atom-ph
25
The categories of this paper are: patt-sol