Publication Date:
2014-02-26
Description:
A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or $k$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness.
Keywords:
ddc:000
Language:
English
Type:
reportzib
,
doc-type:preprint
Format:
application/postscript
Format:
application/pdf
Permalink