In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, entanglement of a
directed graph is a number measuring how strongly
the cycles of the graph are intertwined. It is defined in terms of a
mathematical game in which
''n'' cops try to capture a robber, who escapes along the edges of the graph. Similar to other
graph measures, such as
cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a
digraph is to a directed acyclic graph (DAG), in the sense that a DAG has
...
, some algorithmic problems, e.g.
parity game, can be
efficiently solved on graphs of bounded entanglement.
Definition
The entanglement game
[D. Berwanger and E. Grädel]
Entanglement – A Measure for the Complexity of Directed Graphs with Applications to Logic and Games
Proceedings of LPAR'04, vol. 3452 of LNCS, pp. 209–223 (2004) is played by ''n'' cops against a robber on
a directed graph ''G''. Initially, all cops are outside the graph and the robber selects an arbitrary starting vertex
''v'' of ''G''. Further on, the players move in turn. In each move the cops either stay where they are, or place one
of them on the vertex currently occupied by the robber. The robber must move from her current vertex, along an edge,
to a successor that is not occupied by a cop. The robber must move if no cop is following him. If there is
no free successor to which the robber can move, she is caught, and the cops win. The robber wins if she
cannot be caught, i.e. if the play can be made to last forever.
A graph ''G'' has entanglement ''n'' if ''n'' cops win in the entanglement game on ''G'' but ''n'' − 1 cops lose the game.
Properties and applications
Graphs of entanglement zero and one can be characterized as follows:
[
* entanglement of ''G'' is 0 if and only if ''G'' is acyclic
* entanglement of ''G'' is 1 if and only if ''G'' is not acyclic, and in every ]strongly connected component
In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...
of ''G'' there is a node whose removal makes the component acyclic.
Entanglement has also been a key notion in proving that the variable hierarchy
of the modal mu calculus is strict.[D. Berwanger, E. Grädel and G. Lenzi]
The variable hierarchy of the mu-calculus is strict
Theory of Computing Systems, vol. 40, pp. 437–466 (2007)
References
{{Reflist
External links
You can play the entanglement game online o
Graph invariants