{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:07Z","timestamp":1787321107914,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph $H=(U, \\mathcal{F})$, a conflict-free coloring of $H$ refers to a vertex coloring where every hyperedge has a vertex with a unique color, distinct from all other vertices in the hyperedge. In this paper, we initiate a study of a natural maximization version of this problem, namely, Max-CFC: For a given hypergraph $H$ and a fixed $r\\geq 2$, color the vertices of $U$ using $r$ colors so that the number of hyperedges that are conflict-free colored is maximized. By previously known hardness results for conflict-free coloring, this maximization version is NP-hard. We study this problem in the context of both exact and parameterized algorithms. In the parameterized setting, we study this problem with respect to a natural parameter---the solution size. In particular, the question we study is the following: p-CFC: For a given hypergraph, can we conflict-free color at least $k$ hyperedges with at most $r$ colors, the parameter being the solution size $k$. We show that this problem is fixed parameter tractable by designing an algorithm with running time $2^{\\mathcal{O}(k \\log \\log k + k \\log r)}(n+m)^{\\mathcal{O}(1)}$ using a novel connection to the Unique Coverage problem and applying the method of color coding in a nontrivial manner. For the special case for hypergraphs induced by graph neighborhoods we give a polynomial kernel. Finally, we give an exact algorithm for Max-CFC running in $\\mathcal{O}(2^{n+m})$ time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, Unique Maximum Coloring.<\/jats:p>","DOI":"10.1137\/16m1107462","type":"journal-article","created":{"date-parts":[[2018,6,4]],"date-time":"2018-06-04T15:39:55Z","timestamp":1528126795000},"page":"1189-1208","source":"Crossref","is-referenced-by-count":0,"title":["Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Pradeesha","family":"Ashok","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aditi","family":"Dudeja","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,5]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9425-5"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"atypb3","unstructured":"P. Cheilaris,\n                      Conflict-Free Coloring\n                      , Ph.D. thesis, CUNY, New York, 2009."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.03.005"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"G. Even, Z. Lotker, D. Ron, and S. Smorodinsky,\n                      Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks\n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 691-700.","DOI":"10.1109\/SFCS.2002.1181994"},{"key":"atypb6","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Texts Theoret. Comput. Sci. EATCS Ser., Springer, Berlin, 2006."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"F. V. Fomin and D. Kratsch,\n                      Exact Exponential Algorithms\n                      , Springer, Heidelberg, 2010.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.029"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000540"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1162-6"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"S. Jukna,\n                      Extremal Combinatorics: With Applications in Computer Science\n                      , Springer, Heidelberg, 2011.","DOI":"10.1007\/978-3-642-17364-6"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9608-0"},{"key":"atypb13","first-page":"182","author":"Naor M.","year":"1995","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990290"},{"key":"atypb15","unstructured":"S. Smorodinsky,\n                      Combinatorial Problems in Computational Geometry\n                      , Ph.D. thesis, Tel Aviv University, Tel Aviv, 2003."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"S. Smorodinsky,\n                      Conflict-Free Coloring and its Applications\n                      , Springer, Berlin, 2013.","DOI":"10.1007\/978-3-642-41498-5_12"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1107462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:05:55Z","timestamp":1787317555000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1107462"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1107462"],"URL":"https:\/\/doi.org\/10.1137\/16m1107462","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}