Abstract
The k -Leaf Root problem is a particular case of graph power problems. Here, we study “error correction” versions of k -Leaf Root—that is, for instance, adding or deleting at most l edges to generate a graph that has a k-leaf root. We provide several NP-completeness results in this context, and we show that the NP-complete Closest 3-Leaf Root problem (the error correction version of 3-Leaf Root) is fixed-parameter tractable with respect to the number of edge modifications in the given graph. Thus, we provide the seemingly first nontrivial positive algorithmic results in the field of error compensation for leaf root problems with k > 2. To this end, as a result of independent interest, we develop a forbidden subgraph characterization of graphs with 3-leaf roots.
Supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group PIAF (fixed-parameter algorithms), NI 369/4.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. In: Proc. 43rd FOCS, pp. 238–247. IEEE Computer Society, Los Alamitos (2002)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey. In: SIAM Monographs on Discrete Mathematics and Applications (1999)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58, 171–176 (1996)
Chen, Z.-Z., Jiang, T., Lin, G.: Computing phylogenetic roots with bounded degrees and errors. SIAM Journal on Computing 32(4), 864–879 (2003)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation 9, 251–280 (1990)
Fellows, M.R.: New directions and new challenges in algorithm design and complexity, parameterized. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 505–519. Springer, Heidelberg (2003)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-modeled data clustering: Fixed-parameter algorithms for clique generation. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol. 2653, pp. 108–119. Springer, Heidelberg (2003)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321–347 (2004)
Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM Journal on Computing 7(4), 413–423 (1978)
Jiang, T., Lin, G., Xu, J.: On the closest tree kth root problem. In: Manuscript, Department of Computer Science, University of Waterloo (2000)
Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM Journal on Computing 28(5), 1906–1922 (1999)
Kearney, P.E., Corneil, D.G.: Tree powers. Journal of Algorithms 29(1), 111–131 (1998)
Křivánek, M., Morávek, J.: NP-hard problems in hierarchical-tree clustering. Acta Informatica 23(3), 311–323 (1986)
Lau, L.C.: Bipartite roots of graphs. In: Proc. 15th ACM-SIAM SODA, pp. 952–961. ACM/SIAM (2004)
Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graphs. SIAM Journal on Discrete Mathematics 18(1), 83–102 (2004)
Lin, G., Kearney, P.E., Jiang, T.: Phylogenetic k-root and steiner k-root. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 539–551. Springer, Heidelberg (2000)
Lin, Y.L., Skiena, S.S.: Algorithms for square roots of graphs. SIAM Journal on Discrete Mathematics 8(1), 99–118 (1995)
Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Applied Mathematics 54(1), 81–88 (1994)
Natanzon, A.: Complexity and approximation of some graph modification problems. Master’s thesis, Department of Computer Science, Tel Aviv University (1999)
Niedermeier, R.: Ubiquitous parameterization — invitation to fixed-parameter algorithms. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 84–103. Springer, Heidelberg (2004)
Nishimura, N., Ragde, P., Thilikos, D.M.: On graph powers for leaf-labeled trees. Journal of Algorithms 42(1), 69–108 (2002)
Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Applied Mathematics 131(3), 651–654 (2003)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 379–390. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dom, M., Guo, J., Hüffner, F., Niedermeier, R. (2004). Error Compensation in Leaf Root Problems. In: Fleischer, R., Trippen, G. (eds) Algorithms and Computation. ISAAC 2004. Lecture Notes in Computer Science, vol 3341. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30551-4_35
Download citation
DOI: https://doi.org/10.1007/978-3-540-30551-4_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24131-7
Online ISBN: 978-3-540-30551-4
eBook Packages: Computer ScienceComputer Science (R0)