2026-08-07T05:21:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11913 2024-03-06T10:49:00Z ddc:004 open_access

Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs Dhannya, S. M. Narayanaswamy, N. S. Conflict-free Colouring Interval Hypergraphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik S. M. Dhannya and N. S. Narayanaswamy 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.52 urn:nbn:de:0030-drops-119138 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.52 eng https://creativecommons.org/licenses/by/3.0/legalcode