Evasiveness of Graph Properties and Topological Fixed-Point Theorems
By Carl A. Miller, University of Michigan, Department of Electrical Engineering and Computer Science, USA, carlmi@umich.edu
Abstract
Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the number of edges in the graph that it queries. R. Karp conjectured in the early 1970s that all monotone graph properties are evasive—that is, any algorithm which computes a monotone graph property must check all edges in the worst case. This conjecture is unproven, but a lot of progress has been made. Starting with the work of Kahn, Saks, and Sturtevant in 1984, topological methods have been applied to prove partial results on the Karp conjecture. This text is a tutorial on these topological methods. I give a fully self-contained account of the central proofs from the paper of Kahn, Saks, and Sturtevant, with no prior knowledge of topology assumed. I also briefly survey some of the more recent results on evasiveness.
Evasiveness of Graph Properties and Topological Fixed-Point Theorems
Evasiveness of Graph Properties and Topological Fixed-Point Theorems addresses a fascinating topic that lies at the interface between mathematics and theoretical computer science. There have been several interesting research papers that use topological methods to prove lower bounds on the complexity of graph properties. The goal of this text is to offer an integrated version of the underlying proofs in this body of research. While there are a number of very good expositions available on topological methods in decision-tree complexity, they all refer to other sources for the proofs of some topological results. This work is the first that provides a completely self-contained account. Evasiveness of Graph Properties and Topological Fixed-Point Theorems begins by laying out the important foundational material and builds up to the more complex results at a steady pace. The capstone results, which consist of three lower bounds on the complexity of graph properties, appear in the final part of the text. The reader is not assumed to have any prior background in algebraic topology as all constructions from that subject are developed from scratch. The only prerequisite is a high level of comfort with discrete mathematics and linear algebra.
