Max-SAT with cardinality constraint ( CC-Max-Sat ) is one of the classical NP-complete problems, that generalizes Maximum Coverage , Partial Vertex Cover , Max-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF formula \(\Phi\) , and a positive integer \( k \) , and the goal is to find an assignment \(\beta\) with at most \( k \) variables set to true (also called a \( k \) -weight assignment) such that the number of clauses satisfied by \(\beta\) is maximized. The problem is known to admit an approximation algorithm with factor \(1-\frac{1}{e}\) , which is probably optimal. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any \(\epsilon > 0\) and any function \( h \) , no \(h(k)(n+m)^{o(k)}\) time algorithm can approximate Maximum Coverage (a monotone version of CC-Max-Sat ) with \( n \) elements and \( m \) sets to within a factor \((1-\frac{1}{e}+\epsilon)\) , even with a promise that there exist \( k \) 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 \(K_{d,d}\) -free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes \(K_{d,d}\) as an induced subgraph). We show that for every \(\epsilon > 0\) , there exists an algorithm for CC-Max-Sat on \(K_{d,d}\) -free formulas with approximation ratio \((1-\epsilon)\) and running in time \(2^{{\mathcal{O}}((\frac{dk}{\epsilon})^{d})}(n+m)^{{\mathcal{O}}(1)}\) (these algorithms are called FPT-AS). For Maximum Coverage on \(K_{d,d}\) -free set families, we obtain FPT-AS with running time \((\frac{dk}{\epsilon})^{{\mathcal{O}}(dk)}n^{{\mathcal{O}}(1)}\) . Our second result considers “optimizing \( k \) ,” with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the Maximum Coverage problem as the Max Red Blue Dominating Set with Covering Constraint problem. Here, the input is a bipartite graph \(G=(A,B,E)\) , a positive integer \( t \) , and the objective is to find a minimum sized subset \(S\subseteq A\) , such that \(|N(S)|\) (the size of the set of neighbors of \( S \) ) is at least \( t \) . We design an additive approximation algorithm for Max Red Blue Dominating Set with Covering Constraint , on \(K_{d,d}\) -free bipartite graphs, running in FPT time. In particular, if

Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. Given a set of candidates, C, a set of voters, V, approving a subset of candidates (called approval set of a voter), and an integer k, we consider the problem of selecting a ``good'' committee using Thiele rules. This problem is computationally challenging for most Thiele rules with monotone submodular satisfaction functions, as there is no (1-1/e- epsilon) approximation algorithm in f(k)(|C| + |V|)^(o(k)) time for any fixed epsilon > 0 and any computable function f, and no PTAS even when the length of approval set is two. Skowron designed an approximation scheme running in FPT time parameterized by the combined parameter, size of the approval set, and k. In this paper, we consider a parameter d+k (no d voters approve the same set of d candidates), where d is upper bounded by the size of the approval set (thus, can be much smaller). With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i.e., 1-additive approximation). Additionally, we resolve an open question by Yang and Wang regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm.

In this paper, we study the Achromatic Number problem. Given a graph G and an integer k, the task is to determine whether there exists a proper coloring of G, using at least k colors, in which every pair of distinct colors appears on the endpoints of some edge. It was established early on that the problem is fixed-parameter tractable (FPT)- even before the formal development of parameterized complexity. In fact, Farber, Hahn, Hell, and Miller [JCTB, 1986] devised an algorithm with a running time of 𝒪(f(k) ⋅ |E(G)|). Although the exact form of f(k) was not specified, it appears to be at least doubly exponential in k. In our work, we first present an algorithm with an explicit dependence on k, and then introduce another algorithm that is parameterized by the vertex cover number of the graph. More formally, we show the following. - Achromatic Number is solvable in time 2^𝒪(k⁵)+𝒪(|E(G)|). - Achromatic Number admits a polynomial kernel when the input is restricted to a d-degenerate graph and a more efficient kernel on trees. - We also study the parameterized complexity of the problem with respect to Vertex Cover and show that it admits an FPT algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1), where 𝓁 is the size of a vertex cover.

MAX-SAT with cardinality constraint (CC-MAX-SAT) is one of the classical NP-complete problems, that generalizes MAXIMUM COVERAGE, PARTIAL VERTEX COYER, MAX-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. The problem is known to admit an approximation algorithm with factor , which is probably optimal. In fact, the problem is hard to approximate within 0.944, assuming Unique Games Conjecture, even when the input formula is 2-CNF. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any ε > 0 and any function h, no h(k)(n + m)o(k) time algorithm can approximate MAXIMUM COVERAGE (a monotone version of CC-MAX-SAT) with n elements and m sets to within a factor , even with a promise that there exist k sets that fully cover the whole universe. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Towards this we consider Kd,d-free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes Kd,d as an induced subgraph). We show that for every ε > 0, there exists an algorithm for CC-MAX-SAT on Kd,d-free formulas with approximation ratio (1 — ε) and running in time (these algorithms are called FPT-AS). For, MAXIMUM COVERAGE on Kd,d-free set families, we obtain FPT-AS with running time . Our second result considers “optimizing k”, with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the MAXIMUM COVERAGE problem as the MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT problem. Here, input is a bipartite graph G = (A, B, E), a positive integer t, and the objective is to find a minimum sized subset S ⊆ A, such that |N(S)| (the size of the set of neighbors of S) is at least t. We design an additive approximation algorithm for MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT, on Kd,d-free bipartite graphs, running in FPT time. In particular, if k denotes the minimum size of S ⊆ A, such that |N(S)| ≥ t, then our algorithm runs in time (kd)O(kd)nO(1) and returns a set S' such that |N(S')| ≥ t and |S'| ≤ k +1. This is in sharp contrast to the fact that, even a special case of our problem, namely, the PARTIAL VERTEX COVER problem (or MAX k-VC) is W[1]-hard, parameterized by k. Thus, we get the best possible parameterized approximation algorithm for the MAXIMUM COVERAGE problem on Kd,d-free bipartite graphs. * Pallavi Jain is supported by Seed Grant (IITJ/R&D/2022-23/07) and SERB-SUPRA Grant(SPR/2021/000860). Lawqueen Kanesh is supported by EPSRC Standard Research Grant (EP/V044621/1). Saket Saurabh is supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819416); and he also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.