Testing perfection is hard

Details Testing perfection is hard Testing perfection is hard

2011-10-13

arxiv.org/abs/1110.2828v1

Mathematics

Combinatorics

11 pages

Scientific paper

A graph property P is strongly testable if for every fixed \epsilon>0 there is a one-sided \epsilon-tester for P whose query complexity is bounded by a function of \epsilon. In classifying the strongly testable graph properties, the first author and Shapira showed that any hereditary graph property (such as P the family of perfect graphs) is strongly testable. A property is easily testable if it is strongly testable with query complexity bounded by a polynomial function of \epsilon^{-1}, and otherwise it is hard. One of our main results shows that testing perfectness is hard. The proof shows that testing perfectness is at least as hard as testing triangle-freeness, which is hard. On the other hand, we show that induced P_3-freeness is easily testable. This settles one of the two exceptional graphs, the other being C_4 (and its complement), left open in the characterization by the first author and Shapira of graphs H for which induced H-freeness is easily testable.

Affiliated with

Also associated with

No associations

Rating

Testing perfection is hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing perfection is hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing perfection is hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498524