Technical reports

Complexity and infinite games on finite graphs

Paul William Hunter

November 2007, 170 pages

This technical report is based on a dissertation submitted July 2007 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Hughes Hall.

DOI: 10.48456/tr-704

Abstract

This dissertation investigates the interplay between complexity, infinite games, and finite graphs. We present a general framework for considering two-player games on finite graphs which may have an infinite number of moves and we consider the computational complexity of important related problems. Such games are becoming increasingly important in the field of theoretical computer science, particularly as a tool for formal verification of non-terminating systems. The framework introduced enables us to simultaneously consider problems on many types of games easily, and this is demonstrated by establishing previously unknown complexity bounds on several types of games.

We also present a general framework which uses infinite games to define notions of structural complexity for directed graphs. Many important graph parameters, from both a graph theoretic and algorithmic perspective, can be defined in this system. By considering natural generalizations of these games to directed graphs, we obtain a novel feature of digraph complexity: directed connectivity. We show that directed connectivity is an algorithmically important measure of complexity by showing that when it is limited, many intractable problems can be efficiently solved. Whether it is structurally an important measure is yet to be seen, however this dissertation makes a preliminary investigation in this direction.

We conclude that infinite games on finite graphs play an important role in the area of complexity in theoretical computer science.

Full text

PDF (1.5 MB)

BibTeX record

@TechReport{UCAM-CL-TR-704,
  author =	 {Hunter, Paul William},
  title = 	 {{Complexity and infinite games on finite graphs}},
  year = 	 2007,
  month = 	 nov,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-704.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-704},
  number = 	 {UCAM-CL-TR-704}
}