Some of the readers might not be aware of an intuitive way of understanding the concept of treewidths that is provided by the cops-and-robber games, as pointed out by Seymour and Thomas in their paper "Graph searching and a min-max theorem for treewidth", Journal of Combinatorial Theory B, Vol. 58 (1993). The following presentation follows the second paper cited at the bottom. The k-cops-and-robber games, where k > 1, takes a graph G = (V,E) as a parameter. Each game has two players: the cops and the robber. The game goes as follows:
- In round 0, the cops choose a subset X0 of V of size at most k. The robber chooses a vertex v0 of V - X0.
- In round i+1, the cops choose a subset Xi+1 of V of size at most k. If possible, the robber chooses a vertex vi+1 of V - Xi+1 such that there is a (possibly empty) path from vi to vi+1 which does not pass through Xi ∩ Xi+1. Otherwise, the cops win the game right there.
If this game has no end (i.e. the robber can evade capture), then the robber wins. The cops are said to have a winning strategy on the k-cops-and-robber game on G if they can play in such a way that they will eventually win the game. Otherwise, we say that the robber has a winning strategy on this game.
It is helpful to think of the set Xi+1 - Xi as set of vertices above which the cops are hovering in helicopters in round i+1. [This tells us that cops can move from vertices to vertices unrestrictedly.] Also, the set Xi+1 ∩ Xi can be thought of as the vertices where the cops have landed from helicopters. So, it takes two moves for a cop to be at a particular vertex v (i.e. on the ground): she must first ride a helicopter to v, and second land the helicopter at v. On the other hand, a cop may take off to another vertex (but still is in a helicopter) in just one move. In addition, the robber can see the cops in the helicopter, and may elude capture by running at great speed to another vertex as long as he does not run through a cop on the ground during his escape.
Theorem (Seymour and Thomas): A graph G has treewidth ≤ k-1 iff the cops have a winning strategy in the k-cops-and-robber game on G.
Equivalently, a graph G has treewidth k-1 iff k is the smallest number k' such that the cops have a winning strategy in the k'-cops-and-robber game on G. Let's try this game on a tree. The cops can win the game using 2 cops only. The idea is to gradually shrink the set of vertices the robber can go to in the next round by alternately moving the two cops in a "depth-first traversal" manner. On the other hand, it is clear that the robber player has a winning strategy on a tree if he is chased by only a poor lone cop.
In recent years, some researchers in databases and verification have proposed variants of the cops-and-robber games so as to explain some phenomena in those fields. Let me conclude by mentioning two such papers:
- Gottlob, Leone, and Scarcello. Robbers, marshals, and guards: game theoretic and logical characterization of hypertree width, JCSS 66, 2003.
- Berwanger, Dawar, Hunter, and Kreutzer. DAG-width and Parity Games, STACS 2006.
7 comments:
This is a really interesting note. I never heard of this characterization.
Thank you!
Maverick Woo
Second that.
A while ago I looked at this type of game, but with cops on the ground. It's interesting to think about computing k for simple structures like grids, and to wonder whether robber speed matters.
I wonder if you could try to summarize in your experience why treewidth is important for CS.
My exposure to the concept tells me that one can often take a self-reducible graph theory (or graph-theory-like) problem, exhaustively expand the self-reduction until it hits tree-cases of the problem, then solve these efficiently; if the treewidth is bounded the expansion won't be too huge.
Is this a superficial understanding of treewidth's importance?
Thanks!
There are many equivalent formulations of cops and robber games. For example, the one that Seymour and Thomas use in their paper requires the robber to choose a connected component instead of a vertex. It will be great if you can specify the version of this game that you looked at.
Why is the notion of treewidth is important in CS? If you've done a bit of algorithms and complexity, you notice that proving your problem is NP-complete does not make the problem go away. Many NP-complete problems are very practical, and it's extremely important to come up with "good" algorithms for them. One approach is to restrict the problem instances under consideration (e.g. rather than consider the class of all graphs, we consider the class of all trees). As many algorithmists argue, most graphs that we look at in practice have small treewidths. Therefore, it suffices to come up with an algorithm for the problem with complexity f(k)n^c where f: N -> N is an increasing function that "does not go very fast", k is the treewidth of the input graph, n is the size of the graph, and c is a constant natural number independent of k and n. For example, f(k) = 2^k is tolerable. Many intractable graph problems become tractable when we restrict ourselves to graphs of bounded treewidth.
Another reason why treewidth is important in CS is Courcelle's theorem that says: if your graph problem is MSO-definable, then it can be solved in time f(k)n, where k and n are defined as above.
I hope this convinces you of the importance of treewidth in CS.
Furthering the previous comment, many algorithms in statistics (statistical physics, machine learning, etc.) scale naturally with the treewidth of the underlying Markov field (viewed as a graph). Many natural problems can be expressed as graphs with small treewidths.
Hal, I've heard of this before, but I never understood it. Could you please give me a reference to back up your claim here? Thanks.
Anthony
Sorry for not replying earlier. Lost of papers talk about it...a reasonable reference is here.
Rather amusing piece
Post a Comment