Abstract
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. Our results concern 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, distribution-free ε-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(\sqrt{k/\epsilon})\) 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 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 ε-test with query complexity \(O\left(\frac{k}{\epsilon^2}\right)\) and time complexity O(n). 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). 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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., et al.: Regular languages are testable with a constant number of queries. Siam Journal on Computing 30(6), 1842–1862 (2001)
Fischer, E.: The art of uninformed decisions: A primer to property testing (Also In: Paun, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science: The Challenge of the New Century, vol. I, pp. 229–264. World Scientific Publishing (2004)). Bulletin of the European Association for Theoretical Computer Science 75, 97–126, Section 8 (2001)
Goldreich, O., Goldwasser, S., Ron, D.: Propery testing and its connection to learning and approximation. Journal of the ACM 45(4), 653–750 (1998)
Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32, 302–343 (2002)
Halevy, S., Kushilevitz, E.: Distribution-free property testing. In: Proceedings of the 7th RANDOM and the 6th APPROX, pp. 302–317 (2003)
Halevy, S., Kushilevitz, E.: Distribution-free connectivity testing. In: Proceedings of the 8th RANDOM and the 7th APPROX, pp. 393–404 (2004)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestor. SIAM Journal on Computing 13(2), 338–355 (1984)
Knuth, D.E.: The Art of Computer Programming, vol. 1: Fundamental Algorithms, 2nd edn. Addison-Wesley, Reading (1973)
Moran, S., Snir, S.: Convex recolorings of phylogenetic trees: definitions, hardness results and algorithms (Also: Journal of Computer and System Sciences (JCSS), in press). In: Workshop on Algorithms and Data Structures (WADS), pp. 218–232 (2005)
Fischer, E., et al.: Monotonicity testing over general poset domains. In: Proceedings of the 34th STOC, pp. 474–483 (2002)
Moret, B.M.E., Warnow, T.: Reconstructing optimal phylogenetic trees: A challenge in experimental algorithmics. In: Fleischer, R., Moret, B.M.E., Schmidt, E.M. (eds.) Experimental Algorithmics. LNCS, vol. 2547, pp. 163–180. Springer, Heidelberg (2002)
Nakhleh, L., et al.: A comparison of phylogenetic reconstruction methods on an IE dataset. Transactions of the Philological Society 3(2), 171–192 (2005)
Ron, D.: Property testing (a tutorial). In: Rajasekaran, S., et al. (eds.) Handbook of Randomized Computing, vol. II, pp. 597–649. Kluwer Academic Publishers, Dordrecht (2001)
Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996)
Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)
Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplifications and parallelization. SIAM Journal on Computing 17, 1253–1262 (1988)
Yao, A.C.: Probabilistic computation, towards a unified measure of complexity. In: Proceedings of the 18th IEEE FOCS, pp. 222–227. IEEE Computer Society Press, Los Alamitos (1977)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Fischer, E., Yahalom, O. (2007). Testing Convexity Properties of Tree Colorings. In: Thomas, W., Weil, P. (eds) STACS 2007. STACS 2007. Lecture Notes in Computer Science, vol 4393. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70918-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-70918-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70917-6
Online ISBN: 978-3-540-70918-3
eBook Packages: Computer ScienceComputer Science (R0)