Testing Convexity Properties of Tree Colorings
A coloring of a graph is convex if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in various areas involving large graphs. We study the important subcase of testing for convexity in trees. This problem is linked, among other possible applications, with the study of phylogenetic trees, which are central in genetic research, and are used in linguistics and other areas. We give a 1-sided, non-adaptive, epsilon-test with query complexity O(k/epsilon (2)) and time complexity O(kn/epsilon). For both our convexity and quasi-convexity tests, we show that, assuming that a query takes constant time, the time complexity can be reduced to a constant independent of n if we allow a preprocessing stage of time O(n) and O(n (2)), respectively. Finally, we show how to test for a variation of convexity and quasi-convexity where the maximum number of connectivity classes of each color is allowed to be a constant value other than 1.
phylogenetic trees property testing convex coloring sublinear algorithms massively parameterized graph algorithms