Skip to content Search
Search our website:

Testing forbidden topological subtrees

  • Speaker: Yonatan Goldhirsh
  • Date: Wednesday, 16 May 2012 from 16:45 to 17:45
  • Location: Room 745, Malet Street

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 parametrized 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].