Complexity Measures for Directed Graphs as Graph Searching Games


Roman Rabinovich, I7

Title Complexity Measures for Directed Graphs as Graph Searching Games
When 22.04.2010
Where Lecture Room Informatik 11
Abstract Many difficult problems, e.g., NP-complete, need to be solved in applications. Often , they are even solved “efficiently”: the running time of algorithms is not too bad. The reason for that is that most often only easy-to-handles simple instances are given as input. To distinguish between simple and complex input structures complexity measures on them are defined. For undirected graphs, the standard measure is tree-width, that has a well-studied theory and is used to construct efficient algorithms for difficult problems on simple graphs.

Complexity measures for directed graphs is currently a topic of active research. One of them is entanglement, a measure that has its roots in studying the expressive power of $\mu$-calculus. We present the general idea behind complexity measures that can be defined via graph searching games – an intuitive tool for complexity analysis of graphs. Further, we present our result about entanglement, in that we give a structural characterisation of the measure on a class of graphs.

Slides download