{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T08:32:53Z","timestamp":1767429173529,"version":"3.48.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"\n Max-SAT<\/jats:sc>\n with cardinality constraint (\n CC-Max-Sat<\/jats:sc>\n ) is one of the classical NP-complete problems, that generalizes\n Maximum Coverage<\/jats:sc>\n ,\n Partial Vertex Cover<\/jats:sc>\n ,\n Max-2-SAT<\/jats:sc>\n with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF formula\n \n \\(\\Phi\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and a positive integer\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and the goal is to find an assignment\n \n \\(\\beta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with at most\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n variables set to true (also called a\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -weight assignment) such that the number of clauses satisfied by\n \n \\(\\beta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is maximized. The problem is known to admit an approximation algorithm with factor\n \n \\(1-\\frac{1}{e}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , which is probably optimal. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any\n \n \\(\\epsilon > 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and any function\n \n \\( h \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , no\n \n \\(h(k)(n+m)^{o(k)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time algorithm can approximate\n Maximum Coverage<\/jats:sc>\n (a monotone version of\n CC-Max-Sat<\/jats:sc>\n ) with\n \n \\( n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n elements and\n \n \\( m \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n sets to within a factor\n \n \\((1-\\frac{1}{e}+\\epsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , even with a promise that there exist\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n sets that fully cover the whole universe. In fact, the problem is hard to approximate within 0.929, assuming Unique Games Conjecture, even when the input formula is 2-CNF. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Toward this, we consider\n \n \\(K_{d,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes\n \n \\(K_{d,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n as an induced subgraph). We show that for every\n \n \\(\\epsilon > 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , there exists an algorithm for\n CC-Max-Sat<\/jats:sc>\n on\n \n \\(K_{d,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free formulas with approximation ratio\n \n \\((1-\\epsilon)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and running in time\n \n \\(2^{{\\mathcal{O}}((\\frac{dk}{\\epsilon})^{d})}(n+m)^{{\\mathcal{O}}(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (these algorithms are called FPT-AS). For\n Maximum Coverage<\/jats:sc>\n on\n \n \\(K_{d,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free set families, we obtain FPT-AS with running time\n \n \\((\\frac{dk}{\\epsilon})^{{\\mathcal{O}}(dk)}n^{{\\mathcal{O}}(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n Our second result considers \u201coptimizing\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\u201d with fixed covering constraint for the\n Maximum Coverage<\/jats:sc>\n problem. To explain our result, we first recast the\n Maximum Coverage<\/jats:sc>\n problem as the\n Max Red Blue Dominating Set with Covering Constraint<\/jats:sc>\n problem. Here, the input is a bipartite graph\n \n \\(G=(A,B,E)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a positive integer\n \n \\( t \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and the objective is to find a minimum sized subset\n \n \\(S\\subseteq A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , such that\n \n \\(|N(S)|\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (the size of the set of neighbors of\n \n \\( S \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) is at least\n \n \\( t \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We design an additive approximation algorithm for\n Max Red Blue Dominating Set with Covering Constraint<\/jats:sc>\n , on\n \n \\(K_{d,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free bipartite graphs, running in FPT time. In particular, if\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denotes the minimum size of\n \n \\(S\\subseteq A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , such that\n \n \\(|N(S)|\\geq t\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , then our algorithm runs in time\n \n \\((kd)^{{\\mathcal{O}}(kd)}n^{{\\mathcal{O}}{(1)}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and returns a set\n \n \\(S^{\\prime}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that\n \n \\(|N(S^{\\prime})|\\geq t\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(|S^{\\prime}|\\leq k+1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This is in sharp contrast to the fact that, even a special case of our problem, namely, the\n Partial Vertex Cover<\/jats:sc>\n problem (or\n Max<\/jats:sc>\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -VC<\/jats:sc>\n ) is W[1]-hard, parameterized by\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Thus, we get the best possible parameterized approximation algorithm for the\n Maximum Coverage<\/jats:sc>\n problem on\n \n \\(K_{d,d}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free bipartite graphs.\n <\/jats:p>","DOI":"10.1145\/3763238","type":"journal-article","created":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T15:07:51Z","timestamp":1756220871000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Approximation Schemes for Biclique-Free Max\n k<\/i>\n -Weight SAT and Max Coverage"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8900-9797","authenticated-orcid":false,"given":"Pallavi","family":"Jain","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Jodhpur, Jodhpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9274-4119","authenticated-orcid":false,"given":"Lawqueen","family":"Kanesh","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Indore, Indore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Leeds, Leeds, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8322-0639","authenticated-orcid":false,"given":"Souvik","family":"Saha","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2985-6983","authenticated-orcid":false,"given":"Abhishek","family":"Sahu","sequence":"additional","affiliation":[{"name":"National Institute of Science Education and Research, HBNI, Bhubaneswar, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India and University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6283-0846","authenticated-orcid":false,"given":"Anannya","family":"Upasana","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,7]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.12.002"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2019.24"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1150"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00434-9"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36136-7_17"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028569"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.05.016"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.002"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1309-3"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0053968"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_29"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.4064\/cm-6-1-61-65"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3325116"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004334"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2022.42"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.91"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055456"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2019.15"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.5"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492475"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390187"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.33"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5628"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0019-5"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.10.030"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T08:31:03Z","timestamp":1767429063000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,7]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3763238"],"URL":"https:\/\/doi.org\/10.1145\/3763238","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,10,7]]},"assertion":[{"value":"2023-11-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}