ALBCOM Seminar: Parameterized Testability
- https://computing.phd.upc.edu/en/events/copy_of_albcom-seminar-axiom-based-testing
- ALBCOM Seminar: Parameterized Testability
- 2012-09-13T12:00:00+02:00
- 2012-09-13T13:00:00+02:00
When
Sep 13, 2012 from 12:00 PM to 01:00 PM (Europe/Madrid / UTC200)
Where
Room S208 (floor -2), Omega Building, UPC, Barcelona
Attendees
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 n2 edges to have the property. It turns out that this property is easily testable just by accepting only graphs with at most \epsilon \times n2 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
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 n2 edges to have the property. It turns out that this property is easily testable just by accepting only graphs with at most \epsilon \times n2 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
Share: