  In 2021, Casares, Colcombet and Fijalkow introduced the Alternating Cycle
Decomposition (ACD), a structure used to define optimal transformations of
Muller into parity automata and to obtain theoretical results about the
possibility of relabelling automata with different acceptance conditions. In
this work, we study the complexity of computing the ACD and its DAG-version,
proving that this can be done in polynomial time for suitable representations
of the acceptance condition of the Muller automaton. As corollaries, we obtain
that we can decide typeness of Muller automata in polynomial time, as well as
the parity index of the languages they recognise.
  Furthermore, we show that we can minimise in polynomial time the number of
colours (resp. Rabin pairs) defining a Muller (resp. Rabin) acceptance
condition, but that these problems become NP-complete when taking into account
the structure of an automaton using such a condition.
