Undirected Graphs of Entanglement Two

Entanglement is a complexity measure of finite directed graphs whose purpose is to quantify to what extent cycles are intertwined. It has been introduced in [2, 1] to analyze the variable hierarchy of the Propositional Modal µ-calculus [4]. A main achievement of [2] states that parity games whose underlying graphs have bounded entanglement can be solved in polynomial time. This result calls for the problem of deciding whether a graph has entanglement at most k, a problem which we address. As a matter of fact, if we have an efficient algorithm for this problem then we can pair it with Berwanger’s algorithm to solve parity games efficiently: if the entanglement of the game is small then Berwanger’s algorithm is used to solve it, otherwise a standard exponential algorithm is used. Game theoretic ideas naturally lead to design polynomial algorithms that, for fixed k, decide the problem. If k is not fixed then we can combine these algorithms to show that the problem is in EXPTIME. We have no reasons to state that it is in NP. As we have mentioned above, for fixed k, the problem is in P, known characteriza-tions of directed graphs of entanglement at most 1, see [2], lead, for k = 1, to design even faster algorithms. In this talk,??, we shall provide structural characterizations o