|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-Reports 2015 | Copyright 2015 University of Bonn, Department of Computer Science, Abt. V | |
|
85356 25.03.2015 |
On the Complexity of Nondeterministically Testable Hypergraph Parameters
Marek Karpinski and Roland Marko [Download PostScript] [Download PDF] The paper proves the equivalence of the notions of nondeterministic and deterministic parameter testing for uniform dense hypergraphs of arbitrary order. It generalizes the result previously known only for the case of simple graphs. By a similar method we establish also the equivalence between nondeterministic and deterministic hypergraph property testing, answering the open problem in the area. We introduce a new notion of a cut norm for hypergraphs of higher order, and employ regularity techniques combined with the ultralimit method. |
|
|
Last Change:
03/25/15 at 08:27:58
|
University of Bonn -> Department of Computer Science -> Chair V | |