The Angel Problem, Positional Games, and Digraph Roots: Strategies and Complexity

Abstract

This thesis is about combinatorial games -- mostly. It is also about graphs, directed graphs and hypergraphs, to a large extent; and it deals with the complexity of certain computational problems from these two areas. We study three different problems that share several of the above aspects, yet, they form three individual subjects and so we treat them independently in three self-contained chapters:

The angel-devil game On an infinite chess board, the angel, a chess person who jumps from square to square, tries to escape his opponent, the devil, who intends to strand him by placing obstacles on the board. The open question is, whether some angel who is allowed to make sufficiently large but bounded steps in each move, will be able to escape forever. We attack this problem from the devil's perspective, trying to improve upon the known result that the ordinary chess king cannot escape. A reformulation of the game which focuses on the angel's speed as the crucial quantity, allows us to show that certain faster "chess kings" can still be trapped. A second part of this chapter deals with angels on a three dimensional board. We show that the new dimension grants the angel enough freedom to escape forever.

Weak positional games on hypergraphs The games in the second chapter are very general versions of the well-known game of Tic-Tac-Toe. Two players alternately claim vertices of a hypergraph, the first player trying to get all vertices within some edge, his opponent striving to prevent this from happening. Such weak positional games are known to be PSPACE-complete, but the respective hardness result utilizes edges of size up to 11. We analyze the restricted class of hypergraphs whose edges contain no more than three vertices each, trying to find optimal strategies for both players. We almost succeed. Under the further restriction that any two edges may intersect in at most one vertex, we obtain a classification of such hypergraphs into those that yield a first player win and those who don't, which immediately leads to efficiently computable optimal strategies for either player.

The complexity of digraph root computation Multiplication of square Boolean matrices, if interpreted as adjacency matrices of directed graphs, induces a notion of powers for digraphs. We show that computing roots of Boolean matrices or, equivalently, of directed graphs is NP-hard. Moreover, we discover a relation between digraph roots and graph isomorphism which materializes in form of an isomorphism-completeness result: For a special class of digraphs defined through arc subdivisions, root finding is of the same complexity as deciding whether two digraphs are isomorphic.

In dieser Dissertation betrachten wir neue Strategien für ein unendliches kombinatorisches Spiel, untersuchen die Komplexität einer Klasse von Spielen auf Hypergraphen und beantworten eine offene Frage zu einem Berechnungsproblem auf gerichteten Graphen. Obwohl gewisse Verbindungen zwischen den behandelten Gebieten bzw. den prinzipiellen Fragestellungen bestehen, handelt es sich um drei unabhängige Themen.

Das Engel-Problem Auf einem unendlichen Schachbrett versucht der Engel, eine "Schachfigur" mit beschränkter Schrittweite, seinem Gegner, dem Teufel, unendlich lange davonzulaufen. Der Teufel blockiert Zug um Zug Felder des Brettes mit der Absicht, den Engel einzukreisen. Es ist ein offenes Problem, ob ein Engel mit hinreichend großer Schrittweite gewinnen kann. Wir verbessern eine bekannte Teufel-Strategie und zeigen außerdem, dass der Engel auf einem dreidimensionalen Brett entkommt.

Positionelle Spiele auf Hypergraphen Zwei Spieler wählen abwechselnd Ecken eines Hypergraphen bis alle Ecken vergeben sind. Der Anziehende gewinnt, wenn es ihm gelingt, eine Kante des Hypergraphen zu vervollständigen, andernfalls siegt sein Gegner. Diese asymmetrische Verallgemeinerung des bekannten Spiels Tic-Tac-Toe wird als schwaches positionelles Spiel bezeichnet und ist PSPACE-vollständig. Der entsprechende Härtebeweis verwendet Kanten mit bis zu 11 Ecken. Wir versuchen Spiele auf Hypergraphen mit nicht mehr als drei Ecken pro Kante vollständig zu lösen. Dies gelingt uns fast, mit der zusätzlichen Einschränkung, dass sich je zwei Kanten in höchstens einer Ecke treffen dürfen. Mittels einer vollständigen Klassifizierung in Gewinner und Verlierer erhalten wir einen Polynomialzeit-Algorithmus, der solche Spiele optimal spielt.

Wurzeln gerichteter Graphen Interpretiert man eine quadratische Boolesche 0/1-Matrix als Adjazenzmatrix eines gerichteten Graphen, so induziert die Matrixmultiplikation auf natürliche Weise eine Potenzoperation auf gerichteten Graphen. Wir zeigen, dass in diesem Sinne das Berechnen von Wurzeln gerichteter Graphen NP- vollständig ist. In einem zweiten Teil stellen wir eine Beziehung zwischen solchen Wurzeln und Graphisomorphie her und zeigen, dass für eine spezielle Klasse von gerichteten Graphen das Wurzelproblem von derselben Komplexität ist wie das Isomorphie-Problem für Graphen.