License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.53
URN: urn:nbn:de:0030-drops-94572
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9457/
Go to the corresponding LIPIcs Volume Portal

Nakar, Yonatan ; Ron, Dana

On the Testability of Graph Partition Properties

pdf-format:
LIPIcs-APPROX-RANDOM-2018-53.pdf (0.5 MB)

Abstract

In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998 ). While the family studied by Goldreich, Goldwasser, and Ron includes a variety of natural properties, such as k-colorability and containing a large cut, it does not include other properties of interest, such as split graphs, and more generally (p,q)-colorable graphs. The generalization we consider allows us to impose constraints on the edge-densities within and between parts (relative to the sizes of the parts). We denote the family studied in this work by GPP.
We first show that all properties in GPP have a testing algorithm whose query complexity is polynomial in 1/epsilon, where epsilon is the given proximity parameter (and there is no dependence on the size of the graph). As the testing algorithm has two-sided error, we next address the question of which properties in GPP can be tested with one-sided error and query complexity polynomial in 1/epsilon. We answer this question by establishing a characterization result. Namely, we define a subfamily GPP_{0,1} of GPP and show that a property P in GPP is testable by a one-sided error algorithm that has query complexity poly(1/epsilon) if and only if P in GPP_{0,1}.

BibTeX - Entry

@InProceedings{nakar_et_al:LIPIcs:2018:9457,
  author =	{Yonatan Nakar and Dana Ron},
  title =	{{On the Testability of Graph Partition Properties}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9457},
  URN =		{urn:nbn:de:0030-drops-94572},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.53},
  annote =	{Keywords: Graph Partition Properties}
}

Keywords: Graph Partition Properties
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI