10.4230/LIPICS.STACS.2020.52
Dhannya, S. M.
S. M.
Dhannya
Dept. of Computer Science and Engineering, IIT Madras, Chennai, India
Narayanaswamy, N. S.
N. S.
Narayanaswamy
Dept. of Computer Science and Engineering, IIT Madras, Chennai, India
Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
ConferencePaper
Conflict-free Colouring
Interval Hypergraphs
en
Christophe Paul
https://orcid.org/0000-0001-6519-975X
Dept. of Computer Science and Engineering, IIT Madras, Chennai, India
Markus Bläser
Dept. of Computer Science and Engineering, IIT Madras, Chennai, India
10.4230/LIPIcs.STACS.2020
978-3-95977-140-5
1868-8969
https://doi.org/10.1137/1.9781611974782.127
https://doi.org/10.1007/978-3-662-48971-0_24
https://doi.org/10.1007/s00453-014-9929-x
https://doi.org/10.1137/S0097539704446682
https://doi.org/10.1007/s00493-005-0012-8
https://doi.org/10.1137/S0097539702431840
https://doi.org/10.1007/BF02579273
https://doi.org/10.1016/S0304-0208(08)72943-8
https://doi.org/10.1016/j.comgeo.2012.01.013
https://doi.org/10.1137/1.9781611975031.154
https://doi.org/10.1017/S0963548309990290
https://doi.org/10.1137/050642368
https://doi.org/10.1007_978-3-642-41498-5_12
Creative Commons Attribution 3.0 Unported license
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.
LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 52:1-52:16