direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Parameterized Testability

Prof. Kazuo Iwama (Kyoto University)

The talk is about property testing for NP optimization problems with parameter k under 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 techniquesfor their FPT algorithms (branch-and-bound 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 ε-farness makes the problem trivial for non-sparse graphs that are the source of hardness of the original optimization problem. We also consider k-Odd Cycle Transversal, which is another well-known FPT problem, but we only give a sublinear-time tester when k is a constant.  This is a joint work with Yuichi Yoshida.

Date
Speaker
Location
Language
02.09.2014 11:00
Kazuo Iwama
TEL 512
english

Back to the research colloquium site.

Zusatzinformationen / Extras