Abstract
A vertex coloring of a tree is called convex if each color induces a connected component. The NP-hard Convex Recoloring problem on vertex-colored trees asks for a minimum-weight change of colors to achieve a convex coloring. For the non-uniformly weighted model, where the cost of changing a vertex v to color c depends on both v and c, we improve the running time on trees from O(Δ κ·κn) to O(3κ·κn), where Δ is the maximum vertex degree of the input tree T, κ is the number of colors, and n is the number of vertices in T. In the uniformly weighted case, where costs depend only on the vertex to be recolored, one can instead parameterize on the number of bad colors β ≤ κ, which is the number of colors that do not already induce a connected component. Here, we improve the running time from O(Δ β·βn) to O(3β·βn). For the case where the weights are integers bounded by M, using fast subset convolution, we further improve the running time with respect to the exponential part to O(2κ·κ 4 n 2 M log2(nM)) and O(2β·β 4 n 2 M log2(nM)), respectively. Finally, we use fast subset convolution to improve the exponential part of the running time of the related 1-Connected Coloring Completion problem.
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
Bachoore, E.H., Bodlaender, H.L.: Convex recoloring of leaf-colored trees. In: Proc. 3rd ACiD. Texts in Algorithmics, vol. 9, pp. 19–33. College Publications, London (2007)
Bar-Yehuda, R., Feldman, I., Rawitz, D.: Improved approximation algorithm for convex recoloring of trees. Theory of Computing Systems, (to appear, 2007)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Möbius: fast subset convolution. In: Proc. 39th STOC, pp. 67–74. ACM Press, New York (2007)
Blum, C.: Revisiting dynamic programming for finding optimal subtrees in trees. European Journal of Operational Research 177(1), 102–115 (2007)
Bodlaender, H.L., Weyer, M.: Convex and connected recolorings of trees and graphs (unpublished manuscript, 2005)
Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Kernelization for convex recoloring. In: Proc. 2nd ACiD. Texts in Algorithmics, vol. 7, pp. 23–35. College Publications, London (2006)
Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Quadratic kernelization for convex recoloring of trees. In: Lin, G. (ed.) COCOON. LNCS, vol. 4598, pp. 86–96. Springer, Heidelberg (2007)
Chor, B., Fellows, M.R., Ragan, M.A., Razgon, I., Rosamond, F.A., Snir, S.: Connected coloring completion for general graphs: Algorithms and complexity. In: Lin, G. (ed.) COCOON. LNCS, vol. 4598, pp. 75–85. Springer, Heidelberg (2007)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195–207 (1972)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
Fürer, M.: Faster integer multiplication. In: Proc. 39th STOC, pp. 57–66. ACM Press, New York (2007)
Lingas, A., Wahlen, M.: On exact complexity of subgraph homeomorphism. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 256–261. Springer, Heidelberg (2007)
Maffioli, F.: Finding a best subtree of a tree. Technical Report 91.041, Politecnico di Milano, Dipartimento di Elettronica, Italy (1991)
Moran, S., Snir, S.: Convex recolorings of strings and trees: Definitions, hardness results and algorithms. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 218–232. Springer, Heidelberg (2005) (to appear in Journal of Computer and System Sciences)
Moran, S., Snir, S.: Efficient approximation of convex recolorings. Journal of Computer and System Sciences 73(7), 1078–1089 (2007)
Moran, S., Snir, S., Sung, W.-K.: Partial convex recolorings of trees and galled networks: Tight upper and lower bounds (February 2007) (manuscript)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31. Oxford University Press, Oxford (2006)
Ponta, O.: The Fixed-Parameter Approach to the Convex Recoloring Problem. Diplomarbeit, Mathematisches Institut, Ruprecht-Karls-Universität. Springer, Heidelberg (2007)
Razgon, I.: A 2O(k) poly(n) algorithm for the parameterized convex recoloring problem. Information Processing Letters 104(2), 53–58 (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ponta, O., Hüffner, F., Niedermeier, R. (2008). Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2008. Lecture Notes in Computer Science, vol 4978. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79228-4_43
Download citation
DOI: https://doi.org/10.1007/978-3-540-79228-4_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79227-7
Online ISBN: 978-3-540-79228-4
eBook Packages: Computer ScienceComputer Science (R0)