Document Open Access Logo

Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs

Authors S. M. Dhannya, N. S. Narayanaswamy

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.52.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

S. M. Dhannya
  • Dept. of Computer Science and Engineering, IIT Madras, Chennai, India
N. S. Narayanaswamy
  • Dept. of Computer Science and Engineering, IIT Madras, Chennai, India

Acknowledgements

We thank the anonymous reviewers for their comments which have greatly improved the quality of the paper.

Cite As Get BibTex

S. M. Dhannya and N. S. Narayanaswamy. Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.52

Abstract

Given a hypergraph H, the conflict-free colouring problem is to colour vertices of H using minimum colours so that in every hyperedge e of H, there is a vertex whose colour is different from that of all other vertices in e. Our results are on a variant of the conflict-free colouring problem considered by Cheilaris et al.[Cheilaris et al., 2014], known as the 1-Strong Conflict-Free (1-SCF) colouring problem, for which they presented a polynomial time 2-approximation algorithm for interval hypergraphs. We show that an optimum 1-SCF colouring for interval hypergraphs can be computed in polynomial time. Our results are obtained by considering a different view of conflict-free colouring which we believe could be useful in general. For interval hypergraphs, this different view brings a connection to the theory of perfect graphs which is useful in coming up with an LP formulation to select the vertices that could be coloured to obtain an optimum conflict-free colouring. The perfect graph connection again plays a crucial role in finding a minimum colouring for the vertices selected by the LP formulation.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Hypergraphs
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Conflict-free Colouring
  • Interval Hypergraphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zachary Abel, Victor Alvarez, Erik D. Demaine, Sándor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, and Christian Scheffer. Three colors suffice: Conflict-free coloring of planar graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 1951–1963, USA, 2017. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/1.9781611974782.127.
  2. Pradeesha Ashok, Aditi Dudeja, and Sudeshna Kolay. Exact and FPT algorithms for max-conflict free coloring in hypergraphs. In Algorithms and Computation, pages 271-282, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-662-48971-0_24".
  3. C. Berge. Graphs and Hypergraphs. Elsevier Science Ltd., Oxford, UK, 1985. Google Scholar
  4. Panagiotis Cheilaris, Luisa Gargano, Adele A. Rescigno, and Shakhar Smorodinsky. Strong conflict-free coloring for intervals. Algorithmica, 70(4):732-749, December 2014. URL: https://doi.org/10.1007/s00453-014-9929-x.
  5. Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matoušek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, et al. Online conflict-free coloring for intervals. SIAM Journal on Computing, 36(5):1342-1359, 2006. URL: https://doi.org/10.1137/S0097539704446682.
  6. Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul Seymour, and Kristina Vušković. Recognizing Berge graphs. Combinatorica, 25(2):143-186, March 2005. URL: https://doi.org/10.1007/s00493-005-0012-8.
  7. Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of Mathematics, 164:51-229, 2006. Google Scholar
  8. Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing, 33(1):94-136, 2003. URL: https://doi.org/10.1137/S0097539702431840.
  9. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57). North-Holland Publishing Co., Amsterdam, The Netherlands, The Netherlands, 2004. Google Scholar
  10. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, June 1981. URL: https://doi.org/10.1007/BF02579273.
  11. Martin Grötschel, László Lovász, and Alexander Schrijver. Polynomial algorithms for perfect graphs. In C. Berge and V. Chvátal, editors, Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325-356. North-Holland, 1984. URL: https://doi.org/10.1016/S0304-0208(08)72943-8.
  12. Martin Grötschel, Lászlo Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. Google Scholar
  13. Matthew J Katz, Nissan Lev-Tov, and Gila Morgenstern. Conflict-free coloring of points on a line with respect to a set of intervals. Computational Geometry, 45(9):508-514, 2012. URL: https://doi.org/10.1016/j.comgeo.2012.01.013.
  14. Chaya Keller and Shakhar Smorodinsky. Conflict-free coloring of intersection graphs of geometric objects. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 2397-2411. Society for Industrial and Applied Mathematics, 2018. URL: https://doi.org/10.1137/1.9781611975031.154.
  15. János Pach and Gábor Tardos. Conflict-free colourings of graphs and hypergraphs. Combinatorics, Probability and Computing, 18(05):819-834, 2009. URL: https://doi.org/10.1017/S0963548309990290.
  16. Shakhar Smorodinsky. On the chromatic number of geometric hypergraphs. SIAM Journal on Discrete Mathematics, 21:676-687, 2007. URL: https://doi.org/10.1137/050642368.
  17. Shakhar Smorodinsky. Conflict-free coloring and its applications. In Geometry - Intuitive, Discrete, and Convex, pages 331-389. Springer Berlin Heidelberg, 2013. URL: https://doi.org/10.1007_978-3-642-41498-5_12.
  18. Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag, Berlin, Heidelberg, 2001. Google Scholar
  19. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, September 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact