Directed multigraphs as minimal automata

Question

Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by forgetting labels of transitions, final states). We keep the initial state because every vertex must be accessible from it.

Is the converse true ? I.e. given a directed connected multigraph $G$ with constant out-degree and initial state such that every vertex is accessible from it, is there always a language $L$ such that $G$ is the underlying graph of the minimal automaton of $L$ ?

For instance if $|A|=1$ it's true, since the graph must be a "lasso" with a prefix of size $i$ and a loop of size $j$, and corresponds to the minimal automaton of $L=\{a^{i+nj}~|~n\in\mathbb N\}$.

The motivation comes from a related problem encountered in a decidability reduction, where the solution is easier : starting from a non-oriented simple graph, and with more operations allowed like adding sinks. But I was wondering if someone had already looked at this more natural question ?

The only things remotely connected I could find in the literature are papers like Complexity of Road Coloring with Prescribed Reset Words, where the goal is to color such a multigraph so that the resulting automaton has a synchronizing word. However minimality does not seem to be considered.

Update: Follow-up question after the answer of Klaus Draeger: what is the complexity of deciding whether a graph is of this shape ? We can guess the labeling and polynomially verify minimality of the automaton, so it is in NP, but can we say more ?

Answer 1

Any absorbing node $n$ will have to be either accepting or not (so that either everything or nothing is accepted once $n$ is entered). If the graph has more than two absorbing nodes, then some of them will end up equivalent for any choice of labeling and accepting set.

More generally, for any strongly connected graph $H$ there is only a finite number $n(H)$ of different possible labelings and accepting subsets; if your graph has more than $n(H)$ terminal strongly connected components equivalent to $H$ (attached at the leaves of a tree, say), it cannot correspond to any minimal automaton.

EDIT, regarding the follow-up question: This sounds tricky. One approach suggested by my argument might look like this:

• Partition $G$ into SCCs. This is cheap; $O(|V|+|E|)$ using Tarjan's algorithm.
• Sort the SCCs into isomorphism classes. Unfortunately graph isomorphism is not known to be in $P$.
• For each terminal isomorphism class, determine the number of permissible corresponding sub-automata, and fail if there are not enough of them. Note that not every combination of accepting subset and edge labeling is permissible: for example, suppose our alphabet is $\{a,b\}$, and a component has two nodes, each with a self-loop and an edge to the other node. Making both nodes accepting and labeling both loops with $a$ (and the other edges with $b$) gives an automaton which is bisimilar to a single absorbing state, violating minimality.
• Treat the remaining SCCs in the DAG similarly, taking into account the lower ones; I'm a bit fuzzy on the details of this part.

That is one step whose complexity is famously open, and another one which looks like it may require exponential time (since there may be exponentially many partitions into bisimilarity classes to be excluded when determining permissible automata). Can we do better?