Evasiveness of Graph Properties and Topological Fixed-Point Theorems

DOI10.1561/0400000055zbMath1278.68019arXiv1306.0110OpenAlexW2146135269MaRDI QIDQ2872493

Carl A. Miller

Publication date: 15 January 2014

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.0110

zbMATH Keywords

connectednesstopological methodsgraph propertiesmonotone graph propertiesevasivecontaining a complete subgraphKarp conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Fixed-point and coincidence theorems (topological aspects) (54H25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness], Counting Small Induced Subgraphs Satisfying Monotone Properties, Elusiveness of finding degrees, Using Brouwer’s Fixed Point Theorem, Unnamed Item, Elusiveness of Finding Degrees, Unnamed Item, Counting induced subgraphs: a topological approach to \#W[1-hardness]