Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 9214))
Included in the following conference series:
1809Accesses
Abstract
Aconflict-free coloring of a hypergraph\(H = (V, \mathcal {E})\) with\(n=|V|\) vertices and\(m=|\mathcal {E}|\) hyperedges (where\(\mathcal {E}\subseteq 2^V\)), is a coloring of the verticesV such that every hyperedge\(E \in \mathcal {E}\) contains a vertex of “unique” color. Our goal is to minimize the total number of distinct colors. In its full generality, this problem is known as the conflict-free (hypergraph) coloring problem. It is known that\(\Theta (\sqrt{m})\) colors might be needed in general.
In this paper we study the relaxation of the problem where one is allowed to assign multiple colors to the same node. The goal here is to substantially reduce the total number of colors, while keeping the number of colors per node as small as possible. By a simple adaptation of a result by Pach and Tardos [2009] on the single-color version of the problem, one obtains that only\(O(\log ^2 m)\) colors in total are sufficient (on every instance) if each node is allowed to use up to\(O(\log m)\) colors.
By improving on the result of Pach and Tardos (under the assumption\(n\ll m\)), we show that the same result can be achieved with\(O(\log m \cdot \log n)\) colors in total, and either\(O(\log m)\) or\(O(\log n\cdot \log \log m) \subseteq O(\log ^2 n)\) colors per node. The latter coloring can be computed by a polynomial-time Las Vegas algorithm.
The second author is partially supported by the ERC Starting Grant NEWNET 279352.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
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
Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Annals of Operations Research153(1), 79–129 (2007)
Alon, N., Smorodinsky, S.: Conflict-free colorings of shallow discs. In: Proceedings of the 22nd Annual Symposium on Computational Geometry, SoCG, pp. 41–43 (2006)
Bar-Noy, A., Cheilaris, P., Olonetsky, S., Smorodinsky, S.: Online conflict-free colouring for hypergraphs. Combinatorics, Probability and Computing19, 493–516 (2010)
Bar-Noy, A., Cheilaris, P., Smorodinsky, S.: Deterministic conflict-free coloring for intervals: From offline to online. ACM Transactions on Algorithms4(4), 40:1–40:18 (2008)
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences45(1), 104–126 (1992)
Bärtschi, A., Ghosh, S.K., Mihalák, M., Tschager, T., Widmayer, P.: Improved bounds for the conflict-free chromatic art gallery problem. In: Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG, pp. 144–153 (2014)
Bärtschi, A., Suri, S.: Conflict-free chromatic art gallery coverage. Algorithmica68(1), 265–283 (2014)
Cheilaris, P., Gargano, L., Rescigno, A.A., Smorodinsky, S.: Strong conflict-free coloring for intervals. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 4–13. Springer, Heidelberg (2012)
Chen, K., Fiat, A., Kaplan, H., Levy, M., Matoušek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U., Welzl, E.: Online conflict-free coloring for intervals. SIAM Journal on Computing36(5), 1342–1359 (2006)
Erdős, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Infinite and Finite Sets. Colloquia Mathematica Societatis János Bolyai, vol. 10, pp. 609–627 (1973)
Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing33(1), 94–136 (2003)
Har-Peled, S., Smorodinsky, S.: Conflict-free coloring of points and simple regions in the plane. Discrete & Computational Geometry34(1), 47–70 (2005)
Katz, M.J., Lev-Tov, N., Morgenstern, G.: Conflict-free coloring of points on a line with respect to a set of intervals. Computational Geometry45(9), 508–514 (2012). CCCG 2007
Kostochka, A.V., Kumbhat, M., Łuczak, T.: Conflict-free colourings of uniform hypergraphs with few edges. Combinatorics, Probability and Computing21(4), 611–622 (2012)
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, chap. 4.2: Deriving and Applying Chernoff Bounds. Cambridge University Press (2005)
Moser, R.A., Tardos, G.: A constructive proof of the general Lovász local lemma. Journal of the ACM57(2), 11:1–11:15 (2010)
Pach, J., Tardos, G.: Conflict-free colourings of graphs and hypergraphs. Combinatorics, Probability and Computing18(05), 819–834 (2009)
Pach, J., Tardos, G.: Coloring axis-parallel rectangles. Journal of Combinatorial Theory, Series A117(6), 776–782 (2010)
Shearer, J.B.: On a problem of Spencer. Combinatorica5(3), 241–245 (1985)
Smorodinsky, S.: On the chromatic number of geometric hypergraphs. SIAM Journal on Discrete Mathematics21(3), 676–687 (2007)
Smorodinsky, S.: Conflict-Free Coloring and its Applications. Geometry-Intuitive, Discrete, and Convex, Bolyai Society Mathematical Studies24, 331–389 (2014)
Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discrete Mathematics20, 69–76 (1977)
Author information
Authors and Affiliations
Department of Computer Science, ETH Zürich, 8092, Zürich, Switzerland
Andreas Bärtschi
IDSIA, University of Lugano, 6928, Manno, Switzerland
Fabrizio Grandoni
- Andreas Bärtschi
You can also search for this author inPubMed Google Scholar
- Fabrizio Grandoni
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toAndreas Bärtschi.
Editor information
Editors and Affiliations
Carleton University, Ottawa, Canada
Frank Dehne
Carleton University, Ottawa, Canada
Jörg-Rüdiger Sack
University of Victoria, Victoria, Canada
Ulrike Stege
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Bärtschi, A., Grandoni, F. (2015). On Conflict-Free Multi-coloring. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_9
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-319-21839-7
Online ISBN:978-3-319-21840-3
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative