Czumaj, Artur, Peng, Pan and Sohler, Christian (2016) Relating two property testing models for bounded degree directed graphs. In: 48th Annual ACM Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 19-21 Jun 2016. Published in: STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing pp. 1033-1045. ISBN 9781450341325. doi:10.1145/2897518.2897575

	PDF WRAP_p1033-czumaj.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (769Kb)
	PDF WRAP_0583063-cs-090516-directed-v6.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (410Kb)

Request Changes to record.

Abstract

We study property testing algorithms in directed graphs (digraphs) with maximum indegree and maximum outdegree upper bounded by d. For directed graphs with bounded degree, there are two different models in property testing introduced by Bender and Ron (2002). In the bidirectional model, one can access both incoming and outgoing edges while in the unidirectional model one can only access outgoing edges. In our paper we provide a new relation between the two models: we prove that if a property can be tested with constant query complexity in the bidirectional model, then it can be tested with sublinear query complexity in the unidirectional model. A corollary of this result is that in the unidirectional model (the model allowing only queries to the outgoing neighbors), every property in hyperfinite digraphs is testable with sublinear query complexity.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Directed graphs
Journal or Publication Title:	STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
Publisher:	ACM
ISBN:	9781450341325
Official Date:	18 March 2016
Dates:	Date Event 18 March 2016 Accepted
Page Range:	pp. 1033-1045
DOI:	10.1145/2897518.2897575
Status:	Peer Reviewed
Publication Status:	Published
Date of first compliant deposit:	24 August 2016
Date of first compliant Open Access:	24 August 2016
Funder:	University of Warwick. Centre for Discrete Mathematics and Its Applications, Engineering and Physical Sciences Research Council (EPSRC), European Research Council (ERC)
Grant number:	EP/J021814/1 (EPSRC), Grant No. 307696 (ERC)
Conference Paper Type:	Paper
Title of Event:	48th Annual ACM Symposium on Theory of Computing (STOC 2016)
Type of Event:	Conference
Location of Event:	Cambridge, MA
Date(s) of Event:	19-21 Jun 2016
Related URLs:	Publisher Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads