Testing whether a digraph contains H-free k-induced subgraphs
Resource
Theoretical Computer Science 407 (1-3): 545-553
Journal
Theoretical Computer Science
Journal Volume
407
Journal Issue
1-3
Pages
545-553
Date Issued
2008
Author(s)
Abstract
A subgraph induced by k vertices is called a k-induced subgraph. We prove that determining if a digraph G contains H-free k-induced subgraphs is Ω (N2)-evasive. Then we construct an ε{lunate}-tester to test this property. (An ε{lunate}-tester for a property Π is guaranteed to distinguish, with probability at least 2 / 3, between the case of G satisfying Π and the case of G being ε{lunate}-far from satisfying Π.) The query complexity of the ε{lunate}-tester is independent of the size of the input digraph. An (ε{lunate}, δ)-tester for a property Π is an ε{lunate}-tester for Π that is furthermore guaranteed to accept with probability at least 2 / 3 any input that is δ-close to satisfying Π. This paper presents an (ε{lunate}, δ)-tester for whether a digraph contains H-free k-induced subgraphs. © 2008 Elsevier B.V. All rights reserved.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
20.pdf
Size
696.71 KB
Format
Adobe PDF
Checksum
(MD5):53a577ed80fa6e89898a4b9632db0da8