Evasiveness of Subgraph Containment and Related Properties

DOI10.1137/S0097539700382005zbMath1051.68071WikidataQ56701654 ScholiaQ56701654MaRDI QIDQ2784484

Amit Chakrabarti, Subhash A. Khot, Yaoyun Shi

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

evasivenesstopological methoddecision tree complexitymonotone graph propertiesgraph property testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Query complexity of tournament solutions ⋮ Unnamed Item ⋮ An asymptotic bound for the complexity of monotone graph properties ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Any monotone property of 3-uniform hypergraphs is weakly evasive

This page was built for publication: Evasiveness of Subgraph Containment and Related Properties