{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:59Z","timestamp":1750309439186,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T00:00:00Z","timestamp":1732924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"\n The\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -Strong Conflict-Free (\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -SCF colouring problem seeks to find a colouring of the vertices of a hypergraph\n \n \\(H\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n using minimum number of colours so that in every hyperedge\n \n \\(e\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of\n \n \\(H\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , there are at least\n \n \\(\\min\\{|e|,k\\}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n vertices whose colours are different from that of all other vertices in\n \n \\(e\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In the case of interval hypergraphs, we present an exact\n \n \\({\\mathsf{P}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -time algorithm for the\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -SCF problem thus solving an open problem posed in 2014. We achieve our results by showing that for any hypergraph, a\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -SCF colouring is a proper colouring of a related simple graph which we refer to as a\n co-occurrence graph<\/jats:italic>\n . We then show that a co-occurrence graph is obtained by identifying an induced subgraph of a second simple graph that we introduce, which we refer to as the\n conflict graph<\/jats:italic>\n . For interval hypergraphs, we show that each co-occurrence graph and the conflict graph are perfect graphs. This property plays a crucial role in our polynomial time algorithm. Second, we show that for an interval hypergraph, the\n \n \\(1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -SCF colouring number is the minimum partition of its intervals into sets such that each set has an exact hitting set (a hitting set in which each interval is hit exactly once).\n <\/jats:p>","DOI":"10.1145\/3698880","type":"journal-article","created":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T15:21:16Z","timestamp":1728141676000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Perfect Resolution of Strong Conflict-Free Colouring of Interval Hypergraphs"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8771-3921","authenticated-orcid":false,"given":"N. S.","family":"Narayanaswamy","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0302-7458","authenticated-orcid":false,"given":"S. M.","family":"Dhannya","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Sri Sivasubramaniya Nadar College of Engineering, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,30]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.127"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_24"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/1096893"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9929-x"},{"key":"e_1_3_1_6_2","unstructured":"Panagiotis Cheilaris and Shakhar Smorodinsky. 2012. Conflict-Free Coloring with Respect to a Subset of Intervals. arXiv:1204.6422 Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1204.6422"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446682"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702431840"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.1.42"},{"issue":"7","key":"e_1_3_1_12_2","first-page":"1192","article-title":"Programmes Lineaires-Caracterisation Des Matrices Totalement Unimodulaires","volume":"254","author":"Ghouilahouri Alain","year":"1962","unstructured":"Alain Ghouilahouri. 1962. Programmes Lineaires-Caracterisation Des Matrices Totalement Unimodulaires. Comptes Rendus Hebdomadaires Des Seances De L Academie Des Sciences 254, 7 (1962), 1192.","journal-title":"Comptes Rendus Hebdomadaires Des Seances De L Academie Des Sciences"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/984029"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)72943-8"},{"key":"e_1_3_1_16_2","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","year":"2012","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 2012. Geometric Algorithms and Combinatorial Optimization. Vol. 2, Springer Science & Business Media."},{"key":"e_1_3_1_17_2","first-page":"223","volume-title":"Linear Inequalities and Related Systems","author":"Hoffman A.","year":"1956","unstructured":"A. Hoffman and J. Kruskal. 1956. Integral Boundary Points of Convex Polyhedra. In Linear Inequalities and Related Systems. H. Kuhn and A. Tucker (Eds.), Annals of Mathematics Studies, Vol. 38, 223\u2013246."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.01.013"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.154"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/WCNC.2011.5779286"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990290"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/17634"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/050642368"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41498-5_12"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/500776"},{"key":"e_1_3_1_27_2","volume-title":"Introduction to Graph Theory","author":"West Douglas B.","year":"2000","unstructured":"Douglas B. West. 2000. Introduction to Graph Theory (2nd. ed.). Prentice Hall.","edition":"2"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.46"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698880","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698880","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:44Z","timestamp":1750295384000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,30]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3698880"],"URL":"https:\/\/doi.org\/10.1145\/3698880","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,11,30]]},"assertion":[{"value":"2021-06-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}