LIPIcs.IPEC.2015.43.pdf
- Filesize: 495 kB
- 12 pages
Document
Parameterized and Approximation Algorithms for the Load Coloring Problem
Authors
-
Part of:
Volume:
10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-11-19
Cite As Get BibTex
Florian Barbero, Gregory Gutin, Mark Jones, and Bin Sheng. Parameterized and Approximation Algorithms for the Load Coloring Problem. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.IPEC.2015.43
Abstract
Let c, k be two positive integers. Given a graph G=(V,E), the c-Load Coloring problem asks whether there is a c-coloring varphi: V => [c] such that for every i in [c], there are at least k edges with both endvertices colored i. Gutin and Jones (IPL 2014) studied this problem with c=2. They showed 2-Load Coloring to be fixed-parameter tractable (FPT) with parameter k by obtaining a kernel with at most 7k vertices. In this paper, we extend the study to any fixed c by giving both a linear-vertex and a linear-edge kernel. In the particular case of c=2, we obtain a kernel with less than 4k vertices and less than 8k edges. These results imply that for any fixed c >= 2, c-Load Coloring is FPT and the optimization version of c-Load Coloring (where k is to be maximized) has an approximation algorithm with a constant ratio.
Subject Classification
Keywords
- Load Coloring
- fixed-parameter tractability
- kernelization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
N. Ahuja, A. Baltz, B. Doerr, A. Prívetivý, and A. Srivastav. On the minimum load coloring problem. J. Discrete Algorithms, 5(3):533-545, 2007.
-
J.-P. Allouche and J. Shallit. The ring of k-regular sequences, II. Theor. Comput. Sci., 307(1):3-29, 2003.
-
H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos. (meta) kernelization. In Foundations of Computer Science, FOCS 2009, pages 629-638. IEEE Computer Society, 2009.
-
M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
-
E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005.
-
E. D. Demaine and M. T. Hajiaghayi. The bidimensionality theory and its algorithmic applications. Comput. J., 51(3):292-302, 2008.
-
R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.
-
F. V. Fomin, D. Lokshtanov, N. Misra, G. Philip, and S. Saurabh. Hitting forbidden minors: Approximation and kernelization. In Symposium on Theoretical Aspects of Computer Science, STACS 2011, volume 9 of LIPIcs, pages 189-200. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011.
-
G. Gutin and M. Jones. Parameterized algorithms for load coloring problem. Inf. Process. Lett., 114(8):446-449, 2014.
-
S. Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113, 2014.
-
D. Lokshtanov, N. Misra, and S. Saurabh. Kernelization - preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond, volume 7370 of Lecture Notes in Computer Science, pages 129-161. Springer, 2012.
-
E. Prieto. The method of extremal structure on the k-maximum cut problem. In Theory of Computing 2005, Eleventh CATS 2005, Computing: The Australasian Theory Symposium, Newcastle, NSW, Australia, January/February 2005, volume 41 of CRPIT, pages 119-126. Australian Computer Society, 2005.
- J. Shallit, 2002. URL: http://oeis.org/A073121.