TR06-053 Authors: Eldar Fischer, Orly Yahalom

Publication: 22nd April 2006 09:06

Downloads: 1738

Keywords:

A coloring of a graph is {\it 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. Our results concern the important subcase

of testing for convexity in trees. This problem is linked 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, distribution-free $\epsilon$-test for the

convexity of tree colorings. The query complexity of our test is

$O\left(\frac{k}{\epsilon}\right)$, where $k$ is the number of

colors, and the additional computational complexity is $O(n)$. On

the other hand, we prove a lower bound of

$\Omega\left(\frac{\sqrt{k}}{\sqrt{\epsilon}}\right)$ on the query

complexity of tests for convexity in the standard model, which

applies even for (unweighted) paths. We also consider whether the

dependency on $k$ can be reduced in some cases, and provide an

alternative testing algorithm for the case of paths. Then we

investigate a variant of convexity, namely {\it quasi-convexity},

in which all but one of the colors are required to induce

connected components. For this problem we provide a 1-sided,

non-adaptive $\epsilon$-test with query complexity

$O\left(\frac{k}{\epsilon^2}\right)$. Finally, we show how to test

for the convexity and quasi-convexity where the maximum number of

connectivity classes of each color is allowed to be a constant

value other than 1.