Re: Algorithms and Complexity seminar

Dear all,

I remind you our seminar this Tuesday at 10am by Kazuo Iwama, room 1D06.

Frédéric

On 11 sept. 2012, at 10:02, Frederic Magniez <frederic.magniez@liafa.univ-paris-diderot.fr> wrote:

> Dear all,
>
> The seminar of team Algorithms and Complexity will start this year next Tuesday, September 18th, at 10 am in room 1D06.
> Our first speaker is Kazuo Iwama from Kyoto University, who is visiting us this month.
>
> See you Tuesday,
>
> Frederic
>
> ---
> Title: Parameterized Testability
> Speaker: Kazuo Iwama (Kyoto University)
>
> In graph property testing, given a graph represented by an oracle, wear
> 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 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.
> --