Alladi Ramakrishnan Hall

Parameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max Coverage

Anannya Upasana

IMSc

Parameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max Coverage Abstract: Max-SAT with cardinality constraint 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, 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 this assignment is maximized. The problem is known to admit an approximation algorithm with factor (1- 1/e), which is probably optimal. In fact, the problem is hard to approximate within 0.944, assuming the Unique Games Conjecture, even when the input formula is a 2-CNF. 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 Max-SAT with cardinality constraint) with n elements and m sets to within a factor (1- 1\e + epsilon), 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 Kdd-free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes Kdd as an induced subgraph). We show that for every epsilon > 0, there exists an algorithm for Max-SAT with cardinality constraint on Kdd-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 Kdd-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 a 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 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 of 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, on Kdd-free bipartite graphs, running in FPT time. In particular, if k denotes the minimum size of S, such that |N(S)| >= t, then our algorithm runs in time (kd)^{\mathcal{O}(kd)}n^{\mathcal{O}{(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 is W[1]-hard, parameterized by k. Thus, we get the best possible parameterized approximation algorithm for the Maximum Coverage problem on Kdd-free bipartite graphs. Max-SAT with cardinality constraint 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, 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 this assignment is maximized. The problem is known to admit an approximation algorithm with factor (1- 1/e), which is probably optimal. In fact, the problem is hard to approximate within 0.944, assuming the Unique Games Conjecture, even when the input formula is a 2-CNF. 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 Max-SAT with cardinality constraint) with n elements and m sets to within a factor (1- 1\e + epsilon), 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 Kdd-free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes Kdd as an induced subgraph). We show that for every epsilon > 0, there exists an algorithm for Max-SAT with cardinality constraint on Kdd-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 Kdd-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 a 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 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 of 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, on Kdd-free bipartite graphs, running in FPT time. In particular, if k denotes the minimum size of S, such that |N(S)| >= t, then our algorithm runs in time (kd)^{\mathcal{O}(kd)}n^{\mathcal{O}{(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 is W[1]-hard, parameterized by k. Thus, we get the best possible parameterized approximation algorithm for the Maximum Coverage problem on Kdd-free bipartite graphs.