ALBCOM Seminar: Parameterized Testability


Sep 13, 2012 from 12:00 PM to 01:00 PM (Europe/Madrid / UTC200)


Room S208 (floor -2), Omega Building, UPC, Barcelona


This talk forms part of the Seminar on Algorithms and Programming of the Master in Computing.

Add event to calendar


Speaker: Kazuo Iwama (Kyoto University)

Abstract: In graph property testing, given a graph represented by an oracle, we want to test whether the graph satisfies some predetermined property P  or \epsilon-far from satisfying the property.  Roughly speaking, a
graph is called \epsilon-far from a property if we need to modify an \epsilon-fraction of the graph to make it satisfy the property.  A most important focus in this topic has been on general characterizations for (constant-time) testable properties, which have  obtained much progress in the last decade: For the dense graph model,
Alon et al. finally obtained a purely combinatorial necessary and  sufficient condition for P to be testable that is closely related to  the Szemer\'edi Regularity Lemma.  For the bounded-degree graph model, due to Benjamini et al., any property is testable if it is  minor-closed.

In this talk, we are still interested in a general framework of  testable properties, but our approach is a bit different from the  qualitative one as above.  Rather, we are interested in "parameterized  properties'' that are quite common in NP optimization problems.  A bit curiously, this direction has not been so popular in the context of property testing.  The obvious reason is that the problem becomes less interesting in both the dense graph model and the bounded degree model.  For instance, consider the problem k-Vertex Cover for a constant k.  In the dense graph model, we want to decide whether a graph has a vertex cover of size at most k or we need to remove at least \epsilon \times n^2 edges to have the property.  It turns out that this property is easily testable just by accepting only graphs with at most \epsilon \times n^2 edges.

To avoid this triviality, we consider the general graph model with an  augmentation of random edge sampling capability.  It is shown that a variety of such problems, including k-Vertex Cover, k-Feedback Vertex
Set, k-Multicut, k-Path Free and k-Dominating Set, are constant-time testable if k is constant.  It should be noted that the first four problems are fixed parameter tractable (FPT) and it turns out that algorithmic techniques for their FPT algorithms (bounded-branching tree search, color coding, etc.) are also useful for our testers. k-Dominating Set is W[2]-hard, but we can still test the property in constant time since the definition of \epsilon-farness makes the problem trivial for non-sparse graphs that are the source of hardness for the original optimizat