Fractional Path Coloring in Bounded Degree Trees with Applications
Tóm tắt
This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a 1+5/3e≈1.61—approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) optical networks.
Tài liệu tham khảo
Auletta, V., Caragiannis, I., Kaklamanis, C., Persiano, P.: Randomized path coloring on binary trees. In: APPROX’00. Lecture Notes in Computer Science, vol. 1913, pp. 60–71. Springer, Berlin (2000)
Azuma, K.: Weighted sum of certain dependent random variables. Tohoku Math. J. 19, 357–367 (1967)
Bermond, J.-C., Gargano, L., Pérennes, S., Rescigno, A.A., Vaccaro, U.: Efficient collective communication in optical networks. In: ICALP’96. Lecture Notes in Computer Science, vol. 1099, pp. 574–585. Springer, Berlin (1996)
Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics Series, vol. 244. Springer, Berlin (2008)
Caragiannis, I., Kaklamanis, C.: Approximate path coloring with applications to wavelength assignment in WDM optical networks. In: Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS ’04). Lecture Notes in Computer Science, vol. 2996, pp. 258–269. Springer, Berlin (2004)
Caragiannis, I., Kaklamanis, C., Persiano, P., Sidiropoulos, A.: Fractional and integral coloring of locally-symmetric sets of paths on binary trees. In: Proceedings of the 1st Workshop on Approximation and On-line Algorithms (WAOA ’03). Lecture Notes in Computer Science, vol. 2909, pp. 81–94. Springer, Berlin (2003)
Caragiannis, I., Kaklamanis, C., Persiano, P.: Approximation algorithms for path coloring in trees. In: Efficient Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 3484, pp. 74–96. Springer, Berlin (2006)
Chlamtac, I., Ganz, A., Karmi, G.: Lightpath communications: An approach to high bandwidth optical WAN’s. IEEE Trans. Commun. 40(7), 1171–1182 (1992)
Erlebach, T., Jansen, K., Kaklamanis, C., Mihail, M., Persiano, P.: Optimal wavelength routing on directed fiber trees. Theor. Comput. Sci. 221(1–2), 119–137 (1999)
Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57(2), 187–199 (1998)
Ferreira, A., Pérennes, S., Richa, A., Rivano, H., Stier, N.: On the design of multifiber WDM networks. In: AlgoTel’02, Mèze, France, May 2002, pp. 25–32
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Garg, N.: Multicommodity flows and approximation algorithms. Ph.D. thesis, Indian Institute of Technology, Delhi, April (1994)
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)
Gargano, L., Hell, P., Pérennes, S.: Colouring paths in directed symmetric trees with applications to WDM routing. In: ICALP’97. Lecture Notes in Computer Science, vol. 1256, pp. 505–515. Springer, Berlin (1997)
Golumbic, M.C., Jamison, R.E.: The edge intersection graphs of paths in a tree. J. Comb. Theory 38, 8–22 (1985)
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2, 2nd corrected edn. Springer, Berlin (1993)
Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problems. PWS-Kent, Boston (1997)
Jansen, K.: Approximate strong separation with application in fractional graph coloring and preemptive scheduling. In: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS ’02). Lecture Notes in Computer Science, vol. 2285, pp. 100–111. Springer, Berlin (2002)
Karapetyan, I.A.: On coloring of arc graphs. Dokl. Akad. Nauk Armianskoi CCP 70(5), 306–311 (1980). In Russian
König, D.: Graphok és matrixok. Mat. Fiz. Lapok 116–119 (1931)
Kumar, V.: Approximating arc circular colouring and bandwidth allocation in all-optical ring networks. In: APPROX’98 (1998)
Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383–390 (1975)
Niessen, T., Kind, J.: The round-up property of the fractional chromatic number for proper circular arc graphs, J. Graph Theory (1998)
Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221–232 (1985)
Tucker, A.: Coloring a family of circular arcs. SIAM J. Appl. Math. 29(3), 493–502 (1975)