Testing forbidden topological subtrees

17^th May 2012, 15:00 G12
Yonatan Goldhirsh
Department of Computer Science
Technion, Israel

Abstract

We say that a colored ordered rooted tree H is a topological subtree of a colored ordered rooted tree T if we can map the vertices of H to vertices of T in a mapping which is one-to-one, preserves colors, preserves the ``descendant of'' relation, preserves right-to-left order, and maps least common ancestors to least common ancestors. Fix an ordered rooted tree T and let F be a family of ``forbidden'' colored ordered trees. We present an algorithm for testing whether a coloring of T is free from F or is epsilon-far from being free from F, with query complexity depending only on F and epsilon. This is an instance of the massively parameterized testing model, as T itself is immutable. Families of forbidden topological subtrees generalize previously considered tree coloring properties, such as tree monotonicity [FLNRRS 02] and convexity-like properties [FY 07].