Foundations and Trends® in Theoretical Computer Science > Vol 7 > Issue 4

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

 
Suggested Citation
Carl A. Miller (2013), "Evasiveness of Graph Properties and Topological Fixed-Point Theorems", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 7: No. 4, pp 337-415. http://dx.doi.org/10.1561/0400000055

Publication Date: 16 May 2013
© 2013 C. A. Miller
 
Subjects
Computational aspects of combinatorics and graph theory,  Computational complexity,  Computational Models and Complexity
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction 
2. Basic Concepts 
3. Chain Complexes 
4. Fixed-Point Theorems 
5. Results on Decision-Tree Complexity 
A. Appendix 
Acknowledgments 
References 

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.

DOI:10.1561/0400000055
ISBN: 978-1-60198-664-1
81 pp. $70.00
Buy book (pb)
 
ISBN: 978-1-60198-665-8
81 pp. $115.00
Buy E-book (.pdf)
Table of contents:
Preface
1. Introduction
2. Basic Concepts
3. Chain Complexes
4. Fixed-point theorems
5. Results on Decision-Tree Complexity
A. Appendix
Acknowledgements
References

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.

 
TCS-055