Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR06-053 | 6th April 2006 00:00

Testing Convexity Properties of Tree Colorings

TR06-053
Authors: Eldar Fischer, Orly Yahalom
Publication: 22nd April 2006 09:06
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint