License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.52
URN: urn:nbn:de:0030-drops-119138
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11913/
Dhannya, S. M. ;
Narayanaswamy, N. S.
Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs
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.
BibTeX - Entry
@InProceedings{dhannya_et_al:LIPIcs:2020:11913,
author = {S. M. Dhannya and N. S. Narayanaswamy},
title = {{Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {52:1--52:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11913},
URN = {urn:nbn:de:0030-drops-119138},
doi = {10.4230/LIPIcs.STACS.2020.52},
annote = {Keywords: Conflict-free Colouring, Interval Hypergraphs}
}
|
Keywords: |
|
Conflict-free Colouring, Interval Hypergraphs |
|
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.03.2020 |
