Introduction
Coverage and satisfaction problems under a cardinality bound can be viewed from two complementary perspectives: maximizing the weight of the elements, clauses, or constraints that are covered or satisfied, or minimizing the weight of those that remain uncovered or unsatisfied. Because these two objective values sum to the total input weight, the formulations have the same optimal solutions. Their multiplicative approximation guarantees, however, do not translate into one another. When an optimal solution leaves only a small amount of weight uncovered or unsatisfied, a constant-factor approximation to the covered or satisfied weight may leave a residual arbitrarily larger than the optimum, whereas an approximation to the residual controls this quantity directly. Conversely, when the optimal covered or satisfied weight is small, an approximation to the residual may provide little information about the weight actually covered or satisfied, making the maximization viewpoint more informative. Thus, depending on the instance, either side of the complementary objective may provide the more meaningful approximation guarantee. While the maximization viewpoint has been studied extensively for coverage and satisfiability problems, these differences motivate a systematic study of the corresponding residual-minimization objectives under a cardinality bound.
The classical Maximum Coverage problem asks for at most k k k sets whose union has maximum total weight. We study the complementary residual objective: selecting at most k k k sets so as to minimize the total weight of the elements left uncovered. This objective arises naturally when the unserved portion is itself the quantity of interest. For example, under the approval-based Chamberlin–Courant rule, each candidate corresponds to the set of voters who approve that candidate. Thus, after selecting a committee, the uncovered elements correspond precisely to voters who approve none of its members [7 , 31 ] . We call this problem Min-UnCoverage. It has previously appeared under the names MinNonCovered [31 Definition 2.2] and Min k k k -Uncovered [16 Section 4.2.3] . Formally, an instance consists of a ground set U U U , a family S ⊆ 2 U \mathcal{S} \subseteq2^{U} S ⊆ 2 U , positive rational weights on the ground elements, and a cardinality bound k k k . The goal is to select at most k k k sets while minimizing the total weight of the elements they leave uncovered. We study this objective together with two satisfaction analogues. An instance of Min-Unsat SAT contains a CNF formula with positive rational clause weights, and an instance of Min-Unsat CSP contains weighted constraints over Boolean variables. In both problems, the goal is to set at most k k k variables to true while minimizing the total weight of the unsatisfied clauses or constraints. All weights are encoded in binary. The three problems form a hierarchy that preserves objective weights: Min-UnCoverage is the monotone special case of Min-Unsat SAT, which is a special case of Min-Unsat CSP. The cardinality bound is an upper bound throughout; the distinction from requiring exactly k k k selected objects is discussed in Proposition 3.6 .
For coverage, the separation between the two approximation viewpoints Maximum Coverage and Min-UnCoverage is already extreme. As Skowron and Faliszewski emphasize, when k k k sets can cover the whole universe, a constant-factor approximation for Maximum Coverage may still miss a constant fraction of the elements, whereas every finite-factor approximation for Min-UnCoverage must find a complete cover [31 p. 692] . On the maximization side, the classical greedy algorithm achieves a ( 1 − 1 / e ) (1 - 1/e) ( 1 − 1/ e ) approximation [28 ] , and Feige proved that, for every constant δ > 0 \delta> 0 δ > 0 , no polynomial-time algorithm can achieve 1 − 1 / e + δ 1 - 1/e + \delta 1 − 1/ e + δ unless P = N P \mathrm{P} = \mathrm{NP} P = NP [15 ] . Even allowing parameterized running time does not improve this threshold in general: under the randomized Gap Exponential Time Hypothesis (Gap-ETH), no T ( k ) N o ( k ) T(k)N^{o(k)} T ( k ) N o ( k ) -time algorithm achieves 1 − 1 / e + δ 1 - 1/e + \delta 1 − 1/ e + δ for any function T T T and any constant δ > 0 \delta> 0 δ > 0 [25 ] .
For the complementary minimization objectives, the obstruction is already visible when the optimum value is zero. Every approximation with a finite factor must then find a zero-valued solution exactly. Deciding whether at most k k k sets cover every element, or whether an assignment of Hamming weight at most k k k satisfies every constraint, is W [ 2 ] W[2] W [ 2 ] -hard by the standard hardness of Set Cover and its monotone-SAT encoding. Consequently, unless FPT = W[2 ] , none of the three unrestricted problems admits a finite-factor FPT approximation parameterized by k k k (Corollary 2.9). All objective-value hardness proofs in this paper distinguish zero optimum from positive optimum. They do not establish a multiplicative gap under the promise that the optimum is positive. This sharp contrast, together with the inapproximability of the unrestricted problems, shows that obtaining any meaningful finite-factor approximation requires imposing additional structure. This motivates our study of natural restrictions of the incidence graph under which the residual-minimization objectives become approximable.
Alongside approximating the minimum uncovered or unsatisfied weight while using at most k k k selectable objects, we study a complementary question. Given a target attained by a solution using at most k k k selectable objects, can an FPT algorithm preserve that target while using at most g ( k , d ) g(k,d) g ( k , d ) objects, where g g g is a computable function of the parameters and g ( k , d ) ≥ k g(k,d) \ge k g ( k , d ) ≥ k ? In this setting, the maximization and residual-minimization formulations are exactly equivalent: leaving uncovered or unsatisfied weight at most t t t is the same as covering or satisfying weight at least the corresponding complementary target. Thus, unlike multiplicative approximation of the objective value, there is no distinction between the two viewpoints once the target is fixed and only the cardinality bound is approximated. Consequently, any target-preserving result for one formulation immediately transfers to the other. For coverage, this is the weighted Partial Set Cover problem: given a prescribed coverage threshold, minimize the number of sets whose union has total weight at least that threshold. We return to this question after introducing the structural restrictions considered in the paper and presenting our results on approximating the uncovered or unsatisfied weight.
Structural restrictions. We study five principal restrictions on the incidence graph G = ( A ⊎ B , E ) G = (A \uplus B, E) G = ( A ⊎ B , E ) . For Min-UnCoverage, A = S A = S A = S and B = U B = U B = U , with S u ∈ E S_u \in E S u ∈ E if and only if u ∈ S u \in S u ∈ S . For Min-Unsat SAT and Min-Unsat CSP, A A A is the set of variables and B B B is the set of clauses or constraints, with x C ∈ E x_C \in E x C ∈ E if and only if x x x occurs in C C C . Thus, the cardinality bound k k k restricts the choices made on side A A A , while the vertices whose weights contribute to the residual lie on side B B B . The first two restrictions bound degrees on opposite sides of the incidence graph. Bounded arity means that every clause or constraint contains at most d d d variables; for Min-UnCoverage, the corresponding condition is bounded element frequency, meaning that every ground element belongs to at most d d d sets. Conversely, bounded variable frequency means that every variable occurs in at most d d d clauses or constraints; on the coverage side, this corresponds to bounded set size. These two restrictions are incomparable.
Beyond these two one-sided degree bounds, we consider three increasingly general restrictions on the incidence graph. The first is K d , d K_{d,d} K d , d -freeness: the incidence graph contains no complete bipartite subgraph with d d d vertices on each side. A degree bound of d d d on either side implies K d + 1 , d + 1 K_{d+1,d+1} K d + 1 , d + 1 -freeness. Next, we consider bounded semi-ladder index, a notion introduced by Fabiánski et al. [14 ] . A semi-ladder of order ℓ \ell ℓ consists of vertices a 1 , … , a ℓ a_1,\ldots,a_\ell a 1 , … , a ℓ on one side and b 1 , … , b ℓ b_1,\ldots,b_\ell b 1 , … , b ℓ on the other such that a i b i a_i b_i a i b i is a nonedge and a i b j a_i b_j a i b j is an edge whenever j < i j < i j < i (Definition 2.5). The semi-ladder index is the maximum order of such a pattern. Every K d , d K_{d,d} K d , d -free graph has semi-ladder index less than 2 d 2d 2 d , while set systems of semi-ladder index two can contain arbitrarily large bicliques. For example, a disjoint union of complete bipartite graphs has semi-ladder index at most two and may contain a K n , n K_{n,n} K n , n for arbitrarily large n n n . Thus bounded semi-ladder index is strictly more general than biclique-freeness. The final restriction is bounded VC dimension. The neighborhoods of the vertices in A A A form the set system { N G ( a ) : a ∈ A } ⊆ 2 B \{N_G(a) : a \in A\} \subseteq2^B { N G ( a ) : a ∈ A } ⊆ 2 B . A set X ⊆ B X \subseteq B X ⊆ B is shattered if, for every Y ⊆ X Y \subseteq X Y ⊆ X , there exists a vertex a ∈ A a \in A a ∈ A such that N G ( a ) ∩ X = Y N_G(a) \cap X = Y N G ( a ) ∩ X = Y . The VC dimension is the maximum cardinality of a shattered set (Definition 2.4). Every shattered set of size ℓ \ell ℓ yields a semi-ladder of order ℓ \ell ℓ (Observation 2.7), so bounded semi-ladder index implies bounded VC dimension. The converse fails: half-graphs have VC dimension one but unbounded semi-ladder index; a half-graph of order ℓ \ell ℓ has vertices a 1 , … , a ℓ a_1,\ldots,a_\ell a 1 , … , a ℓ and b 1 , … , b ℓ b_1,\ldots,b_\ell b 1 , … , b ℓ , with a i b j a_i b_j a i b j an edge exactly when j < i j<i j < i .
Our results. We first present our results on approximating the residual weight while respecting the cardinality bound, organized according to the hierarchy of incidence restrictions described above. We then turn to approximating the cardinality bound while preserving a prescribed upper bound on the residual weight.
Bounded arity and ground-element frequency. For every d ≥ 1 d\ge1 d ≥ 1 , we give a deterministic efficient parameterized approximation scheme (EPAS) for weighted arity-d d d Min-Unsat CSP parameterized by k + d k+d k + d (Theorem 3.4 ). For 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 , its running time is
( d k / ε ) O ( k ) N O ( 1 ) , (dk/\varepsilon)^{O(k)}N^{O(1)}, ( d k / ε ) O ( k ) N O ( 1 ) ,
where N N N denotes the input encoding size. Since CNF formulas are a special case of Boolean CSP, the same result applies to weighted arity-d d d Min-Unsat SAT. Moreover, encoding each ground element as a monotone clause of the same weight gives a deterministic EPAS for weighted Min-UnCoverage when every ground element belongs to at most d d d sets (Corollary 3.5). Skowron and Faliszewski previously gave a randomized FPT approximation scheme for unit weights; our algorithm is deterministic and also handles positive rational weights [31 ] .
The algorithm compares the all-zero assignment with an optimum assignment at each recursive step. If the all-zero assignment is not already a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximation, then some variable set to one by the optimum occurs in constraints of sufficiently large total weight that the all-zero assignment violates. Bounded arity limits the number of variables with this property, allowing the algorithm to branch over them in FPT time.
Bounded variable frequency and set size. This pair of corresponding one-sided degree restrictions yields a sharp separation between coverage and general satisfaction problems. In the monotone-CNF encoding of Min-UnCoverage, each set S S S is represented by a variable x S x_S x S , which occurs in one clause for every element of S S S . Thus, a bound of d d d on set size is exactly a bound of d d d on variable frequency. Bläser’s randomized color-coding algorithm gives an exact FPT algorithm for unweighted Partial Set Cover [4 ] ; Bonnet et al. gave an alternative deterministic FPT algorithm for Maximum k k k -Set Cover based on greediness-for-parameterization [13 ] . We adapt Bläser’s color-coding framework to positive rational element weights and show that weighted Min-UnCoverage is exactly solvable in
2 O ( k d ) N O ( 1 ) 2^{O(kd)}N^{O(1)} 2 O ( k d ) N O ( 1 )
time when every set has size at most d d d (Proposition B.1 ). Our extension assigns each covered element (at most k d kd k d many) to one selected set, producing at most k k k pairwise disjoint subsets, each of size at most d d d . A k d kd k d -perfect hash family contains a coloring that is injective on all elements covered by an optimum solution, and a dynamic program over subsets of colors finds a maximum-weight collection of such subsets while remembering the original set containing each one. Selecting those original sets recovers an optimum coverage solution. Since this proof is a weighted deterministic adaptation of Bläser’s color-coding argument, rather than one of our main structural techniques, we defer it to Section B. In contrast, we show that unless FPT = W[1 ] , neither Min-Unsat SAT nor Min-Unsat CSP admits a finite-factor FPT approximation parameterized by k + d k+d k + d , even on unweighted instances in which every variable occurs in at most d d d clauses or constraints (Theorem 4.6 ). Under the Exponential Time Hypothesis (ETH), no such approximation runs in f ( k , d ) N o ( k + d ) f(k,d)N^{o(\sqrt{k+d})} f ( k , d ) N o ( k + d ) time for any computable function f f f .
K d , d K_{d,d} K d , d -free graphs and bounded semi-ladder index. We now move from one-sided degree bounds to restrictions on the entire incidence graph. For weighted Min-UnCoverage on incidence graphs of semi-ladder index at most d d d , we give a deterministic EPAS parameterized by k + d k+d k + d (Theorem 5.4), with running time
( d k ε ) O ( d 2 k ε 2 log 2 k ε ) N O ( 1 ) . \left(\frac{dk}{\varepsilon}\right)^{O\left(\frac{d^2k}{\varepsilon^2}\log\frac{2k}{\varepsilon}\right)}N^{O(1)}. ( ε d k ) O ( ε 2 d 2 k l o g ε 2 k ) N O ( 1 ) .
The algorithm adapts the skeleton-based branching framework and deterministic weighted-net construction of Kundu et al. [23 ] , which in turn builds on Guillemot’s FPT algorithm for Set Cover on semi-ladder-free hypergraphs [17 ] . The skeletons, eligible families, forced-coverage intersections, weighted nets, and semi-ladder depth argument are inherited from that framework. Our additional step is the residual-weight case distinction and averaging argument described next, which gives the new approximation guarantee. The algorithm maintains k k k skeletons M 1 , … , M k M_1,\ldots,M_k M 1 , … , M k , where M i M_i M i records elements that the i i i th chosen set must contain. The sets containing M i M_i M i remain eligible for that coordinate, and their intersection is already guaranteed to be covered. Let W W W be the elements not guaranteed to be covered at any coordinate. If w ( W ) > ( 1 + ε ) OPT m i s s ( I ) w(W)>(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ) > ( 1 + ε ) OPT miss ( I ) , an averaging argument shows that some optimum set O i O_i O i covers weight greater than δ w ( W ) \delta w(W) δ w ( W ) , where δ = ε / ( k ( 1 + ε ) ) \delta=\varepsilon/(k(1+\varepsilon)) δ = ε / ( k ( 1 + ε )) . A weighted δ \delta δ -net then contains an element u ∈ O i ∩ W u\in O_i\cap W u ∈ O i ∩ W ; since the algorithm tries every pair ( i , u ) (i,u) ( i , u ) , one recursive branch adds u u u to the corresponding skeleton and remains consistent with the fixed optimum. Each element added to one skeleton produces a new semi-ladder rung, so every skeleton has size at most d d d and the recursion depth is at most k d kd k d . When w ( W ) w(W) w ( W ) is small, arbitrary eligible sets already give the required approximation.
By Observation 2.6 , every K d , d K_{d,d} K d , d -free graph has semi-ladder index less than 2 d 2d 2 d . Consequently, Theorem 5.4 also gives an EPAS for weighted K d , d K_{d,d} K d , d -free Min-UnCoverage. For the unit-weight case, we additionally give a specialized algorithm with the improved running time ( d k / ε ) O ( d k ) N O ( 1 ) (dk/\varepsilon)^{O(dk)}N^{O(1)} ( d k / ε ) O ( d k ) N O ( 1 ) (Theorem A.5 ).
These graph-based positive results rely on the monotonicity of coverage and do not extend to general CNF formulas. Unless FPT = W[1 ] , Min-Unsat SAT and Min-Unsat CSP admit no finite-factor FPT approximation even on unweighted K 3 , 3 K_{3,3} K 3 , 3 -free instances and, separately, on unweighted instances of semi-ladder index at most four (Theorem 4.3 ). Under ETH, no such approximation runs in f ( k , d ) N o ( k + d ) f(k,d)N^{o(k+d)} f ( k , d ) N o ( k + d ) time for any computable function f f f .
Bounded VC dimension. We compare the preceding graph restrictions with bounded VC dimension. Badanidiyuru et al. gave an EPAS for Maximum Coverage on set systems of bounded VC dimension [3 ] . The corresponding residual objectives behave differently. Bringmann et al. proved that Hitting Set is W[1 ] -hard even when both its primal and dual VC dimensions are at most two [5 ] . Dualizing their instances and using the fact that any finite-factor approximation must distinguish optimum zero from positive optimum (Proposition 2.8 ) shows that, unless FPT = W[1 ] , none of Min-UnCoverage, Min-Unsat SAT, and Min-Unsat CSP admits a finite-factor FPT approximation on unweighted instances of VC dimension at most two (Corollary 2.10 ). Thus, bounded semi-ladder index suffices for approximating the coverage residual, whereas bounded VC dimension alone does not.
Table 1 summarizes the FPT approximability landscape for the residual-minimization objective (the uncovered or unsatisfied weight) under the cardinality bound k k k , with parameter k + d k+d k + d , for each incidence restriction considered in the paper. Positive results are for positive rational weights unless stated otherwise, whereas all hardness results already hold for unweighted instances. Each hardness entry rules out every finite-factor FPT approximation parameterized by k + d k+d k + d , unless FPT = W[1 ] .
Table 1. Residual-objective results for parameter k + d k+d k + d . “This paper” marks results proved here; “Consequence” marks an immediate corollary or specialization; “Adaptation” marks a weighted deterministic extension of a cited algorithm; and “External” marks cited work. All hardness entries use the zero-optimum barrier and do not give a gap between two positive optimum values. Here N N N is the input size and L = ( d 2 k / ε ) log ( 2 k / ε ) L=(d^2k/\varepsilon)\log(2k/\varepsilon) L = ( d 2 k / ε ) log ( 2 k / ε ) . In the two one-sided degree rows, the first line gives the SAT/CSP restriction and the second line gives the corresponding coverage restriction.
Approximating the cardinality bound. We finally consider relaxing the cardinality bound while preserving a prescribed upper bound on the uncovered or unsatisfied weight. As discussed above, the maximization and residual-minimization formulations are equivalent once the target is fixed. On the coverage side, Jain et al. [21 ] showed that, on K d , d K_{d,d} K d , d -free incidence graphs, a target attainable with k k k sets can be attained in FPT time with at most k + 1 k+1 k + 1 sets. Kundu et al. [23 ] extended this additive-one guarantee to weighted Partial Set Cover on incidence graphs of bounded semi-ladder index. Their result therefore also applies to the biclique-free and one-sided degree-bounded coverage classes considered here. For bounded set size, our exact FPT algorithm attains the target without increasing the cardinality bound. In contrast, bounded VC dimension alone does not permit an additive-one guarantee: for every fixed δ > 0 \delta>0 δ > 0 , Partial Set Cover admits no parameterized ( 2 − δ ) (2-\delta) ( 2 − δ ) -approximation of the cardinality bound, unless FPT = W[1 ] , even on set systems of VC dimension seven [23 ] .
For Min-Unsat SAT and Min-Unsat CSP, the separation is stronger: all of our hardness results below already hold for unweighted instances. Unless FPT = W[1 ] , for every computable function g ( k , d ) ≥ k g(k,d)\ge k g ( k , d ) ≥ k , no FPT algorithm can preserve a prescribed upper bound on the unsatisfied weight while replacing the cardinality bound k k k by g ( k , d ) g(k,d) g ( k , d ) . This holds for clause or constraint arity three (Theorem 6.3), under bounded variable frequency (Theorem 6.5), and consequently on K 3 , 3 K_{3,3} K 3 , 3 -free incidence graphs, on incidence graphs of semi-ladder index at most four, and on incidence systems of VC dimension at most two (Corollary 6.6). These reductions establish a stronger gap than the failure of any particular approximation factor: a yes-instance has an assignment of Hamming weight at most k k k attaining the prescribed bound, whereas in a no-instance no assignment, regardless of its Hamming weight, attains it. Equivalently, let CC-Max-SAT denote the problem of maximizing the total weight of satisfied clauses subject to a bound on the Hamming weight. Our results give a negative answer to its corresponding “optimizing k k k ” question under all the structural restrictions considered here: even an arbitrary computable relaxation of the cardinality bound is impossible. This contrasts with the additive-one FPT guarantee for Partial Set Cover, proved by Jain et al. [21 ] on K d , d K_{d,d} K d , d -free incidence graphs and extended by Kundu et al. [23 ] to weighted instances of bounded semi-ladder index. Our lower bounds thereby complete the corresponding picture on the satisfaction side of the target-preserving cardinality-approximation question initiated by Jain et al.
Table 2 summarizes the results for relaxing the cardinality bound while preserving the objective target. The coverage column states how many sets suffice when k k k sets attain the target. The SAT/CSP column records the corresponding cardinality-approximation hardness. Every hardness entry in the SAT/CSP column holds unless FPT = W[1 ] .
Table 2. Results for relaxing the cardinality bound while preserving the bound on uncovered or unsatisfied weight. The parameter is k k k unless stated otherwise; all SAT/CSP hardness results hold for unweighted instances. In the first two rows, the restrictions before and after the semicolon refer to SAT/CSP and coverage, respectively.
Applications of the Min-Unsat CSP formulation. The CSP formulation also captures cardinality-constrained selection problems in which covering some elements incurs a penalty. Such objectives are nonmonotone and therefore fall outside standard coverage maximization. We illustrate this with two related examples.
An instance of Positive-Negative Partial Set Cover consists of disjoint sets P P P and N N N of positive and negative elements, respectively, and a family S ⊆ 2 P ⊎ N \mathcal{S} \subseteq2^{P \uplus N} S ⊆ 2 P ⊎ N . The objective is to choose a subfamily T ⊆ S \mathcal{T} \subseteq\mathcal{S} T ⊆ S minimizing the number of uncovered positive elements plus the number of covered negative elements. We consider the weighted, cardinality-constrained version, in which all elements have positive rational weights and ∣ T ∣ ≤ k |\mathcal{T}| \le k ∣ T ∣ ≤ k .
An instance of Red-Blue Set Cover consists of disjoint sets R R R and B B B of red and blue elements, respectively, and a family S ⊆ 2 R ⊎ B \mathcal{S} \subseteq2^{R \uplus B} S ⊆ 2 R ⊎ B . Its objective is to cover every blue element while minimizing the number of covered red elements. In the weighted, cardinality-constrained version considered here, red elements have positive rational weights and at most k k k sets may be selected.
Carr et al. introduced Red-Blue Set Cover [6 ] . Peleg subsequently gave a 2 m log ∣ B ∣ 2\sqrt{m\log|B|} 2 m log ∣ B ∣ -approximation, where m = ∣ S ∣ m = |\mathcal{S}| m = ∣ S ∣ [29 ] . Chlamtáč et al. obtained an O ( m 1 / 3 log 4 / 3 ∣ R ∣ log ∣ B ∣ ) O(m^{1/3}\log^{4/3}|R|\log|B|) O ( m 1/3 log 4/3 ∣ R ∣ log ∣ B ∣ ) -approximation [9 ] . Miettinen introduced Positive-Negative Partial Set Cover and gave polynomial-time reductions in both directions between it and Red–Blue Set Cover, thereby transferring approximation guarantees and hardness results between the two problems. For the original unweighted problem without a cardinality bound, he also proved that, for every ε > 0 \varepsilon> 0 ε > 0 , no polynomial-time 2 ( log ∣ P ∣ ) 1 − ε 2^{(\log|P|)^{1-\varepsilon}} 2 ( l o g ∣ P ∣ ) 1 − ε -approximation exists unless P = NP [27 ] .
We next encode the weighted, cardinality-constrained variants as Min-Unsat CSP instances. For every set S ∈ S S \in\mathcal{S} S ∈ S , introduce a variable x S x_S x S , where x S = 1 x_S = 1 x S = 1 means that S S S is selected. A positive element p p p is represented by the constraint
C p = ⋁ S ∋ p x S C_p = \bigvee_{S \ni p} x_S C p = S ∋ p ⋁ x S
which is unsatisfied precisely when p p p is uncovered. A negative element n n n is represented by
C n = ⋀ S ∋ n ¬ x S C_n = \bigwedge_{S \ni n} \neg x_S C n = S ∋ n ⋀ ¬ x S
which is unsatisfied precisely when n n n is covered. Give each constraint the weight of its corresponding element. Thus, the total weight of the unsatisfied constraints is exactly the total weight of the uncovered positive elements and the covered negative elements, that is, the objective value of the corresponding Positive–Negative Partial Set Cover solution.
For the weighted, cardinality-constrained Red–Blue Set Cover encoding, in which blue elements play the role of positive elements and red elements play the role of negative elements, fix the requested accuracy ε > 0 \varepsilon> 0 ε > 0 , let W R W_R W R be the total weight of the red elements, and give every blue constraint a rational weight M > ( 1 + ε ) W R M > (1+\varepsilon)W_R M > ( 1 + ε ) W R ; red constraints retain their original weights. Suppose that all blue elements can be covered with at most k k k sets. The optimum CSP value is then at most W R W_R W R , whereas any assignment leaving a blue element uncovered has value at least M M M . Consequently, both an optimum solution and every ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate solution cover all blue elements, and the CSP objective on such solutions is exactly the covered red weight. This gives the desired ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximation for every feasible instance. Because selecting an additional set can violate a negative-element constraint, these encodings require general Min-Unsat CSP rather than Min-UnCoverage.
In these encodings, bounded arity has a direct interpretation in the original problems. For Positive–Negative Partial Set Cover and Red–Blue Set Cover, the constraint associated with an element has arity equal to the number of sets containing that element. Hence, arity at most d d d means that every ground element belongs to at most d d d sets. Our bounded-arity EPAS therefore applies directly under this restriction.
Bounded set size alone gives a different picture for the nonmonotone red–blue objective. For the unweighted decision version, called Generalized Red–Blue Set Cover, Ashok et al. proved W[1 ] -hardness parameterized by the number of selected sets and the red budget even when every set has size three and contains at least two red elements. They also gave a 2 O ( d k ) N O ( 1 ) 2^{O(dk)}N^{O(1)} 2 O ( d k ) N O ( 1 ) -time exact algorithm when every set contains at most one red element and at most d d d blue elements [2 ] . This contrast explains why the exact bounded-set-size result in Proposition B.1 is specific to the monotone coverage objective.
Related work. The survey of Feldmann et al. calls the unit-weight version of our coverage objective Min k k k -Uncovered, observes that it is not approximable on unrestricted set systems, and records the randomized bounded-frequency scheme as Theorem 2.1 [16 Section 4.2.3] . In the original analysis, Skowron and Faliszewski call the problem MinNonCovered and prove the scheme in their Theorem 4.5 [31 ] . They also record in their Table 1 that exact optimization is W[1 ] -complete for every fixed upper frequency bound at least two when parameterized by k k k . When the permitted number ℓ \ell ℓ of uncovered elements is the parameter, the problem is para-NP-complete even under bounded element frequency; for unrestricted set systems, it is W[2 ] -complete for the joint parameter ( k , ℓ ) (k,\ell) ( k , ℓ ) .
For the graph case, which has ground-element frequency two, Maximum Partial Vertex Cover is W[1 ] -complete when parameterized by k k k [18 ] . Damaschke studied the equivalent problem of selecting at most k k k vertices while leaving at most ℓ \ell ℓ edges uncovered. He gave exact FPT branching algorithms parameterized by k + ℓ k+\ell k + ℓ [11 ] . These algorithms use the permitted number of uncovered elements as an additional parameter and do not give an approximation parameterized only by k k k .
The semi-ladder class and terminology originate with Fabiański et al. [14 ] . Guillemot subsequently studied Set Cover on precisely this class, adapting ideas of Langerman and Morin [24 ] to obtain FPT and kernelization algorithms together with a matching compression lower bound [17 ] . This exact-cover work is a structural predecessor of our semi-ladder result. Our objective is different: we permit uncovered elements and seek a multiplicative approximation of their minimum total weight without taking that weight as a parameter. Kundu et al. [23 ] subsequently identified a related boundary for weighted Partial Set Cover. They showed that bounded semi-ladder index permits an FPT algorithm to preserve a coverage target with k + 1 k+1 k + 1 sets whenever k k k sets suffice. Conversely, for every fixed δ > 0 \delta> 0 δ > 0 , they ruled out a parameterized ( 2 − δ ) (2-\delta) ( 2 − δ ) -approximation on set systems of VC dimension seven unless FPT = W[1 ] . They also developed the skeleton framework, branching idea, and weighted-net bounds used in our objective-value approximation; their construction explicitly builds on Guillemot’s FPT routine [17 ] .
For broader background on approximation in parameterized complexity, we refer to Feldmann et al. [16 ] . Jain et al. gave approximation schemes for cardinality-constrained Max k k k -Weight SAT and Maximum Coverage on biclique-free incidence systems [21 ] . Manurangsi subsequently obtained an improved deterministic scheme and an approximate kernel for Max k k k -Weight SAT [26 ] . Recent work also gives reductions between satisfaction and coverage in the presence of global and matroid constraints [19 ] . Inamdar et al. further obtained parameterized approximation schemes for connectivity-constrained Maximum Coverage on K d , d K_{d,d} K d , d -free incidence graphs [20 ] . Those results maximize the number of satisfied clauses or covered elements and therefore do not directly control the small complementary objective studied here. CSPs with global cardinality constraints have also been studied through semidefinite programming hierarchies [30 ] .
Finally, our formulation should not be confused with Boolean MinCSP as studied in the constraint-deletion literature [12 , 22 ] . There, the parameter bounds the number or total weight of constraints that may be violated, so the input is required to be close to satisfiable. Here the parameter k k k instead bounds the Hamming weight of the assignment; the number of violated constraints is unbounded and is the objective being minimized.
Organization. Section 2 introduces the problems and the relevant incidence parameters. Section 3 presents an EPAS for bounded-arity Min-Unsat CSP, while Section 4 establishes hardness results for Min-Unsat SAT and Min-Unsat CSP under biclique-freeness, bounded semi-ladder index, and bounded variable frequency. In contrast, Section 5 develops an EPAS for Min-Uncoverage on instances of bounded semi-ladder index, including its biclique-free consequence. Section 6 investigates the alternative approximation of the cardinality bound and completes the landscape for all three problems under each of the considered restrictions. Section 7 summarizes the resulting landscape. Finally, the appendices contain a specialized EPAS for unit-weight biclique-free instances and an exact algorithm for weighted Min-Uncoverage with bounded set size.
Preliminaries
A Boolean constraint is a pair C = ( scope ( C ) , R C ) C=(\operatorname{scope}(C),R_C) C = ( scope ( C ) , R C ) , where the scope is an ordered tuple of distinct variables and R C ⊆ { 0 , 1 } ∣ scope ( C ) ∣ R_C \subseteq\{0,1\}^{|\operatorname{scope}(C)|} R C ⊆ { 0 , 1 } ∣ scope ( C ) ∣ is a relation. The assignment τ \tau τ satisfies C C C when its restriction to the ordered scope, viewed as a tuple in { 0 , 1 } ∣ scope ( C ) ∣ \{0,1\}^{|\operatorname{scope}(C)|} { 0 , 1 } ∣ scope ( C ) ∣ , belongs to R C R_C R C . A weighted Boolean CSP instance is a triple ( X , C , w ) (X,\mathcal{C},w) ( X , C , w ) consisting of variables, a collection of constraints, and a weight function w : C → Q > 0 w: \mathcal{C} \to\mathbb{Q}_{>0} w : C → Q > 0 . The arity of the instance is the maximum scope size. A literal is a Boolean variable or its negation. A clause is a disjunction of literals, and a CNF formula is a conjunction of clauses. We remove repeated literals and discard tautological clauses, which does not change the unsatisfied weight of any assignment. We represent each constraint relation extensionally by listing either its satisfying tuples or its falsifying tuples, together with a bit indicating which list is used. Thus, a clause is represented by its unique falsifying tuple, making SAT a syntactic special case of Boolean CSP. An arity-d d d relation has at most 2 d 2^d 2 d tuples, so this representation is compatible with the parameterized running times below.
Definition 2.1 (Min-Unsat CSP and Min-Unsat SAT). Given a weighted Boolean CSP instance ( X , C , w ) (X,\mathcal{C},w) ( X , C , w ) and a nonnegative integer k k k , the objective is to find an assignment τ \tau τ minimizing
unsat C , w ( τ ) = ∑ C ∈ C τ does not satisfy C w ( C ) . \operatorname{unsat}_{\mathcal{C},w}(\tau)=\sum_{\substack{C\in\mathcal{C}\\ \tau\text{ does not satisfy }C}}w(C). unsat C , w ( τ ) = C ∈ C τ does not satisfy C ∑ w ( C ) . The assignment must have Hamming weight at most k k k , where its Hamming weight is ∣ { x ∈ X : τ ( x ) = 1 } ∣ |\{x\in X:\tau(x)=1\}| ∣ { x ∈ X : τ ( x ) = 1 } ∣ . For D ⊆ C D\subseteq\mathcal{C} D ⊆ C , write w ( D ) = ∑ C ∈ D w ( C ) w(D)=\sum_{C\in D}w(C) w ( D ) = ∑ C ∈ D w ( C ) . If I = ( X , C , w ) I=(X,\mathcal{C},w) I = ( X , C , w ) , we also write unsat I ( τ ) \operatorname{unsat}_I(\tau) unsat I ( τ ) for unsat C , w ( τ ) \operatorname{unsat}_{\mathcal{C},w}(\tau) unsat C , w ( τ ) . When every constraint is a clause of a CNF formula, the problem is Min-Unsat SAT. An instance is unweighted when every constraint or clause has weight one.
Definition 2.2 (Min-UnCoverage). An instance is a tuple I = ( U , S , w , k ) I=(U,\mathcal{S},w,k) I = ( U , S , w , k ) , where U U U is a set of ground elements, S ⊆ 2 U \mathcal{S}\subseteq2^U S ⊆ 2 U is a family of sets, w : U → Q > 0 w:U\to\mathbb{Q}_{>0} w : U → Q > 0 is a weight function, and k k k is a nonnegative integer. The objective is to find a subfamily A ⊆ S \mathcal{A}\subseteq\mathcal{S} A ⊆ S with ∣ A ∣ ≤ k |\mathcal{A}|\leq k ∣ A ∣ ≤ k minimizing
miss S , w ( A ) = ∑ u ∈ U ∖ ⋃ S ∈ A S w ( u ) . \operatorname{miss}_{\mathcal{S},w}(\mathcal{A})=\sum_{u\in U\setminus\bigcup_{S\in\mathcal{A}}S}w(u). miss S , w ( A ) = u ∈ U ∖ ⋃ S ∈ A S ∑ w ( u ) . For Y ⊆ U Y\subseteq U Y ⊆ U , write w ( Y ) = ∑ u ∈ Y w ( u ) w(Y)=\sum_{u\in Y}w(u) w ( Y ) = ∑ u ∈ Y w ( u ) . We also write cov S , w ( A ) = w ( U ) − miss S , w ( A ) \operatorname{cov}_{\mathcal{S},w}(\mathcal{A})=w(U)-\operatorname{miss}_{\mathcal{S},w}(\mathcal{A}) cov S , w ( A ) = w ( U ) − miss S , w ( A ) for the total weight of the covered elements. When all ground elements have weight one, the instance is unweighted and we omit w w w from the notation.
Definition 2.3 (Incidence graph). For a CSP instance I = ( X , C , w ) I=(X,\mathcal{C},w) I = ( X , C , w ) , the incidence graph G I G_I G I is the bipartite graph with parts X X X and C \mathcal{C} C . It contains an edge x C xC x C if and only if variable x x x occurs in the scope of constraint C C C . For SAT, the two parts are the variables and clauses, with an edge recording that a variable occurs in a clause. For a coverage instance I = ( U , S , w , k ) I=(U,\mathcal{S},w,k) I = ( U , S , w , k ) , the two parts are the sets S \mathcal{S} S and the ground elements U U U . It contains an edge u S uS u S if and only if u ∈ S u\in S u ∈ S .
Definition 2.4 (VC dimension [32 ] ). Let ( U , F ) (U,\mathcal{F}) ( U , F ) be a set system, where F ⊆ 2 U \mathcal{F}\subseteq2^U F ⊆ 2 U . A set X ⊆ U X\subseteq U X ⊆ U is shattered by F \mathcal{F} F if
{ F ∩ X : F ∈ F } = 2 X . \{F\cap X:F\in\mathcal{F}\}=2^X. { F ∩ X : F ∈ F } = 2 X . The VC dimension of ( U , F ) (U,\mathcal{F}) ( U , F ) is the maximum cardinality of a set shattered by F \mathcal{F} F ; it is also called the primal VC dimension . The dual set system is ( F , F ∗ ) (\mathcal{F},\mathcal{F}^*) ( F , F ∗ ) , where
F ∗ : = { { F ∈ F : u ∈ F } : u ∈ U } . \mathcal{F}^*:=\{\{F\in\mathcal{F}:u\in F\}:u\in U\}. F ∗ := {{ F ∈ F : u ∈ F } : u ∈ U } . Its VC dimension is the dual VC dimension of ( U , F ) (U,\mathcal{F}) ( U , F ) .
For a bipartite incidence graph G = ( A ∪ ˙ B , E ) G=(A\mathbin{\dot\cup}B,E) G = ( A ∪ ˙ B , E ) , where A A A contains the selectable objects, let
N A ( G ) : = { N G ( a ) : a ∈ A } ⊆ 2 B , N B ( G ) : = { N G ( b ) : b ∈ B } ⊆ 2 A . \mathcal{N}_A(G):=\{N_G(a):a\in A\}\subseteq2^B,\qquad\mathcal{N}_B(G):=\{N_G(b):b\in B\}\subseteq2^A. N A ( G ) := { N G ( a ) : a ∈ A } ⊆ 2 B , N B ( G ) := { N G ( b ) : b ∈ B } ⊆ 2 A . The primal and dual VC dimensions of G G G are the VC dimensions of ( B , N A ( G ) ) (B,\mathcal{N}_A(G)) ( B , N A ( G )) and ( A , N B ( G ) ) (A,\mathcal{N}_B(G)) ( A , N B ( G )) , respectively. Unless stated otherwise, the VC dimension of G G G , and hence of the corresponding instance, means its primal VC dimension.
Definition 2.5 (Semi-ladder index [14 ] ). Let G = ( A ∪ ˙ B , E ) G=(A\mathbin{\dot\cup}B,E) G = ( A ∪ ˙ B , E ) be a bipartite graph. A semi-ladder of order ℓ \ell ℓ consists of vertices a 1 , … , a ℓ ∈ A a_1,\ldots,a_\ell\in A a 1 , … , a ℓ ∈ A and b 1 , … , b ℓ ∈ B b_1,\ldots,b_\ell\in B b 1 , … , b ℓ ∈ B such that
a i b i ∉ E for every i ∈ [ ℓ ] , a i b j ∈ E whenever j < i . a_i b_i\notin E \quad\text{for every }i\in[\ell],\qquad a_i b_j\in E \quad\text{whenever }j<i. a i b i ∈ / E for every i ∈ [ ℓ ] , a i b j ∈ E whenever j < i . There is no condition on a i b j a_i b_j a i b j when j > i j>i j > i . The semi-ladder index of G G G is the maximum order of a semi-ladder in G G G .
An instance is K d , d K_{d,d} K d , d -free if its incidence graph contains no K d , d K_{d,d} K d , d as a subgraph.
Observation 2.6. For every d ≥ 1 d\ge1 d ≥ 1 , every K d , d K_{d,d} K d , d -free bipartite graph has semi-ladder index less than 2 d 2d 2 d .
Proof. If a 1 , … , a 2 d a_1,\ldots,a_{2d} a 1 , … , a 2 d and b 1 , … , b 2 d b_1,\ldots,b_{2d} b 1 , … , b 2 d form a semi-ladder, then a d + 1 , … , a 2 d a_{d+1},\ldots,a_{2d} a d + 1 , … , a 2 d and b 1 , … , b d b_1,\ldots,b_d b 1 , … , b d induce all edges of a K d , d K_{d,d} K d , d , since j ≤ d < i j\le d<i j ≤ d < i for every selected pair. Thus a K d , d K_{d,d} K d , d -free graph has no semi-ladder of order 2 d 2d 2 d . Since every prefix of a semi-ladder is itself a semi-ladder, it has no semi-ladder of order at least 2 d 2d 2 d , and hence its semi-ladder index is less than 2 d 2d 2 d .
Observation 2.7 (Kundu et al.). The VC dimension of a bipartite incidence graph is at most its semi-ladder index [23 Lemma 8.6] .
Proof. Let X = { b 1 , … , b ℓ } X=\{b_1,\ldots,b_\ell\} X = { b 1 , … , b ℓ } be shattered. For each i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] , choose a i a_i a i whose neighborhood satisfies N ( a i ) ∩ X = { b 1 , … , b i − 1 } N(a_i)\cap X=\{b_1,\ldots,b_{i-1}\} N ( a i ) ∩ X = { b 1 , … , b i − 1 } . Then a i b i a_i b_i a i b i is a nonedge and a i b j a_i b_j a i b j is an edge whenever j < i j<i j < i , so these vertices form a semi-ladder of order ℓ \ell ℓ .
The degree of a clause or constraint is its arity, while the degree of a ground element is its frequency. The degree of a variable is its variable frequency, while the degree of a set is its size. Throughout, d d d denotes the stated structural bound: a degree bound, the size of an excluded biclique, or a bound on the semi-ladder index or VC dimension. It is included in the parameter k + d k+d k + d and is not assumed to be an absolute constant unless stated otherwise.
For an instance I I I and an explicit budget q q q , let OPT ( I , q ) \operatorname{OPT}(I,q) OPT ( I , q ) be its minimum objective value among solutions using at most q q q selectable objects: sets in a coverage instance or variables set to one in a SAT or CSP instance. For a coverage instance I = ( U , S , w , k ) I=(U,S,w,k) I = ( U , S , w , k ) , we use the complementary notation
OPT m i s s ( I ) : = OPT ( I , k ) and OPT c o v ( I ) : = w ( U ) − OPT m i s s ( I ) . \operatorname{OPT}_{\mathrm{miss}}(I):=\operatorname{OPT}(I,k)
\quad\text{and}\quad
\operatorname{OPT}_{\mathrm{cov}}(I):=w(U)-\operatorname{OPT}_{\mathrm{miss}}(I). OPT miss ( I ) := OPT ( I , k ) and OPT cov ( I ) := w ( U ) − OPT miss ( I ) .
An efficient parameterized approximation scheme (EPAS) for one of the restricted problems takes ε > 0 \varepsilon>0 ε > 0 and returns a feasible solution of value at most ( 1 + ε ) OPT ( I , k ) (1+\varepsilon)\operatorname{OPT}(I,k) ( 1 + ε ) OPT ( I , k ) . Its running time is
f ( k , d , 1 / ε ) N O ( 1 ) f(k,d,1/\varepsilon)N^{O(1)} f ( k , d , 1/ ε ) N O ( 1 )
for a computable function f f f , where N N N denotes the input encoding size. More generally, a finite-factor FPT approximation parameterized by p p p runs in g ( p ) N O ( 1 ) g(p)N^{O(1)} g ( p ) N O ( 1 ) time and returns a feasible solution of value at most c ( p ) OPT ( I , k ) c(p)\operatorname{OPT}(I,k) c ( p ) OPT ( I , k ) , for some computable functions g g g and c : N → [ 1 , ∞ ) c:\mathbb{N}\to[1,\infty) c : N → [ 1 , ∞ ) . Thus its approximation factor may depend on the parameter but not on the input size. All rational weights are encoded in binary and are included in N N N . Arithmetic and comparisons on these weights therefore take time polynomial in the input size.
The following elementary proposition will be used in the hardness results.
Proposition 2.8 (Zero-optimum barrier). Let W ∈ { W [ 1 ] , W [ 2 ] } \mathcal{W}\in\{W[1],W[2]\} W ∈ { W [ 1 ] , W [ 2 ]} . Suppose it is W \mathcal{W} W -hard, parameterized by p p p , to decide whether some feasible solution covers every ground element or satisfies every constraint. Unless F P T = W \mathrm{FPT}=\mathcal{W} FPT = W , the corresponding minimization problem has no FPT c ( p ) c(p) c ( p ) -approximation parameterized by p p p for any computable function c : N → [ 1 , ∞ ) c:\mathbb{N}\to[1,\infty) c : N → [ 1 , ∞ ) .
Proof. On a yes-instance the optimum is zero, so every solution satisfying a finite multiplicative approximation guarantee must also have value zero. On a no-instance every feasible solution has positive value. Running the approximation algorithm and testing whether its output has value zero would therefore decide the W W W -hard problem in FPT time. □
All objective-value hardness proofs in this paper use this zero-optimum argument. They distinguish optimum zero from positive optimum. These proofs do not establish hardness under the promise that the optimum is positive, or a multiplicative gap between two positive optimum values.
Combining Proposition 2.8 with the standard W [ 2 ] W[2] W [ 2 ] -hardness of Set Cover parameterized by the solution size [10 ] yields the following folklore consequence.
Corollary 2.9 (Folklore). Unless FPT = W [ 2 ] W[2] W [ 2 ] , none of Min-UnCoverage, Min-Unsat SAT, and Min-Unsat CSP admits a finite-factor FPT approximation parameterized by k k k , even when every ground element, clause, or constraint has weight one.
Proof. An instance of Set Cover has a cover of size at most k k k if and only if the corresponding Min-UnCoverage instance has optimum zero. For each ground element u u u , the monotone clause ⋁ S ∈ S : u ∈ S x S \bigvee_{S\in\mathcal{S}:u\in S} x_S ⋁ S ∈ S : u ∈ S x S is satisfied exactly when the selected sets cover u u u . Thus coverage is a special case of monotone SAT, and SAT is a special case of Boolean CSP. □
The following is another folklore consequence of Proposition 2.8 , now combined with the bounded-VC-dimension hardness of Bringmann et al. [5 ] .
Corollary 2.10 (Folklore). Unless FPT = W [ 1 ] W[1] W [ 1 ] , none of Min-UnCoverage, Min-Unsat SAT, and Min-Unsat CSP admits a finite-factor FPT approximation parameterized by k + d k+d k + d on incidence systems of VC dimension at most d d d , even when d = 2 d=2 d = 2 and every ground element, clause, or constraint has weight one.
Proof. Bringmann et al. proved that Hitting Set is W [ 1 ] W[1] W [ 1 ] -hard parameterized by the solution size even when both the primal and dual VC dimensions are at most two [5 ] . Dualizing such an instance gives a Set Cover instance of VC dimension at most two with the same solution size. By Proposition 2.8 , this rules out a finite-factor FPT approximation for Min-UnCoverage. The monotone-CNF encoding used in the proof of Corollary 2.9 has an incidence graph isomorphic to that of the Set Cover instance: each set S S S becomes a variable x S x_S x S , each element u u u becomes a clause C u C_u C u , and x S x_S x S occurs in C u C_u C u exactly when u ∈ S u\in S u ∈ S . Hence the VC dimension remains at most two, and the same lower bound applies to Min-Unsat SAT and therefore to Min-Unsat CSP. □
An EPAS for Weighted Min-Unsat CSP with Bounded Arity
Fix d ≥ 1 d\ge1 d ≥ 1 and 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 . For a weighted Boolean CSP instance I = ( X , C , w ) I=(X,\mathcal{C},w) I = ( X , C , w ) of arity at most d d d , we write 0 \mathbf{0} 0 for the all-zero assignment on the current variable set and put
Z ( I ) = { C ∈ C : 0 does not satisfy C } , z w ( I ) = ∑ C ∈ Z ( I ) w ( C ) . \mathcal{Z}(I)=\{C\in\mathcal{C}:\mathbf{0}\text{ does not satisfy }C\},\qquad z_w(I)=\sum_{C\in\mathcal{Z}(I)}w(C). Z ( I ) = { C ∈ C : 0 does not satisfy C } , z w ( I ) = C ∈ Z ( I ) ∑ w ( C ) .
For x ∈ X x\in X x ∈ X , define its weighted occurrence in Z ( I ) \mathcal{Z}(I) Z ( I ) by
occ Z ( I ) , w ( x ) = ∑ C ∈ Z ( I ) x ∈ scope ( C ) w ( C ) . \operatorname{occ}_{\mathcal{Z}(I),w}(x)=\sum_{\substack{C\in\mathcal{Z}(I)\\x\in\operatorname{scope}(C)}}w(C). occ Z ( I ) , w ( x ) = C ∈ Z ( I ) x ∈ scope ( C ) ∑ w ( C ) .
Algorithmic idea. The algorithm first considers the simplest feasible solution: assign zero to every variable of the current instance. This solution violates total constraint weight z w ( I ) z_w(I) z w ( I ) . The initial call has budget q = k q = k q = k ; in every later call, q q q is the remaining number of variables that may still be set to one. To look for a better solution, the algorithm sets a variable x x x to the Boolean value one. This uses one unit of the budget, so it solves the remaining instance recursively with budget q − 1 q - 1 q − 1 . Trying every variable would be too expensive, so we use the constraints in Z ( I ) \mathcal{Z}(I) Z ( I ) to select a small set of variables. Define
θ ( I , q ) = ε ( 1 + ε ) q z w ( I ) and H ( I , q ) = { x ∈ X : occ Z ( I ) , w ( x ) > θ ( I , q ) } . \theta(I,q) = \frac{\varepsilon}{(1+\varepsilon)q}z_w(I)
\qquad\text{and}\qquad
H(I,q) = \{x \in X : \operatorname{occ}_{\mathcal{Z}(I),w}(x) > \theta(I,q)\}. θ ( I , q ) = ( 1 + ε ) q ε z w ( I ) and H ( I , q ) = { x ∈ X : occ Z ( I ) , w ( x ) > θ ( I , q )} .
The algorithm tries setting each variable in H ( I , q ) H(I,q) H ( I , q ) to one. If the all-zero solution is not a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximation, let R \mathcal{R} R be the constraints in Z ( I ) \mathcal{Z}(I) Z ( I ) that an optimum assignment satisfies. Their total weight satisfies w ( R ) ≥ z w ( I ) − OPT ( I , q ) > ε z w ( I ) / ( 1 + ε ) w(\mathcal{R}) \ge z_w(I) - \operatorname{OPT}(I,q) > \varepsilon z_w(I)/(1+\varepsilon) w ( R ) ≥ z w ( I ) − OPT ( I , q ) > ε z w ( I ) / ( 1 + ε ) . Each constraint in R \mathcal{R} R contains a variable that the optimum sets to one. Charge its weight to one such variable. Since the optimum sets at most q q q variables to one, some variable receives total charge at least w ( R ) / q > θ ( I , q ) w(\mathcal{R})/q > \theta(I,q) w ( R ) / q > θ ( I , q ) . Its weighted occurrence is at least this charge, so it belongs to H ( I , q ) H(I,q) H ( I , q ) . On the other hand, arity at most d d d implies ∣ H ( I , q ) ∣ < d ( 1 + ε ) q / ε |H(I,q)| < d(1+\varepsilon)q/\varepsilon ∣ H ( I , q ) ∣ < d ( 1 + ε ) q / ε . Thus the algorithm tries only a bounded number of variables, including an optimum choice whenever the all-zero solution is not good enough, and returns the best solution found. The residual construction below defines the instance obtained after setting x = 1 x = 1 x = 1 , and Lemmas 3.1 and 3.2 prove the two stated properties of H ( I , q ) H(I,q) H ( I , q ) .
Residual instances. Fixing x = 1 x = 1 x = 1 restricts every constraint containing x x x . Formally, delete the coordinate of x x x from its scope. If the relation is represented by its satisfying tuples, retain the projected tuples whose extension by a one in that coordinate satisfies the original relation. If it is represented by its falsifying tuples, apply the same operation to the falsifying list and retain the complement representation. Constraints with an empty scope are retained as constant true or constant false constraints, and every residual constraint retains its weight. Denote the resulting instance by I [ x ← 1 ] I[x \leftarrow1] I [ x ← 1 ] . Every assignment σ \sigma σ of the residual variables satisfies
unsat I ( σ ∪ { x ↦ 1 } ) = unsat I [ x ← 1 ] ( σ ) . (1) \operatorname{unsat}_{I}(\sigma\cup\{x \mapsto1\}) = \operatorname{unsat}_{I[x \leftarrow1]}(\sigma). \tag*{(1)} unsat I ( σ ∪ { x ↦ 1 }) = unsat I [ x ← 1 ] ( σ ) . (1)
This restriction operation does not increase arity and is polynomial in the explicit input representation.
The following pseudocode implements this search.
Algorithm 1 Min-Unsat-d-CSP(I, q, ε)
Require: A weighted Boolean CSP instance I = (X, C, w) of arity at most d, a remaining
budget q, and ε ∈ (0, 1].
Ensure: An assignment of Hamming weight at most q.
1: τ_best ← 0
2: if q = 0 or z_w(I) = 0 then
3: return τ_best
4: θ ← εz_w(I)/((1 + ε)q)
5: H ← {x ∈ X : occ_{Z(I),w}(x) > θ}
6: for all x ∈ H do
7: σ_x ← Min-Unsat-d-CSP(I[x ← 1], q − 1, ε)
8: τ_x ← σ_x ∪ {x ↦ 1}
9: if unsat_I(τ_x) < unsat_I(τ_best) then
10: τ_best ← τ_x
11: return τ_best
We now prove that the branching set contains an optimum choice when branching is necessary and that its size is bounded.
Lemma 3.1 (An optimum branch exists). Let I = ( X , C , w ) I=(X,\mathcal{C},w) I = ( X , C , w ) be a weighted Boolean CSP instance of arity at most d d d , let q ≥ 1 q \ge1 q ≥ 1 , and let τ ∗ \tau^* τ ∗ be an optimum assignment of Hamming weight at most q q q . If z w ( I ) > ( 1 + ε ) OPT ( I , q ) z_w(I)>(1+\varepsilon)\operatorname{OPT}(I,q) z w ( I ) > ( 1 + ε ) OPT ( I , q ) , then { x ∈ X : τ ∗ ( x ) = 1 } ∩ H ( I , q ) ≠ ∅ \{x\in X:\tau^*(x)=1\}\cap H(I,q)\ne\varnothing { x ∈ X : τ ∗ ( x ) = 1 } ∩ H ( I , q ) = ∅ .
Proof. The constraints in Z ( I ) \mathcal{Z}(I) Z ( I ) have total weight z w ( I ) z_w(I) z w ( I ) , and τ ∗ \tau^* τ ∗ violates constraints of total weight at most OPT ( I , q ) \operatorname{OPT}(I,q) OPT ( I , q ) . Therefore, the constraints in Z ( I ) \mathcal{Z}(I) Z ( I ) that it satisfies have total weight greater than ε z w ( I ) / ( 1 + ε ) \varepsilon z_w(I)/(1+\varepsilon) ε z w ( I ) / ( 1 + ε ) . For each of these satisfied constraints, choose a variable in its scope that τ ∗ \tau^* τ ∗ sets to one. Such a variable must exist; otherwise, τ ∗ \tau^* τ ∗ and the all-zero assignment would assign the same tuple to the constraint, and both would violate it. Associate the weight of each such constraint with one chosen variable. Since τ ∗ \tau^* τ ∗ sets at most q q q variables to one, some variable receives total weight greater than ε z w ( I ) / ( ( 1 + ε ) q ) = θ ( I , q ) \varepsilon z_w(I)/((1+\varepsilon)q)=\theta(I,q) ε z w ( I ) / (( 1 + ε ) q ) = θ ( I , q ) . Its weighted occurrence is at least this value. Hence, this variable belongs to both { x ∈ X : τ ∗ ( x ) = 1 } \{x\in X:\tau^*(x)=1\} { x ∈ X : τ ∗ ( x ) = 1 } and H ( I , q ) H(I,q) H ( I , q ) . □ \square □
Lemma 3.2 (The branching set is small). For every weighted Boolean CSP instance I = ( X , C , w ) I=(X,\mathcal{C},w) I = ( X , C , w ) of arity at most d d d and every q ≥ 1 q\ge1 q ≥ 1 , ∣ H ( I , q ) ∣ < d ( 1 + ε ) q / ε |H(I,q)|<d(1+\varepsilon)q/\varepsilon ∣ H ( I , q ) ∣ < d ( 1 + ε ) q / ε .
Proof. If z w ( I ) = 0 z_w(I)=0 z w ( I ) = 0 , then every weighted occurrence is zero, so H ( I , q ) = ∅ H(I,q)=\varnothing H ( I , q ) = ∅ and the claim follows. Assume henceforth that z w ( I ) > 0 z_w(I)>0 z w ( I ) > 0 . Each constraint in Z ( I ) \mathcal{Z}(I) Z ( I ) contains at most d d d variables. Therefore, ∑ x ∈ X occ Z ( I ) , w ( x ) ≤ d z w ( I ) \sum_{x\in X}\operatorname{occ}_{\mathcal{Z}(I),w}(x)\le d z_w(I) ∑ x ∈ X occ Z ( I ) , w ( x ) ≤ d z w ( I ) . Moreover, every x ∈ H ( I , q ) x\in H(I,q) x ∈ H ( I , q ) satisfies occ Z ( I ) , w ( x ) > θ ( I , q ) = ε z w ( I ) / ( ( 1 + ε ) q ) \operatorname{occ}_{\mathcal{Z}(I),w}(x)>\theta(I,q)=\varepsilon z_w(I)/((1+\varepsilon)q) occ Z ( I ) , w ( x ) > θ ( I , q ) = ε z w ( I ) / (( 1 + ε ) q ) . Hence, ∣ H ( I , q ) ∣ θ ( I , q ) < ∑ x ∈ X occ Z ( I ) , w ( x ) ≤ d z w ( I ) |H(I,q)|\theta(I,q)<\sum_{x\in X}\operatorname{occ}_{\mathcal{Z}(I),w}(x)\le d z_w(I) ∣ H ( I , q ) ∣ θ ( I , q ) < ∑ x ∈ X occ Z ( I ) , w ( x ) ≤ d z w ( I ) . Substituting the value of θ ( I , q ) \theta(I,q) θ ( I , q ) and rearranging gives ∣ H ( I , q ) ∣ < d ( 1 + ε ) q / ε |H(I,q)|<d(1+\varepsilon)q/\varepsilon ∣ H ( I , q ) ∣ < d ( 1 + ε ) q / ε , as claimed. □ \square □
Lemma 3.3 (Approximation guarantee). For every weighted Boolean CSP instance I I I of arity at most d d d and every q ≥ 0 q\ge0 q ≥ 0 , Algorithm 1 returns an assignment τ \tau τ of Hamming weight at most q q q with unsat I ( τ ) ≤ ( 1 + ε ) OPT ( I , q ) \operatorname{unsat}_I(\tau)\le(1+\varepsilon)\operatorname{OPT}(I,q) unsat I ( τ ) ≤ ( 1 + ε ) OPT ( I , q ) .
Proof. We prove the claim simultaneously for every weighted arity-d d d instance by induction on q q q . For the base case q = 0 q=0 q = 0 , the all-zero assignment is the only feasible assignment, and the algorithm returns it. Now fix q ≥ 1 q\ge1 q ≥ 1 and assume as the induction hypothesis that the claim holds for every weighted arity-d d d instance with budget q − 1 q-1 q − 1 . If z w ( I ) = 0 z_w(I)=0 z w ( I ) = 0 , the all-zero assignment has objective value zero and is therefore optimal, and the algorithm returns it. We may therefore assume that z w ( I ) > 0 z_w(I)>0 z w ( I ) > 0 .
First suppose that z w ( I ) ≤ ( 1 + ε ) OPT ( I , q ) z_w(I)\le(1+\varepsilon)\operatorname{OPT}(I,q) z w ( I ) ≤ ( 1 + ε ) OPT ( I , q ) . The all-zero assignment violates total constraint weight exactly z w ( I ) z_w(I) z w ( I ) , so it satisfies the required approximation guarantee. Since the algorithm returns the best assignment it finds, its output also satisfies this guarantee.
Now suppose that z w ( I ) > ( 1 + ε ) OPT ( I , q ) z_w(I)>(1+\varepsilon)\operatorname{OPT}(I,q) z w ( I ) > ( 1 + ε ) OPT ( I , q ) . By Lemma 3.1, there is a variable x ∗ ∈ H ( I , q ) x^*\in H(I,q) x ∗ ∈ H ( I , q ) that an optimum assignment τ ∗ \tau^* τ ∗ sets to one. The algorithm therefore considers the branch x ∗ = 1 x^*=1 x ∗ = 1 . Restricting τ ∗ \tau^* τ ∗ to the remaining variables gives an assignment of Hamming weight at most q − 1 q-1 q − 1 for I [ x ∗ ← 1 ] I[x^*\leftarrow1] I [ x ∗ ← 1 ] with value OPT ( I , q ) \operatorname{OPT}(I,q) OPT ( I , q ) . Conversely, any better assignment for the residual instance would extend to an assignment for I I I with Hamming weight at most q q q , contradicting the optimality of τ ∗ \tau^* τ ∗ . Thus, the optimum value of the residual instance is OPT ( I , q ) \operatorname{OPT}(I,q) OPT ( I , q ) .
By the induction hypothesis, the recursive call returns an assignment of value at most ( 1 + ε ) OPT ( I , q ) (1+\varepsilon)\operatorname{OPT}(I,q) ( 1 + ε ) OPT ( I , q ) . By (1) , extending this assignment with x ∗ = 1 x^*=1 x ∗ = 1 gives the same value for I I I . Since the algorithm returns the best candidate, the claim follows. □ \square □
Theorem 3.4. For every d ≥ 1 d\ge1 d ≥ 1 , weighted arity-d d d Min-Unsat CSP admits a deterministic EPAS parameterized by k + d k+d k + d . For 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 , its running time is ( d k / ε ) O ( k ) N O ( 1 ) (dk/\varepsilon)^{O(k)}N^{O(1)} ( d k / ε ) O ( k ) N O ( 1 ) .
Proof. It is enough to consider ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] . If ε > 1 \varepsilon>1 ε > 1 , we run the algorithm with ε ′ = 1 \varepsilon'=1 ε ′ = 1 ; the resulting approximation factor of 2 is at most 1 + ε 1+\varepsilon 1 + ε . We start the algorithm with budget q = k q=k q = k , and Lemma 3.3 gives the required approximation guarantee. Each recursive call reduces the remaining budget by one. Since the initial budget is k k k , the recursion has at most k k k levels. Let c = ⌈ d ( 1 + ε ) / ε ⌉ c = \lceil d(1+\varepsilon)/\varepsilon\rceil c = ⌈ d ( 1 + ε ) / ε ⌉ , and let N i N_i N i be the number of recursive calls at depth i i i , where the initial call has depth zero. By Lemma 3.2, a call with remaining budget q q q considers fewer than d ( 1 + ε ) q / ε ≤ c q d(1+\varepsilon)q/\varepsilon\le cq d ( 1 + ε ) q / ε ≤ c q variables. Therefore, it makes at most c q cq c q recursive calls. We claim that N i ≤ c i k ! / ( k − i ) ! N_i \le c^i k!/(k-i)! N i ≤ c i k ! / ( k − i )! for every i ∈ { 0 , … , k } i \in\{0,\ldots,k\} i ∈ { 0 , … , k } . At depth zero, there is only the initial call, so N 0 = 1 N_0 = 1 N 0 = 1 , as required. Now suppose the claim holds at depth i i i . Every call at this depth has remaining budget k − i k-i k − i and therefore makes at most c ( k − i ) c(k-i) c ( k − i ) recursive calls. Hence,
N i + 1 ≤ N i c ( k − i ) ≤ c i k ! ( k − i ) ! c ( k − i ) = c i + 1 k ! ( k − i − 1 ) ! . N_{i+1} \le N_i c(k-i) \le c^i \frac{k!}{(k-i)!}c(k-i) = c^{i+1}\frac{k!}{(k-i-1)!}. N i + 1 ≤ N i c ( k − i ) ≤ c i ( k − i )! k ! c ( k − i ) = c i + 1 ( k − i − 1 )! k ! .
This proves the claim by induction. The total number of calls is therefore at most
∑ i = 0 k N i ≤ ∑ i = 0 k c i k ! ( k − i ) ! = c k k ! ∑ j = 0 k 1 c j j ! . \sum_{i=0}^{k}N_i \le\sum_{i=0}^{k}c^i\frac{k!}{(k-i)!}=c^k k!\sum_{j=0}^{k}\frac{1}{c^j j!}. i = 0 ∑ k N i ≤ i = 0 ∑ k c i ( k − i )! k ! = c k k ! j = 0 ∑ k c j j ! 1 .
Since c ≥ 2 c \ge2 c ≥ 2 and j ! ≥ 1 j! \ge1 j ! ≥ 1 , we have ∑ j = 0 k 1 / ( c j j ! ) ≤ ∑ j = 0 k 1 / 2 j < 2 \sum_{j=0}^{k}1/(c^j j!) \le\sum_{j=0}^{k}1/2^j < 2 ∑ j = 0 k 1/ ( c j j !) ≤ ∑ j = 0 k 1/ 2 j < 2 . Thus, the total number of recursive calls is less than 2 c k k ! 2c^k k! 2 c k k ! , and hence it is O ( c k k ! ) O(c^k k!) O ( c k k !) . Constructing a residual instance and comparing candidate assignments takes polynomial time. Since c = O ( d / ε ) c = O(d/\varepsilon) c = O ( d / ε ) and k ! ≤ k k k! \le k^k k ! ≤ k k , we have c k k ! ≤ ( d k / ε ) O ( k ) c^k k! \le(dk/\varepsilon)^{O(k)} c k k ! ≤ ( d k / ε ) O ( k ) . Therefore, the total running time is ( d k / ε ) O ( k ) N O ( 1 ) (dk/\varepsilon)^{O(k)}N^{O(1)} ( d k / ε ) O ( k ) N O ( 1 ) , as stated.
Corollary 3.5. Weighted arity-d d d Min-Unsat SAT and weighted Min-UnCoverage with ground-element frequency at most d d d admit deterministic EPAS algorithms parameterized by k + d k+d k + d .
Proof. By Theorem 3.4, weighted bounded-arity Min-Unsat CSP admits a deterministic EPAS. Since CNF formulas are a special case of Boolean CSP, the result for arity-d d d Min-Unsat SAT follows immediately.
We obtain the coverage result by reducing Min-UnCoverage to Min-Unsat SAT. Given an instance ( U , S , w , k ) (U,S,w,k) ( U , S , w , k ) , introduce a Boolean variable x S x_S x S for each set S ∈ S S \in\mathcal{S} S ∈ S , where x S = 1 x_S = 1 x S = 1 means that S S S is selected. For each ground element u u u , add the monotone clause ⋁ S ∈ S : u ∈ S x S \bigvee_{S\in\mathcal{S}:u\in S}x_S ⋁ S ∈ S : u ∈ S x S with weight w ( u ) w(u) w ( u ) . An assignment of Hamming weight at most k k k corresponds to a subfamily of at most k k k sets. The clause associated with u u u is violated exactly when u u u is uncovered, so the reduction preserves the objective value. If u u u belongs to no input set, this disjunction is empty and denotes the always-false clause. Its arity equals the number of sets containing u u u , so the reduction preserves the bound d d d . The coverage result follows from Theorem 3.4. Skowron and Faliszewski previously obtained the bounded-frequency coverage result for unit weights using a randomized algorithm [31 ] ; the algorithm obtained here is deterministic and allows rational objective weights.
Proposition 3.6 (Exactly k k k choices). For Min-UnCoverage, the at-most-k k k and exactly-k k k variants have the same optimum whenever ∣ S ∣ ≥ k |\mathcal{S}| \ge k ∣ S ∣ ≥ k , and all objective-value coverage algorithms in this paper extend to the exactly-k k k variant. If ∣ S ∣ < k |\mathcal{S}| < k ∣ S ∣ < k , that variant is infeasible. In contrast, unless FPT = W[1 ] , neither Min-Unsat SAT nor Min-Unsat CSP with exactly k k k true variables admits a finite-factor FPT approximation parameterized by k k k , even for unweighted clauses of arity two.
Proof. For coverage, a subfamily of fewer than k k k sets can be extended to k k k sets without increasing the uncovered weight. This proves equality of the two optima and preserves the guarantee of any approximation algorithm.
For SAT, take an instance ( G , k ) (G,k) ( G , k ) of Independent Set, which is W[1 ] -hard parameterized by k k k [10 ] . We may assume k ≤ ∣ V ( G ) ∣ k \le|V(G)| k ≤ ∣ V ( G ) ∣ . Introduce a variable x v x_v x v for each vertex and the unit-weight clause ( ¬ x u ∨ ¬ x v ) (\neg x_u \vee\neg x_v) ( ¬ x u ∨ ¬ x v ) for each edge u v uv uv . An assignment with exactly k k k true variables satisfies every clause if and only if those variables represent an independent set of size k k k . Thus its minimum unsatisfied weight is zero precisely on yes-instances. By the zero-optimum argument in Proposition 2.8, a finite-factor FPT approximation would decide Independent Set in FPT time. The CSP claim follows because SAT is a special case of Boolean CSP.
Hardness for Min-Unsat SAT and Min-Unsat CSP
The previous section gives an EPAS for weighted instances when every constraint has bounded arity. In this section, we show that this positive result does not extend to general CNF formulas under biclique-freeness, bounded semi-ladder index, or bounded variable frequency.
Hardness under Biclique-Freeness and Bounded Semi-Ladder Index
We give a parameter-preserving reduction from Multicolored Independent Set, which is W[1 ] -hard when parameterized by the number of colors [10 ] as follows.
Construction. Let ( G , V 1 , … , V k ) (G, V_1, \ldots, V_k) ( G , V 1 , … , V k ) be an instance of Multicolored Independent Set, where V ( G ) = V 1 ⊎ ⋯ ⊎ V k V(G) = V_1 \uplus\cdots\uplus V_k V ( G ) = V 1 ⊎ ⋯ ⊎ V k . Introduce a Boolean variable x v x_v x v for each vertex v ∈ V ( G ) v \in V(G) v ∈ V ( G ) . We may delete all edges within a color class, since they are irrelevant to a multicolored independent set. For each color i ∈ [ k ] i \in[k] i ∈ [ k ] , add the selection clause A i = ⋁ v ∈ V i x v A_i = \bigvee_{v \in V_i} x_v A i = ⋁ v ∈ V i x v . For each edge u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) , add the conflict clause B u v = ¬ x u ∨ ¬ x v B_{uv} = \neg x_u \vee\neg x_v B uv = ¬ x u ∨ ¬ x v . Finally, for each i ∈ [ k ] i \in[k] i ∈ [ k ] and each pair of distinct vertices u , v ∈ V i u, v \in V_i u , v ∈ V i , add the pairwise exclusion clause D u v = ¬ x u ∨ ¬ x v D_{uv} = \neg x_u \vee\neg x_v D uv = ¬ x u ∨ ¬ x v . Let Φ G \Phi_G Φ G be the conjunction of these clauses, and set the Hamming-weight bound to k k k .
Claim 4.1. The incidence graph of Φ G \Phi_G Φ G excludes both orientations of K 3 , 2 K_{3,2} K 3 , 2 and, in particular, is K 3 , 3 K_{3,3} K 3 , 3 -free.
Proof. Every clause other than a selection clause contains only two variables, and all variables in a selection clause belong to the same color class. Thus any three variables have at most one common clause neighbor, namely their common selection clause when all three belong to the same color class. Hence the incidence graph contains no K 3 , 2 K_{3,2} K 3 , 2 whose three-vertex side lies in the variable part.
Conversely, any two variables have at most two common clause neighbors. Two variables from the same color class occur together only in their selection clause and their pairwise exclusion clause, while two variables from different color classes occur together in at most one conflict clause. Hence the incidence graph contains no K 2 , 3 K_{2,3} K 2 , 3 whose three-vertex side lies in the clause part. Thus both orientations of K 3 , 2 K_{3,2} K 3 , 2 are excluded. In particular, the incidence graph is K 3 , 3 K_{3,3} K 3 , 3 -free.
Claim 4.2. G G G contains a multicolored independent set of size k k k if and only if Φ G \Phi_G Φ G has a satisfying assignment. Moreover, every satisfying assignment of Φ G \Phi_G Φ G has Hamming weight exactly k k k .
Proof. (⇒ \Rightarrow ⇒ ) Suppose S S S is a multicolored independent set in G G G . Set x v = 1 x_v = 1 x v = 1 exactly when v ∈ S v \in S v ∈ S . This assignment has Hamming weight k k k and satisfies every selection clause and every pairwise exclusion clause. It also satisfies every conflict clause because no edge has both endpoints in S S S . Hence, it satisfies Φ G \Phi_G Φ G .
(⇐ \Leftarrow ⇐ ) Conversely, let τ \tau τ be a satisfying assignment. Each selection clause A i A_i A i forces at least one variable from V i V_i V i to be true, and the pairwise exclusion clauses force at most one such variable to be true. Hence every satisfying assignment, even without a Hamming-weight restriction, sets exactly one variable from each color class to one and has Hamming weight exactly k k k . Let S S S be the corresponding set of vertices. Every conflict clause is satisfied, so no edge has both endpoints in S S S . Therefore, S S S is a multicolored independent set.
Unless F P T = W [ 1 ] FPT = W[1] F P T = W [ 1 ] , for every computable function g : N 2 → R ≥ 1 g : \mathbb{N}^{2} \to\mathbb{R}_{\ge1} g : N 2 → R ≥ 1 , neither Min-Unsat SAT nor Min-Unsat CSP admits a g ( k , d ) g(k,d) g ( k , d ) -approximation in FPT time parameterized by k + d k+d k + d on unweighted K d , d K_{d,d} K d , d -free instances or on unweighted instances of semi-ladder index at most d d d . In particular, the hardness holds already on K 3 , 3 K_{3,3} K 3 , 3 -free instances and on instances of semi-ladder index at most four, respectively, and hence neither problem admits a finite-factor FPT approximation parameterized by k k k on these classes.
Moreover, assuming ETH, neither problem admits a finite-factor approximation running in f ( k , d ) N o ( k + d ) f(k,d)N^{o(k+d)} f ( k , d ) N o ( k + d ) time under either restriction, for any computable function f f f .
Proof. Give every clause unit weight. By Claims 4.1 and 4.2 , the construction is a parameter-preserving reduction from Multicolored Independent Set, the resulting incidence graph excludes both orientations of K 3 , 2 K_{3,2} K 3 , 2 , and every satisfying assignment has Hamming weight exactly k k k . Thus Proposition 2.8 gives the claimed approximation hardness for K 3 , 3 K_{3,3} K 3 , 3 -free Min-Unsat SAT.
A bipartite graph excluding both orientations of K 3 , 2 K_{3,2} K 3 , 2 has semi-ladder index at most four: a semi-ladder of order five contains all edges between { a 3 , a 4 , a 5 } \{a_3,a_4,a_5\} { a 3 , a 4 , a 5 } and { b 1 , b 2 } \{b_1,b_2\} { b 1 , b 2 } , and hence contains a K 3 , 2 K_{3,2} K 3 , 2 . This proves the semi-ladder claim. The same lower bounds hold for Min-Unsat CSP because Min-Unsat SAT is a special case of Boolean CSP that preserves the incidence graph.
For the ETH lower bound, Independent Set on an n n n -vertex graph has no f ( k ) n o ( k ) f(k)n^{o(k)} f ( k ) n o ( k ) -time algorithm for any computable function f f f [8 ] ; the standard construction with k k k colored copies gives the same lower bound for Multicolored Independent Set. Our reduction produces a formula of size N = n O ( 1 ) N=n^{O(1)} N = n O ( 1 ) and preserves k k k . Since d = 3 d=3 d = 3 in the biclique-free case and d = 4 d=4 d = 4 in the semi-ladder case, k + d = Θ ( k ) k+d=\Theta(k) k + d = Θ ( k ) , which yields the stated running-time lower bound.
Hardness under Bounded Variable Frequency
We next show that the positive result for bounded arity does not extend to bounded variable frequency. We give a parameter-preserving reduction from Multicolored Clique, which is W[1 ] -hard when parameterized by the number of colors [10 ] .
Construction. Let ( G , V 1 , … , V r ) (G,V_1,\ldots,V_r) ( G , V 1 , … , V r ) be an instance of Multicolored Clique, where V ( G ) = V 1 ⊎ ⋯ ⊎ V r V(G)=V_1\uplus\cdots\uplus V_r V ( G ) = V 1 ⊎ ⋯ ⊎ V r . Introduce a variable x v x_v x v for every vertex v v v and a variable y e y_e y e for every edge e e e joining two different color classes.
X i = ⋁ v ∈ V i x v . X_i=\bigvee_{v\in V_i}x_v. X i = v ∈ V i ⋁ x v .
Y i j = ⋁ e ∈ E ( V i , V j ) y e . Y_{ij}=\bigvee_{e\in E(V_i,V_j)}y_e. Y ij = e ∈ E ( V i , V j ) ⋁ y e .
If some E ( V i , V j ) E(V_i,V_j) E ( V i , V j ) is empty, then the source instance is a no-instance; in this case, we output the single clause ( z ) (z) ( z ) with Hamming-weight bound zero. We may therefore assume that every edge-selection clause is nonempty.
C ( v , j ) = ¬ x v ∨ ⋁ e = v w , w ∈ V j y e . C(v,j)=\neg x_v\vee\bigvee_{\substack{e=vw,\,w\in V_j}}y_e. C ( v , j ) = ¬ x v ∨ e = v w , w ∈ V j ⋁ y e .
If v v v has no neighbor in V j V_j V j , this clause is simply ¬ x v \neg x_v ¬ x v .
k ′ : = r + ( r 2 ) , k' := r + \binom{r}{2}, k ′ := r + ( 2 r ) ,
and let Φ G \Phi_G Φ G be the conjunction of all the clauses above.
Claim 4.4. The maximum variable frequency of Φ G \Phi_G Φ G is at most d : = max { r , 3 } d := \max\{r,3\} d := max { r , 3 } , and k ′ + d = O ( r 2 ) k' + d = O(r^2) k ′ + d = O ( r 2 ) .
Proof. Each variable x v x_v x v , where v ∈ V i v \in V_i v ∈ V i , occurs in X i X_i X i and in the r − 1 r-1 r − 1 clauses C ( v , j ) C(v,j) C ( v , j ) with j ≠ i j \ne i j = i , and hence has frequency r r r . If e = u v e = uv e = uv joins V i V_i V i and V j V_j V j , then y e y_e y e occurs in exactly three clauses: Y i j Y_{ij} Y ij , C ( u , j ) C(u,j) C ( u , j ) , and C ( v , i ) C(v,i) C ( v , i ) . Thus the maximum variable frequency is at most d : = max { r , 3 } d := \max\{r,3\} d := max { r , 3 } . Since k ′ = r + ( r 2 ) = O ( r 2 ) k' = r + \binom{r}{2} = O(r^2) k ′ = r + ( 2 r ) = O ( r 2 ) , we also have k ′ + d = O ( r 2 ) k' + d = O(r^2) k ′ + d = O ( r 2 ) .
Claim 4.5. G G G contains a multicolored clique of size r r r if and only if Φ G \Phi_G Φ G has a satisfying assignment of Hamming weight at most k ′ k' k ′ .
Proof. (⇒ \Rightarrow ⇒ ) Suppose that { v 1 , … , v r } \{v_1,\ldots,v_r\} { v 1 , … , v r } is a multicolored clique, where v i ∈ V i v_i \in V_i v i ∈ V i . Set x v i = 1 x_{v_i}=1 x v i = 1 for every i ∈ [ r ] i \in[r] i ∈ [ r ] and y v i v j = 1 y_{v_iv_j}=1 y v i v j = 1 for every $1 \le i < j \le r$, and set all other variables to zero. This assignment has Hamming weight exactly k ′ k' k ′ . Every vertex-selection clause X i X_i X i and every edge-selection clause Y i j Y_{ij} Y ij is satisfied. Moreover, for every selected vertex v i v_i v i and every j ≠ i j \ne i j = i , the variable y v i v j y_{v_iv_j} y v i v j occurs in C ( v i , j ) C(v_i,j) C ( v i , j ) and is set to one, while every consistency clause corresponding to an unselected vertex is satisfied by its negative literal. Hence Φ G \Phi_G Φ G is satisfied.
(⇐ \Leftarrow ⇐ ) Conversely, suppose that Φ G \Phi_G Φ G has a satisfying assignment of Hamming weight at most k ′ k' k ′ . There are exactly r + ( r 2 ) = k ′ r + \binom{r}{2} = k' r + ( 2 r ) = k ′ selection clauses, namely the clauses X i X_i X i and Y i j Y_{ij} Y ij , and their variable sets are pairwise disjoint. Hence satisfying all of them requires at least k ′ k' k ′ true variables. The Hamming-weight bound therefore implies that exactly one variable is set to one in each selection clause and no other variable is set to one.
For every i ∈ [ r ] i \in[r] i ∈ [ r ] , let x v i x_{v_i} x v i be the unique true variable in X i X_i X i , and for every $1 \le i < j \le r$, let y e i j y_{e_{ij}} y e ij be the unique true variable in Y i j Y_{ij} Y ij . Since x v i = 1 x_{v_i}=1 x v i = 1 , the clause C ( v i , j ) C(v_i,j) C ( v i , j ) can be satisfied only by a true edge variable representing an edge from v i v_i v i to V j V_j V j . Since y e i j y_{e_{ij}} y e ij is the unique true variable in Y i j Y_{ij} Y ij , the edge e i j e_{ij} e ij must be incident with v i v_i v i . Similarly, C ( v j , i ) C(v_j,i) C ( v j , i ) implies that e i j e_{ij} e ij is incident with v j v_j v j . Hence e i j = v i v j e_{ij}=v_iv_j e ij = v i v j . This holds for every pair i < j i<j i < j , and therefore { v 1 , … , v r } \{v_1,\ldots,v_r\} { v 1 , … , v r } is a multicolored clique.
Theorem 4.6. Unless F P T = W [ 1 ] FPT = W[1] F P T = W [ 1 ] , for every computable function g : N 2 → R ≥ 1 g:\mathbb{N}^2 \to\mathbb{R}_{\ge1} g : N 2 → R ≥ 1 , neither Min-Unsat SAT nor Min-Unsat CSP admits a g ( k , d ) g(k,d) g ( k , d ) -approximation in FPT time parameterized by k + d k+d k + d on unweighted instances of maximum variable frequency at most d d d .
Moreover, assuming ETH, neither problem admits a finite-factor approximation running in f ( k , d ) N o ( k + d ) f(k,d)N^{o(\sqrt{k+d})} f ( k , d ) N o ( k + d ) time for any computable function f f f .
Proof. By Claims 4.4 and 4.5, the construction is a parameterized reduction from Multicolored Clique: the resulting formula is satisfiable by an assignment of Hamming weight at most k ′ k' k ′ if and only if the source graph has a multicolored clique, and its maximum variable frequency is at most d = max { r , 3 } d=\max\{r,3\} d = max { r , 3 } . Giving every clause unit weight and applying Proposition 2.8 proves the approximation hardness for Min-Unsat SAT. It extends to Min-Unsat CSP because SAT is a special case of Boolean CSP and the encoding preserves variable frequency.
For the ETH lower bound, Clique on an n n n -vertex graph has no f ( r ) n o ( r ) f(r)n^{o(r)} f ( r ) n o ( r ) -time algorithm for any computable function f f f [8 ] ; the standard construction with r r r colored copies gives the same lower bound for Multicolored Clique. Our reduction produces a formula of size N = n O ( 1 ) N=n^{O(1)} N = n O ( 1 ) with k ′ + d = Θ ( r 2 ) k'+d=\Theta(r^2) k ′ + d = Θ ( r 2 ) . Therefore, a running time of f ( k , d ) N o ( k + d ) f(k,d)N^{o(\sqrt{k+d})} f ( k , d ) N o ( k + d ) would yield an f ′ ( r ) n o ( r ) f'(r)n^{o(r)} f ′ ( r ) n o ( r ) -time algorithm for Multicolored Clique, contradicting ETH.
An EPAS for Weighted Min-UnCoverage with Bounded Semi-Ladder Index
We now move beyond bounded ground-element frequency and place a restriction on the whole incidence graph. Fix ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] and consider a weighted Min-UnCoverage instance I = ( U , S , w , k ) I=(U,\mathcal{S},w,k) I = ( U , S , w , k ) whose incidence graph has semi-ladder index at most d d d . Write
OPT m i s s ( I ) = min A ⊆ S ∣ A ∣ ≤ k miss S , w ( A ) . \operatorname{OPT}_{\mathrm{miss}}(I)=\min_{\substack{\mathcal{A}\subseteq\mathcal{S}\\|\mathcal{A}|\leq k}}\operatorname{miss}_{\mathcal{S},w}(\mathcal{A}). OPT miss ( I ) = A ⊆ S ∣ A ∣ ≤ k min miss S , w ( A ) .
We adapt Kundu et al.’s skeleton-based branching framework and deterministic weighted-net construction [23 ] . The skeletons, eligible families, forced-coverage intersections, weighted nets, and semi-ladder depth argument come from that framework. Our contribution here is the residual-weight argument: unless the current candidate has the required approximation guarantee, an optimum set covers enough unresolved weight to be hit by the net. This yields an approximation to the uncovered weight while keeping the original budget of at most k k k sets.
Assume for now that k ≥ 1 k\geq1 k ≥ 1 and S ≠ ∅ \mathcal{S}\neq\varnothing S = ∅ ; the remaining cases are immediate. The algorithm maintains an ordered tuple of skeletons
M = ( M 1 , … , M k ) , M i ⊆ U . \mathbf{M}=(M_1,\ldots,M_k),\qquad M_i\subseteq U. M = ( M 1 , … , M k ) , M i ⊆ U .
The skeleton M i M_i M i records the elements that the set chosen for coordinate i i i must contain. Its eligible choices are
P i ( M ) = { S ∈ S : M i ⊆ S } \mathcal{P}_i(\mathbf{M})=\{S\in\mathcal{S}:M_i\subseteq S\} P i ( M ) = { S ∈ S : M i ⊆ S }
and the state is feasible when every P i ( M ) \mathcal{P}_i(\mathbf{M}) P i ( M ) is nonempty. At a feasible state, define
F i ( M ) = ⋂ S ∈ P i ( M ) S , F ( M ) = ⋃ i = 1 k F i ( M ) , W ( M ) = U ∖ F ( M ) . F_i(\mathbf{M})=\bigcap_{S\in\mathcal{P}_i(\mathbf{M})}S,\qquad F(\mathbf{M})=\bigcup_{i=1}^{k}F_i(\mathbf{M}),\qquad W(\mathbf{M})=U\setminus F(\mathbf{M}). F i ( M ) = S ∈ P i ( M ) ⋂ S , F ( M ) = i = 1 ⋃ k F i ( M ) , W ( M ) = U ∖ F ( M ) .
Here F i ( M ) F_i(\mathbf{M}) F i ( M ) is the coverage forced at coordinate i i i , F ( M ) F(\mathbf{M}) F ( M ) is the coverage guaranteed by all coordinates, and W ( M ) W(\mathbf{M}) W ( M ) contains the elements whose coverage remains unresolved. Choosing any A i ∈ P i ( M ) A_i\in\mathcal{P}_i(\mathbf{M}) A i ∈ P i ( M ) for every i ∈ [ k ] i\in[k] i ∈ [ k ] gives a candidate subfamily A = { A 1 , … , A k } \mathcal{A}=\{A_1,\ldots,A_k\} A = { A 1 , … , A k } . It covers F ( M ) F(\mathbf{M}) F ( M ) and therefore leaves uncovered weight at most w ( W ( M ) ) w(W(\mathbf{M})) w ( W ( M )) .
Because adding a set cannot increase the uncovered weight, an optimum solution can be represented by an ordered k k k -tuple O = ( O 1 , … , O k ) \mathbf{O}=(O_1,\ldots,O_k) O = ( O 1 , … , O k ) , allowing repeated sets. We call a state M \mathbf{M} M consistent with O \mathbf{O} O if M i ⊆ O i M_i\subseteq O_i M i ⊆ O i , or equivalently O i ∈ P i ( M ) O_i\in\mathcal{P}_i(\mathbf{M}) O i ∈ P i ( M ) , for every i ∈ [ k ] i\in[k] i ∈ [ k ] .
Branching depends only on how eligible sets meet the unresolved elements. We record these intersections in the restricted set system
R ( M ) = ( W ( M ) , { S ∩ W ( M ) : S ∈ ⋃ i = 1 k P i ( M ) } ) . \mathcal{R}(\mathbf{M})=\left(W(\mathbf{M}),\left\{S\cap W(\mathbf{M}):S\in\bigcup_{i=1}^{k}\mathcal{P}_i(\mathbf{M})\right\}\right). R ( M ) = ( W ( M ) , { S ∩ W ( M ) : S ∈ i = 1 ⋃ k P i ( M ) } ) .
Intersecting the eligible sets with W ( M ) W(\mathbf{M}) W ( M ) cannot increase the semi-ladder index. Suppose that distinct members T 1 , … , T ℓ T_1,\ldots,T_\ell T 1 , … , T ℓ of the restricted family and elements u 1 , … , u ℓ ∈ W ( M ) u_1,\ldots,u_\ell\in W(\mathbf{M}) u 1 , … , u ℓ ∈ W ( M ) form a semi-ladder in R ( M ) \mathcal{R}(\mathbf{M}) R ( M ) . For each i i i , choose an eligible set S i S_i S i such that T i = S i ∩ W ( M ) T_i=S_i\cap W(\mathbf{M}) T i = S i ∩ W ( M ) . The sets S 1 , … , S ℓ S_1,\ldots,S_\ell S 1 , … , S ℓ are distinct because the sets T 1 , … , T ℓ T_1,\ldots,T_\ell T 1 , … , T ℓ are distinct. Since every u j u_j u j belongs to W ( M ) W(\mathbf{M}) W ( M ) , we have u j ∈ T i u_j\in T_i u j ∈ T i if and only if u j ∈ S i u_j\in S_i u j ∈ S i . Hence u i ∉ S i u_i\notin S_i u i ∈ / S i and u j ∈ S i u_j\in S_i u j ∈ S i whenever j < i j<i j < i . Thus, S 1 , … , S ℓ S_1,\ldots,S_\ell S 1 , … , S ℓ and u 1 , … , u ℓ u_1,\ldots,u_\ell u 1 , … , u ℓ form a semi-ladder of order ℓ \ell ℓ in the original incidence graph. Therefore, R ( M ) \mathcal{R}(\mathbf{M}) R ( M ) has semi-ladder index at most d d d .
By Observation 2.7 , semi-ladder index at most d d d implies VC dimension at most d d d . Thus standard weighted δ \delta δ -net bounds already explain the existence and size of the net used below. The additional algorithmic ingredient needed here is a deterministic FPT-time construction.
Kundu et al. obtain such a construction under bounded semi-ladder index using Guillemot’s FPT algorithm for Set Cover [23 , 17 ] . For W ≠ ∅ W \ne\varnothing W = ∅ and 0 < δ ≤ 1 0 < \delta\le1 0 < δ ≤ 1 , a weighted δ \delta δ -net for ( W , P , w ) (W,\mathcal{P},w) ( W , P , w ) is a set Z ⊆ W Z \subseteq W Z ⊆ W that intersects every P ∈ P P \in\mathcal{P} P ∈ P with w ( P ) ≥ δ w ( W ) w(P) \ge\delta w(W) w ( P ) ≥ δ w ( W ) . The following lemma is a direct consequence of Kundu et al.’s Theorem 5.9 and Lemmas 8.10 and 8.12 [23 ] , applied to P δ = { P ∈ P : w ( P ) ≥ δ w ( W ) } \mathcal{P}_{\delta} = \{P \in\mathcal{P} : w(P) \ge\delta w(W)\} P δ = { P ∈ P : w ( P ) ≥ δ w ( W )} . Restricting P \mathcal{P} P to this subfamily cannot increase its semi-ladder index.
Lemma 5.1 (Deterministic weighted nets for bounded semi-ladder index). Let ( W , P ) (W,\mathcal{P}) ( W , P ) be a set system with W ≠ ∅ W \ne\varnothing W = ∅ whose incidence graph has semi-ladder index at most d d d , let w : W → Q > 0 w: W \to\mathbb{Q}_{>0} w : W → Q > 0 , and let δ ∈ ( 0 , 1 / 2 ] \delta\in(0,1/2] δ ∈ ( 0 , 1/2 ] . A weighted δ \delta δ -net of size
O ( d + 1 δ log 1 δ ) O\left(\frac{d+1}{\delta}\log\frac{1}{\delta}\right) O ( δ d + 1 log δ 1 ) can be found in time
( d + 1 δ ) O ( ( d + 1 ) 2 δ log 1 δ ) N O ( 1 ) , \left(\frac{d+1}{\delta}\right)^{O\left(\frac{(d+1)^2}{\delta}\log\frac{1}{\delta}\right)}N^{O(1)}, ( δ d + 1 ) O ( δ ( d + 1 ) 2 l o g δ 1 ) N O ( 1 ) , where N N N is the encoding size of ( W , P , w ) (W,\mathcal{P},w) ( W , P , w ) .
The polynomial factor accounts for exact arithmetic on binary rational weights. To form P δ \mathcal{P}_{\delta} P δ , we sum the weights in each range and compare the result with δ w ( W ) \delta w(W) δ w ( W ) . Each such sum has bit length polynomial in the input size. The remaining net construction is an unweighted covering computation on the incidence graph of ( W , P δ ) (W,\mathcal{P}_{\delta}) ( W , P δ ) .
Now consider a state consistent with O such that ∑ i = 1 k ∣ M i ∣ < k d \sum_{i=1}^{k}|M_i| < kd ∑ i = 1 k ∣ M i ∣ < k d . Since O i ∈ P i ( M ) O_i \in\mathcal{P}_i(\mathbf{M}) O i ∈ P i ( M ) , we have F i ( M ) ⊆ O i F_i(\mathbf{M}) \subseteq O_i F i ( M ) ⊆ O i . Hence every element missed by O belongs to W ( M ) W(\mathbf{M}) W ( M ) , and these elements have total weight OPT m i s s ( I ) \operatorname{OPT}_{\mathrm{miss}}(I) OPT miss ( I ) . If w ( W ( M ) ) ≤ ( 1 + ε ) OPT m i s s ( I ) w(W(\mathbf{M})) \le(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ( M )) ≤ ( 1 + ε ) OPT miss ( I ) , the current candidate already has the required value. Otherwise, w ( W ( M ) ) > ( 1 + ε ) OPT m i s s ( I ) w(W(\mathbf{M})) > (1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ( M )) > ( 1 + ε ) OPT miss ( I ) , so OPT m i s s ( I ) < w ( W ( M ) ) / ( 1 + ε ) \operatorname{OPT}_{\mathrm{miss}}(I) < w(W(\mathbf{M}))/(1+\varepsilon) OPT miss ( I ) < w ( W ( M )) / ( 1 + ε ) . Hence the optimum covers more than ε w ( W ( M ) ) / ( 1 + ε ) \varepsilon w(W(\mathbf{M}))/(1+\varepsilon) εw ( W ( M )) / ( 1 + ε ) weight among the unresolved elements. Therefore, one of its k k k sets satisfies
w ( O i ∩ W ( M ) ) > ε k ( 1 + ε ) w ( W ( M ) ) . w(O_i \cap W(\mathbf{M})) > \frac{\varepsilon}{k(1+\varepsilon)}w(W(\mathbf{M})). w ( O i ∩ W ( M )) > k ( 1 + ε ) ε w ( W ( M )) .
Set δ = ε / ( k ( 1 + ε ) ) \delta= \varepsilon/(k(1+\varepsilon)) δ = ε / ( k ( 1 + ε )) . Since k ≥ 1 k \ge1 k ≥ 1 and 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 , we have 0 < δ ≤ 1 / 2 0 < \delta\le1/2 0 < δ ≤ 1/2 . By Lemma 5.1, a weighted δ \delta δ -net for R ( M ) \mathcal{R}(\mathbf{M}) R ( M ) contains an element u ∈ O i ∩ W ( M ) u \in O_i \cap W(\mathbf{M}) u ∈ O i ∩ W ( M ) . The algorithm does not know the optimum tuple, so it tries every pair ( i , u ) (i,u) ( i , u ) and restricts coordinate i i i to eligible sets that contain u u u . The branch indexed by this pair ( i , u ) (i,u) ( i , u ) remains consistent.
The comparison with OPT m i s s ( I ) \operatorname{OPT}_{\mathrm{miss}}(I) OPT miss ( I ) is used only in the proof. The algorithm does not know this value. It records the candidate at every state, explores the branches described below, and returns the best candidate found.
Adding u u u to M i M_i M i also creates a new semi-ladder rung. Indeed, u ∈ W ( M ) u \in W(\mathbf{M}) u ∈ W ( M ) implies u ∉ F i ( M ) u \notin F_i(\mathbf{M}) u ∈ / F i ( M ) , so some eligible set misses u u u while containing every element already in M i M_i M i . Each skeleton therefore grows at most d d d times, and the recursion depth is at most k d kd k d . The complete procedure is given in Algorithm 2. Lemmas 5.2 and 5.3 establish the skeleton-size and approximation bounds.
The algorithm is invoked as SL-MinUnCov( I , ( ∅ , … , ∅ ) , d , ε ) (I,(\varnothing,\ldots,\varnothing),d,\varepsilon) ( I , ( ∅ , … , ∅ ) , d , ε ) . The test before each recursive call ensures that the updated skeleton has an eligible set; the eligible sets at the other coordinates do not change.
We first prove the depth bound.
Lemma 5.2 (Skeleton size). Consider any recursive call reached by Algorithm 2, and fix h ∈ [ k ] h \in[k] h ∈ [ k ] . Write M h = { u 1 , … , u ℓ } M_h = \{u_1,\ldots,u_{\ell}\} M h = { u 1 , … , u ℓ } in the order in which its elements were inserted. Then there exist pairwise distinct sets R 1 , … , R ℓ ∈ S R_1,\ldots,R_{\ell} \in\mathcal{S} R 1 , … , R ℓ ∈ S such that, for every r ∈ [ ℓ ] r \in[\ell] r ∈ [ ℓ ] ,
u r ∉ R r and u s ∈ R r for every s < r . u_r \notin R_r \qquad\text{and} \qquad u_s \in R_r \text{ for every } s<r. u r ∈ / R r and u s ∈ R r for every s < r .
Algorithm 2 SL-MinUnCov( I , M , d , ε ) (I,\mathbf{M},d,\varepsilon) ( I , M , d , ε )
Require: A weighted Min-UnCoverage instance I = ( U , S , w , k ) I=(U,\mathcal{S},w,k) I = ( U , S , w , k ) of semi-ladder index at most d d d , skeletons M = ( M 1 , … , M k ) \mathbf{M}=(M_1,\ldots,M_k) M = ( M 1 , … , M k ) , and ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] .
Ensure: A subfamily of at most k k k sets, or ⊥ \bot ⊥ if some skeleton has no eligible set.
for i ← 1 i\gets1 i ← 1 to k k k do
P i ← { S ∈ S : M i ⊆ S } \mathcal{P}_i\gets\{S\in\mathcal{S}:M_i\subseteq S\} P i ← { S ∈ S : M i ⊆ S }
if P i = ∅ \mathcal{P}_i=\varnothing P i = ∅ then
return ⊥ \bot ⊥
Choose any A i ∈ P i A_i\in\mathcal{P}_i A i ∈ P i
F i ← ⋂ S ∈ P i S F_i\gets\bigcap_{S\in\mathcal{P}_i}S F i ← ⋂ S ∈ P i S
A ← { A 1 , … , A k } \mathcal{A}\gets\{A_1,\ldots,A_k\} A ← { A 1 , … , A k } , F ← ⋃ i = 1 k F i F\gets\bigcup_{i=1}^{k}F_i F ← ⋃ i = 1 k F i , and W ← U ∖ F W\gets U\setminus F W ← U ∖ F
if W = ∅ W=\varnothing W = ∅ or ∑ i = 1 k ∣ M i ∣ ≥ k d \sum_{i=1}^{k}|M_i|\ge kd ∑ i = 1 k ∣ M i ∣ ≥ k d then
return A \mathcal{A} A
δ ← ε / ( k ( 1 + ε ) ) \delta\gets\varepsilon/(k(1+\varepsilon)) δ ← ε / ( k ( 1 + ε ))
Use Lemma 5.1 to compute a weighted δ \delta δ -net Z ⊆ W Z\subseteq W Z ⊆ W for { S ∩ W : S ∈ ⋃ i = 1 k P i } \{S\cap W:S\in\bigcup_{i=1}^{k}\mathcal{P}_i\} { S ∩ W : S ∈ ⋃ i = 1 k P i }
A b e s t ← A \mathcal{A}_{\mathrm{best}}\gets\mathcal{A} A best ← A
for all ( i , u ) ∈ [ k ] × Z (i,u)\in[k]\times Z ( i , u ) ∈ [ k ] × Z do
if { S ∈ P i : u ∈ S } ≠ ∅ \{S\in\mathcal{P}_i:u\in S\}\ne\varnothing { S ∈ P i : u ∈ S } = ∅ then
Let M ′ \mathbf{M}' M ′ be obtained from M \mathbf{M} M by replacing M i M_i M i with M i ∪ { u } M_i\cup\{u\} M i ∪ { u }
B ← S L - M i n U n C o v ( I , M ′ , d , ε ) \mathcal{B}\gets\mathrm{SL\text{-}MinUnCov}(I,\mathbf{M}',d,\varepsilon) B ← SL - MinUnCov ( I , M ′ , d , ε )
if B ≠ ⊥ \mathcal{B}\ne\bot B = ⊥ and miss S , w ( B ) < miss S , w ( A b e s t ) \operatorname{miss}_{\mathcal{S},w}(\mathcal{B})<\operatorname{miss}_{\mathcal{S},w}(\mathcal{A}_{\mathrm{best}}) miss S , w ( B ) < miss S , w ( A best ) then
A b e s t ← B \mathcal{A}_{\mathrm{best}}\gets\mathcal{B} A best ← B
return A b e s t \mathcal{A}_{\mathrm{best}} A best
Thus, R 1 , … , R ℓ R_1,\ldots,R_\ell R 1 , … , R ℓ and u 1 , … , u ℓ u_1,\ldots,u_\ell u 1 , … , u ℓ form a semi-ladder of order ℓ \ell ℓ . Consequently, ∣ M h ∣ ≤ d |M_h|\le d ∣ M h ∣ ≤ d for every h ∈ [ k ] h\in[k] h ∈ [ k ] .
Proof. Fix a coordinate h h h . Suppose that the successive elements inserted into M h M_h M h are u 1 , … , u ℓ u_1,\ldots,u_\ell u 1 , … , u ℓ . For each r ∈ [ ℓ ] r\in[\ell] r ∈ [ ℓ ] , let M ( r − 1 ) \mathbf{M}^{(r-1)} M ( r − 1 ) be the state immediately before u r u_r u r is inserted into coordinate h h h , and let M h ( r − 1 ) M_h^{(r-1)} M h ( r − 1 ) be its h h h th skeleton. The algorithm chooses u r ∈ W ( M ( r − 1 ) ) u_r\in W(\mathbf{M}^{(r-1)}) u r ∈ W ( M ( r − 1 ) ) , and hence
u r ∉ F h ( M ( r − 1 ) ) = ⋂ S ∈ P h ( M ( r − 1 ) ) S . u_r\notin F_h(\mathbf{M}^{(r-1)})=\bigcap_{S\in\mathcal{P}_h(\mathbf{M}^{(r-1)})}S. u r ∈ / F h ( M ( r − 1 ) ) = S ∈ P h ( M ( r − 1 ) ) ⋂ S .
Therefore, some set R r ∈ P h ( M ( r − 1 ) ) R_r\in\mathcal{P}_h(\mathbf{M}^{(r-1)}) R r ∈ P h ( M ( r − 1 ) ) misses u r u_r u r . At that time, { u 1 , … , u r − 1 } ⊆ M h ( r − 1 ) \{u_1,\ldots,u_{r-1}\}\subseteq M_h^{(r-1)} { u 1 , … , u r − 1 } ⊆ M h ( r − 1 ) . Every set in P h ( M ( r − 1 ) ) \mathcal{P}_h(\mathbf{M}^{(r-1)}) P h ( M ( r − 1 ) ) contains M h ( r − 1 ) M_h^{(r-1)} M h ( r − 1 ) , so
u r ∉ R r , u s ∈ R r whenever s < r . u_r\notin R_r,\qquad u_s\in R_r\quad\text{whenever }s<r. u r ∈ / R r , u s ∈ R r whenever s < r .
Moreover, if s < r s<r s < r , then u s ∈ M h ( r − 1 ) ⊆ F h ( M ( r − 1 ) ) u_s\in M_h^{(r-1)}\subseteq F_h(\mathbf{M}^{(r-1)}) u s ∈ M h ( r − 1 ) ⊆ F h ( M ( r − 1 ) ) , whereas u r ∈ W ( M ( r − 1 ) ) ⊆ U ∖ F h ( M ( r − 1 ) ) u_r\in W(\mathbf{M}^{(r-1)})\subseteq U\setminus F_h(\mathbf{M}^{(r-1)}) u r ∈ W ( M ( r − 1 ) ) ⊆ U ∖ F h ( M ( r − 1 ) ) . Thus, u 1 , … , u ℓ u_1,\ldots,u_\ell u 1 , … , u ℓ are pairwise distinct. The witness sets are also pairwise distinct: if s < r s<r s < r , then u s ∈ R r u_s\in R_r u s ∈ R r but u s ∉ R s u_s\notin R_s u s ∈ / R s , and hence R r ≠ R s R_r\ne R_s R r = R s . Therefore, R 1 , … , R ℓ R_1,\ldots,R_\ell R 1 , … , R ℓ and u 1 , … , u ℓ u_1,\ldots,u_\ell u 1 , … , u ℓ form a semi-ladder of order ℓ \ell ℓ . Since the incidence graph has semi-ladder index at most d d d , we have ℓ ≤ d \ell\le d ℓ ≤ d .
Lemma 5.3 (Approximation guarantee)
Let d ≥ 0 d\ge0 d ≥ 0 and 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 , and let I = ( U , S , w , k ) I=(U,\mathcal{S},w,k) I = ( U , S , w , k ) be a weighted Min-UnCoverage instance with k ≥ 1 k\ge1 k ≥ 1 and S ≠ ∅ \mathcal{S}\ne\varnothing S = ∅ . If its incidence graph has semi-ladder index at most d d d , then
S L - M i n U n C o v ( I , ( ∅ , … , ∅ ) , d , ε ) \mathrm{SL\text{-}MinUnCov}(I,(\varnothing,\ldots,\varnothing),d,\varepsilon) SL - MinUnCov ( I , ( ∅ , … , ∅ ) , d , ε )
returns a subfamily A ⊆ S \mathcal{A}\subseteq\mathcal{S} A ⊆ S satisfying
∣ A ∣ ≤ k and miss S , w ( A ) ≤ ( 1 + ε ) OPT m i s s ( I ) . |\mathcal{A}|\le k\qquad\text{and}\qquad\operatorname{miss}_{\mathcal{S},w}(\mathcal{A})\le(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I). ∣ A ∣ ≤ k and miss S , w ( A ) ≤ ( 1 + ε ) OPT miss ( I ) .
Proof. List the sets of an optimum subfamily and append arbitrary sets from S S S until the list has length k k k , allowing repetitions. This is possible because S ≠ ∅ S \ne\emptyset S = ∅ . Adding sets cannot increase the uncovered weight, so the resulting tuple O = ( O 1 , … , O k ) \mathbf{O}=(O_1,\ldots,O_k) O = ( O 1 , … , O k ) remains optimal. A state M \mathbf{M} M is consistent with O \mathbf{O} O if O i ∈ P i ( M ) O_i \in\mathcal{P}_i(\mathbf{M}) O i ∈ P i ( M ) for every i ∈ [ k ] i \in[k] i ∈ [ k ] . In particular, the initial state ( ∅ , … , ∅ ) (\emptyset,\ldots,\emptyset) ( ∅ , … , ∅ ) is consistent. A state is reachable if it occurs in a recursive call generated from this initial state.
For a reachable state M \mathbf{M} M , define
q ( M ) : = k d − ∑ h = 1 k ∣ M h ∣ . q(\mathbf{M}) := kd-\sum_{h=1}^{k}|M_h|. q ( M ) := k d − h = 1 ∑ k ∣ M h ∣.
By Lemma 5.2 , q ( M ) ≥ 0 q(\mathbf{M}) \ge0 q ( M ) ≥ 0 . For r ∈ { 0 , … , k d } r \in\{0,\ldots,kd\} r ∈ { 0 , … , k d } , let P ( r ) P(r) P ( r ) be the following statement: for every reachable state M \mathbf{M} M consistent with O \mathbf{O} O and satisfying q ( M ) = r q(\mathbf{M})=r q ( M ) = r , the algorithm, when called at M \mathbf{M} M , returns a subfamily whose uncovered weight is at most ( 1 + ε ) OPT m i s s ( I ) (1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) ( 1 + ε ) OPT miss ( I ) . We prove P ( r ) P(r) P ( r ) by induction on r r r .
Recall that δ = ε / ( k ( 1 + ε ) ) \delta=\varepsilon/(k(1+\varepsilon)) δ = ε / ( k ( 1 + ε )) . We use the following two claims in both the base case and the inductive step.
Claim 1. At a feasible state M \mathbf{M} M , the algorithm chooses one set A i ∈ P i ( M ) A_i \in\mathcal{P}_i(\mathbf{M}) A i ∈ P i ( M ) for each i ∈ [ k ] i \in[k] i ∈ [ k ] . Before making any recursive calls, it takes A M = { A i : i ∈ [ k ] } \mathcal{A}_{\mathbf{M}}=\{A_i:i\in[k]\} A M = { A i : i ∈ [ k ]} as its current candidate. This candidate satisfies
miss S , w ( A M ) ≤ w ( W ( M ) ) . \operatorname{miss}_{S,w}(\mathcal{A}_{\mathbf{M}})\le w(W(\mathbf{M})). miss S , w ( A M ) ≤ w ( W ( M )) .
Indeed, F i ( M ) F_i(\mathbf{M}) F i ( M ) is the intersection of all sets in P i ( M ) \mathcal{P}_i(\mathbf{M}) P i ( M ) , so F i ( M ) ⊆ A i F_i(\mathbf{M}) \subseteq A_i F i ( M ) ⊆ A i for every i i i . Thus, A M \mathcal{A}_{\mathbf{M}} A M covers F ( M ) F(\mathbf{M}) F ( M ) , and only elements in W ( M ) = U ∖ F ( M ) W(\mathbf{M})=U\setminus F(\mathbf{M}) W ( M ) = U ∖ F ( M ) can remain uncovered. The algorithm returns either this candidate or a subfamily with smaller uncovered weight.
Claim 2. Let M \mathbf{M} M be a reachable state consistent with O \mathbf{O} O . If w ( W ( M ) ) > ( 1 + ε ) OPT m i s s ( I ) w(W(\mathbf{M}))>(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ( M )) > ( 1 + ε ) OPT miss ( I ) , then some i ∈ [ k ] i\in[k] i ∈ [ k ] satisfies w ( O i ∩ W ( M ) ) > δ w ( W ( M ) ) w(O_i\cap W(\mathbf{M}))>\delta w(W(\mathbf{M})) w ( O i ∩ W ( M )) > δ w ( W ( M )) .
To prove the claim, consistency gives F i ( M ) ⊆ O i F_i(\mathbf{M})\subseteq O_i F i ( M ) ⊆ O i for every i i i . Therefore, every element missed by O \mathbf{O} O lies in W ( M ) W(\mathbf{M}) W ( M ) . These elements have total weight OPT m i s s ( I ) \operatorname{OPT}_{\mathrm{miss}}(I) OPT miss ( I ) , so
w ( W ( M ) ∩ ⋃ i = 1 k O i ) = w ( W ( M ) ) − OPT m i s s ( I ) > ε 1 + ε w ( W ( M ) ) . w\left(W(\mathbf{M})\cap\bigcup_{i=1}^{k}O_i\right)=w(W(\mathbf{M}))-\operatorname{OPT}_{\mathrm{miss}}(I)>\frac{\varepsilon}{1+\varepsilon}w(W(\mathbf{M})). w ( W ( M ) ∩ i = 1 ⋃ k O i ) = w ( W ( M )) − OPT miss ( I ) > 1 + ε ε w ( W ( M )) .
Since the left-hand side is at most ∑ i = 1 k w ( O i ∩ W ( M ) ) \sum_{i=1}^{k}w(O_i\cap W(\mathbf{M})) ∑ i = 1 k w ( O i ∩ W ( M )) , some i ∈ [ k ] i\in[k] i ∈ [ k ] satisfies
w ( O i ∩ W ( M ) ) > ε k ( 1 + ε ) w ( W ( M ) ) = δ w ( W ( M ) ) , w(O_i\cap W(\mathbf{M}))>\frac{\varepsilon}{k(1+\varepsilon)}w(W(\mathbf{M}))=\delta w(W(\mathbf{M})), w ( O i ∩ W ( M )) > k ( 1 + ε ) ε w ( W ( M )) = δ w ( W ( M )) ,
as required.
For the base case, consider a reachable state M \mathbf{M} M consistent with O \mathbf{O} O and satisfying q ( M ) = 0 q(\mathbf{M})=0 q ( M ) = 0 . If w ( W ( M ) ) ≤ ( 1 + ε ) OPT m i s s ( I ) w(W(\mathbf{M}))\le(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ( M )) ≤ ( 1 + ε ) OPT miss ( I ) , Claim 1 proves the required bound. Otherwise, Claim 2 gives an index i ∈ [ k ] i\in[k] i ∈ [ k ] satisfying the displayed inequality. Since ∑ h = 1 k ∣ M h ∣ = k d \sum_{h=1}^{k}|M_h|=kd ∑ h = 1 k ∣ M h ∣ = k d and ∣ M h ∣ ≤ d |M_h|\le d ∣ M h ∣ ≤ d for every h ∈ [ k ] h\in[k] h ∈ [ k ] , we have ∣ M h ∣ = d |M_h|=d ∣ M h ∣ = d for every h h h . The inequality above implies that O i ∩ W ( M ) ≠ ∅ O_i\cap W(\mathbf{M})\ne\emptyset O i ∩ W ( M ) = ∅ because all weights are positive. Choose u u u from this set and write M i = { u 1 , … , u d } M_i=\{u_1,\ldots,u_d\} M i = { u 1 , … , u d } in insertion order. By Lemma 5.2 , there are pairwise distinct witness sets R 1 , … , R d R_1,\ldots,R_d R 1 , … , R d . Since u ∈ W ( M ) ⊆ U ∖ F i ( M ) u\in W(\mathbf{M})\subseteq U\setminus F_i(\mathbf{M}) u ∈ W ( M ) ⊆ U ∖ F i ( M ) , there is a set R d + 1 ∈ P i ( M ) R_{d+1}\in\mathcal{P}_i(\mathbf{M}) R d + 1 ∈ P i ( M ) that misses u u u . Every set in P i ( M ) \mathcal{P}_i(\mathbf{M}) P i ( M ) contains M i M_i M i , so u j ∈ R d + 1 u_j\in R_{d+1} u j ∈ R d + 1 for every j ∈ [ d ] j\in[d] j ∈ [ d ] . Moreover, u ∉ M i u\notin M_i u ∈ / M i because M i ⊆ F i ( M ) M_i\subseteq F_i(\mathbf{M}) M i ⊆ F i ( M ) , and, for every j ∈ [ d ] j\in[d] j ∈ [ d ] , we have R d + 1 ≠ R j R_{d+1}\ne R_j R d + 1 = R j because u j ∈ R d + 1 ∖ R j u_j\in R_{d+1}\setminus R_j u j ∈ R d + 1 ∖ R j . Therefore, for every u 1 , … , u d u_1,\ldots,u_d u 1 , … , u d , you form a semi-ladder of order d + 1 d+1 d + 1 , a contradiction. Thus, w ( W ( M ) ) > ( 1 + ε ) OPT m i s s ( I ) w(W(\mathbf{M}))>(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ( M )) > ( 1 + ε ) OPT miss ( I ) is impossible, which proves P ( 0 ) P(0) P ( 0 ) .
For the inductive step, let r ∈ { 1 , … , k d } r\in\{1,\ldots,kd\} r ∈ { 1 , … , k d } and assume P ( r − 1 ) P(r-1) P ( r − 1 ) . Let M \mathbf{M} M be a reachable state consistent with O \mathbf{O} O and satisfying q ( M ) = r q(\mathbf{M})=r q ( M ) = r . If w ( W ( M ) ) ≤ ( 1 + ε ) OPT m i s s ( I ) w(W(\mathbf{M}))\le(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ( M )) ≤ ( 1 + ε ) OPT miss ( I ) , Claim 1 proves the required bound. Otherwise, Claim 2 gives an index i ∈ [ k ] i\in[k] i ∈ [ k ] such that w ( O i ∩ W ( M ) ) > δ w ( W ( M ) ) w(O_i\cap W(\mathbf{M}))>\delta w(W(\mathbf{M})) w ( O i ∩ W ( M )) > δ w ( W ( M )) . Moreover, q ( M ) > 0 q(\mathbf{M})>0 q ( M ) > 0 implies ∑ h = 1 k ∣ M h ∣ < k d \sum_{h=1}^{k}|M_h|<kd ∑ h = 1 k ∣ M h ∣ < k d , and w ( W ( M ) ) > ( 1 + ε ) OPT m i s s ( I ) w(W(\mathbf{M}))>(1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) w ( W ( M )) > ( 1 + ε ) OPT miss ( I ) implies W ( M ) ≠ ∅ W(\mathbf{M})\ne\emptyset W ( M ) = ∅ . The algorithm therefore computes a weighted δ \delta δ -net Z Z Z . Because O i ∈ P i ( M ) O_i\in\mathcal{P}_i(\mathbf{M}) O i ∈ P i ( M ) , the set O i ∩ W ( M ) O_i \cap W(\mathbf{M}) O i ∩ W ( M ) belongs to the restricted family and has weight greater than δ w ( W ( M ) ) \delta w(W(\mathbf{M})) δ w ( W ( M )) . Hence Z Z Z contains an element u ∈ O i ∩ W ( M ) u \in O_i \cap W(\mathbf{M}) u ∈ O i ∩ W ( M ) .
Let M ′ \mathbf{M}' M ′ be obtained by replacing M i M_i M i with M i ∪ { u } M_i \cup\{u\} M i ∪ { u } . The set O i O_i O i is eligible at coordinate i i i and contains u u u , so the algorithm explores this recursive call. Moreover, M i ⊆ O i M_i \subseteq O_i M i ⊆ O i and u ∈ O i u \in O_i u ∈ O i , so M ′ \mathbf{M}' M ′ is consistent with O \mathbf{O} O . Since u ∈ W ( M ) u \in W(\mathbf{M}) u ∈ W ( M ) and M i ⊆ F i ( M ) M_i \subseteq F_i(\mathbf{M}) M i ⊆ F i ( M ) , we have u ∉ M i u \notin M_i u ∈ / M i , and therefore q ( M ′ ) = q ( M ) − 1 q(\mathbf{M}') = q(\mathbf{M}) - 1 q ( M ′ ) = q ( M ) − 1 . By the induction hypothesis, the call at M ′ \mathbf{M}' M ′ returns a subfamily of uncovered weight at most ( 1 + ε ) OPT m i s s ( I ) (1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) ( 1 + ε ) OPT miss ( I ) . The call at M \mathbf{M} M returns a subfamily of no larger value. This proves P ( r ) P(r) P ( r ) .
The initial state is consistent with O \mathbf{O} O , so applying the induction claim to this state proves the lemma. □ \square □
Theorem 5.4. For every d ≥ 0 d \ge0 d ≥ 0 , weighted Min-UnCoverage on instances whose incidence graph has semi-ladder index at most d d d admits a deterministic EPAS parameterized by k + d k+d k + d . For 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 , its running time is
( d k ε ) O ( d 2 k ε 2 log 2 k ε ) N O ( 1 ) , \left(\frac{dk}{\varepsilon}\right)^{O\left(\frac{d^{2}k}{\varepsilon^{2}}\log\frac{2k}{\varepsilon}\right)}N^{O(1)}, ( ε d k ) O ( ε 2 d 2 k l o g ε 2 k ) N O ( 1 ) ,
for d ≥ 1 d \ge1 d ≥ 1 , where N N N includes the incidence representation and the binary encoding of the rational weights. The case d = 0 d=0 d = 0 is solvable in O ( N ) O(N) O ( N ) time.
Proof. It is enough to consider 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 . For ε > 1 \varepsilon> 1 ε > 1 , running the algorithm with accuracy parameter 1 1 1 gives approximation factor 2 ≤ 1 + ε 2 \le1+\varepsilon 2 ≤ 1 + ε .
If k = 0 k=0 k = 0 or S = ∅ S=\varnothing S = ∅ , return the empty subfamily. Hence assume k ≥ 1 k \ge1 k ≥ 1 and S ≠ ∅ S \ne\varnothing S = ∅ . If d = 0 d=0 d = 0 , every set contains every ground element: a set and an element not contained in it would form a semi-ladder of order one. Thus, an arbitrary set is optimal and can be returned in O ( N ) O(N) O ( N ) time. We may therefore assume that d ≥ 1 d \ge1 d ≥ 1 . Correctness follows from Lemma 5.3.
Recall that δ = ε / ( k ( 1 + ε ) ) \delta=\varepsilon/(k(1+\varepsilon)) δ = ε / ( k ( 1 + ε )) . By Lemma 5.1, the weighted δ \delta δ -net computed at any call has size
O ( d + 1 δ log 1 δ ) . O\left(\frac{d+1}{\delta}\log\frac{1}{\delta}\right). O ( δ d + 1 log δ 1 ) .
Since the algorithm considers at most k k k coordinates for each element of this weighted δ \delta δ -net, every call has
O ( k ( d + 1 ) δ log 1 δ ) O\left(\frac{k(d+1)}{\delta}\log\frac{1}{\delta}\right) O ( δ k ( d + 1 ) log δ 1 )
children.
By Lemma 5.2, every skeleton has size at most d d d . Before making a recursive call, the algorithm adds one new element to exactly one skeleton. Hence every root-to-leaf path has length at most k d kd k d . The total number of calls is therefore
( k ( d + 1 ) δ log 1 δ ) O ( k d ) . \left(\frac{k(d+1)}{\delta}\log\frac{1}{\delta}\right)^{O(kd)}. ( δ k ( d + 1 ) log δ 1 ) O ( k d ) .
We next bound the work in one call. The restricted set system is obtained by restricting eligible input sets to W ( M ) W(\mathbf{M}) W ( M ) , so its encoding size is at most N N N . By scanning the incidence lists for each coordinate and each skeleton element, the algorithm can construct the eligible families, the forced and unresolved elements, the restricted set system, and the current candidate using O ( k d N ) O(kdN) O ( k d N ) incidence operations. Computing and comparing candidate weights takes polynomial time in N N N , since each value is a sum of input rational weights. By Lemma 5.1, using the weighted δ \delta δ -net construction of Kundu et al. [23 ] , this weighted δ \delta δ -net can be computed in
( d + 1 δ ) O ( ( d + 1 ) 2 δ log 1 δ ) N O ( 1 ) \left(\frac{d+1}{\delta}\right)^{O\left(\frac{(d+1)^2}{\delta}\log\frac{1}{\delta}\right)}N^{O(1)} ( δ d + 1 ) O ( δ ( d + 1 ) 2 l o g δ 1 ) N O ( 1 )
time. Thus, the total running time is
( k ( d + 1 ) δ log 1 δ ) O ( k d ) ( d + 1 δ ) O ( ( d + 1 ) 2 δ log 1 δ ) N O ( 1 ) . \left(\frac{k(d+1)}{\delta}\log\frac{1}{\delta}\right)^{O(kd)}\left(\frac{d+1}{\delta}\right)^{O\left(\frac{(d+1)^2}{\delta}\log\frac{1}{\delta}\right)}N^{O(1)}. ( δ k ( d + 1 ) log δ 1 ) O ( k d ) ( δ d + 1 ) O ( δ ( d + 1 ) 2 l o g δ 1 ) N O ( 1 ) .
The first factor bounds the number of recursive calls. Since 1 / δ ≥ 2 k 1/\delta\ge2k 1/ δ ≥ 2 k , we have k ≤ 1 / δ ≤ ( d + 1 ) / δ k \le1/\delta\le(d+1)/\delta k ≤ 1/ δ ≤ ( d + 1 ) / δ . Also, log ( 1 / δ ) ≤ 1 / δ ≤ ( d + 1 ) / δ \log(1/\delta) \le1/\delta\le(d+1)/\delta log ( 1/ δ ) ≤ 1/ δ ≤ ( d + 1 ) / δ . Thus, all three factors in its base are at most ( d + 1 ) / δ (d+1)/\delta ( d + 1 ) / δ , and ( k ( d + 1 ) / δ ) log ( 1 / δ ) ≤ ( ( d + 1 ) / δ ) 3 (k(d+1)/\delta)\log(1/\delta) \le((d+1)/\delta)^3 ( k ( d + 1 ) / δ ) log ( 1/ δ ) ≤ (( d + 1 ) / δ ) 3 . It follows that the first factor is at most ( ( d + 1 ) / δ ) O ( k d ) ((d+1)/\delta)^{O(kd)} (( d + 1 ) / δ ) O ( k d ) . Moreover,
( d + 1 ) 2 δ log 1 δ ≥ 2 ( log 2 ) k d . \frac{(d+1)^2}{\delta}\log\frac{1}{\delta} \ge2(\log2)kd. δ ( d + 1 ) 2 log δ 1 ≥ 2 ( log 2 ) k d .
where we use 1 / δ ≥ 2 k 1/\delta\ge2k 1/ δ ≥ 2 k , log ( 1 / δ ) ≥ log 2 \log(1/\delta) \ge\log2 log ( 1/ δ ) ≥ log 2 , and ( d + 1 ) 2 ≥ d (d+1)^2 \ge d ( d + 1 ) 2 ≥ d . Therefore, the weighted δ \delta δ -net construction time absorbs the first factor, and the total running time is
( d + 1 δ ) O ( ( d + 1 ) 2 δ log 1 δ ) N O ( 1 ) . \left(\frac{d+1}{\delta}\right)^{O\left(\frac{(d+1)^2}{\delta}\log\frac{1}{\delta}\right)}N^{O(1)}. ( δ d + 1 ) O ( δ ( d + 1 ) 2 l o g δ 1 ) N O ( 1 ) .
Finally, d + 1 ≤ 2 d d+1 \le2d d + 1 ≤ 2 d and 1 / δ ≤ 2 k / ε 1/\delta\le2k/\varepsilon 1/ δ ≤ 2 k / ε . Therefore, ( d + 1 ) / δ ≤ 4 d k / ε (d+1)/\delta\le4dk/\varepsilon ( d + 1 ) / δ ≤ 4 d k / ε and log ( 1 / δ ) ≤ log ( 2 k / ε ) \log(1/\delta) \le\log(2k/\varepsilon) log ( 1/ δ ) ≤ log ( 2 k / ε ) . Substituting these bounds gives
( d k ε ) O ( d 2 k ε log 2 k ε ) N O ( 1 ) , \left(\frac{dk}{\varepsilon}\right)^{O\left(\frac{d^2k}{\varepsilon}\log\frac{2k}{\varepsilon}\right)}N^{O(1)}, ( ε d k ) O ( ε d 2 k l o g ε 2 k ) N O ( 1 ) ,
which is fixed-parameter tractable in k + d + 1 / ε k+d+1/\varepsilon k + d + 1/ ε .
By Observation 2.6, every K b , b K_{b,b} K b , b -free incidence graph has semi-ladder index less than 2 b 2b 2 b . Thus, Theorem 5.4 also applies to weighted K b , b K_{b,b} K b , b -free instances. Bounded semi-ladder index is more general because it permits arbitrarily large bicliques.
Approximating the Cardinality Bound (k k k )
This section turns from approximating the uncovered or unsatisfied weight to relaxing the cardinality bound. Suppose that a solution using at most k k k selectable objects leaves weight at most t t t uncovered or unsatisfied. Can an FPT algorithm achieve the same bound using at most g ( k , d ) g(k,d) g ( k , d ) objects, for some computable function g g g ? Because the bound t t t is fixed, this question is equivalent in the complementary maximization formulation.
For Min-UnCoverage, this is the weighted Partial Set Cover problem; the relevant positive results and limitations are summarized in Table 2 . For Min-Unsat SAT and Min-Unsat CSP, we prove that, unless FPT = W[1 ] , no FPT algorithm can always attain the same bound t t t after replacing k k k by g ( k , d ) g(k,d) g ( k , d ) , for any computable function g g g , under any of the structural restrictions considered here.
Observation 6.1 (Exact-cardinality gap). Let I I I be an underlying instance, let k k k be a cardinality bound, and let t t t be a prescribed upper bound on its uncovered or unsatisfied weight. Suppose that every solution attaining this bound selects exactly k k k sets, or, in the SAT/CSP setting, sets exactly k k k variables to true. Then
OPT ( I , k ) > t ⟹ OPT ( I , q ) > t for every q ≥ 0. \operatorname{OPT}(I,k) > t \quad\Longrightarrow\quad\operatorname{OPT}(I,q) > t \qquad\text{for every } q \ge0. OPT ( I , k ) > t ⟹ OPT ( I , q ) > t for every q ≥ 0. Consequently, increasing the cardinality bound from k k k to any value q q q , in particular, to any computable function g ( k , d ) g(k,d) g ( k , d ) , cannot produce a solution attaining the prescribed bound.
Proof. Suppose instead that OPT ( I , q ) ≤ t \operatorname{OPT}(I,q) \le t OPT ( I , q ) ≤ t for some q ≥ 0 q \ge0 q ≥ 0 . Then there is a solution whose uncovered or unsatisfied weight is at most t t t . By assumption, this solution uses exactly k k k sets or true variables and is therefore feasible under the cardinality bound k k k . Hence OPT ( I , k ) ≤ t \operatorname{OPT}(I,k) \le t OPT ( I , k ) ≤ t , contradicting OPT ( I , k ) > t \operatorname{OPT}(I,k) > t OPT ( I , k ) > t .
An ordinary bounded-cardinality hardness reduction would not suffice, since a no-instance under the cardinality bound k k k might still admit an assignment of larger Hamming weight whose unsatisfied weight is at most t t t . Our reductions rule out this possibility by ensuring that every assignment attaining the prescribed bound has Hamming weight exactly k k k . By Observation 6.1 , no assignment of any Hamming weight attains the bound in a no-instance, so replacing k k k by any computable function g ( k , d ) g(k,d) g ( k , d ) cannot help.
The targets in the constructions below may be positive. These results concern preserving a prescribed target and are separate from multiplicative-gap hardness for approximating a positive optimum value.
Hardness under Bounded Arity for Min-Unsat SAT
The EPAS in § 3 approximates the total weight of unsatisfied constraints while respecting the cardinality bound. We now show that the reverse tradeoff, preserving a bound on the unsatisfied weight while relaxing the cardinality bound, is impossible even for clauses of arity three. The reduction ensures that every assignment attaining the prescribed bound has Hamming weight exactly k k k . Consequently, by Observation 6.1 , a no-instance admits no assignment of any Hamming weight attaining this bound. We reduce from Multicolored Clique to Min-Unsat SAT as follows.
Construction. Let ( G , V 1 , … , V r ) (G,V_1,\ldots,V_r) ( G , V 1 , … , V r ) be an instance of Multicolored Clique, where V ( G ) = V 1 ∪ ˙ ⋯ ∪ ˙ V r V(G) = V_1 \mathbin{\dot\cup} \cdots\mathbin{\dot\cup} V_r V ( G ) = V 1 ∪ ˙ ⋯ ∪ ˙ V r is the partition into color classes, and let n = ∣ V ( G ) ∣ n = \lvert V(G)\rvert n = ∣ V ( G )∣ . Introduce a Boolean variable x v x_v x v for every v ∈ V ( G ) v \in V(G) v ∈ V ( G ) . Call a pair of distinct vertices { u , v } \{u,v\} { u , v } forbidden if either u u u and v v v belong to the same color class, or they belong to different color classes and u v ∉ E ( G ) uv \notin E(G) uv ∈ / E ( G ) . Thus, a set containing no forbidden pair contains at most one vertex from each color class and induces a clique.
For every vertex v ∈ V ( G ) v \in V(G) v ∈ V ( G ) , add the unit clause ( x v ) (x_v) ( x v ) .
Set W = n + 1 W = n + 1 W = n + 1 . For every forbidden pair { u , v } \{u,v\} { u , v } and every j ∈ [ W ] j \in[W] j ∈ [ W ] , introduce a fresh variable z u v , j z_{uv,j} z uv , j and add the gadget clauses ( ¬ x u ∨ ¬ x v ∨ z u v , j ) (\neg x_u \lor\neg x_v \lor z_{uv,j}) ( ¬ x u ∨ ¬ x v ∨ z uv , j ) and ( ¬ z u v , j ) (\neg z_{uv,j}) ( ¬ z uv , j ) .
Set k = r k = r k = r and t = n − r t = n-r t = n − r .
Let Φ G \Phi_G Φ G denote the resulting formula. Every clause has arity at most three.
Claim 6.2. G G G contains a multicolored clique of size r r r if and only if Φ G \Phi_G Φ G has an assignment leaving at most t t t clauses unsatisfied.
Proof. ( ⇒ ) (\Rightarrow) ( ⇒ ) Suppose first that G G G contains a multicolored clique S = { v 1 , … , v r } S = \{v_1,\ldots,v_r\} S = { v 1 , … , v r } , where v i ∈ V i v_i \in V_i v i ∈ V i . Set x v = 1 x_v = 1 x v = 1 exactly for v ∈ S v \in S v ∈ S and set every fresh variable z u v , j z_{uv,j} z uv , j to zero. Since S S S contains no forbidden pair, every clause involving a fresh variable is satisfied. Among the unit clauses ( x v ) (x_v) ( x v ) , exactly those corresponding to vertices outside S S S are unsatisfied. Hence the assignment leaves exactly n − r = t n-r=t n − r = t clauses unsatisfied and has Hamming weight exactly r = k r=k r = k .
( ⇐ ) (\Leftarrow) ( ⇐ ) Suppose that τ \tau τ is an assignment to Φ G \Phi_G Φ G leaving at most t = n − r t=n-r t = n − r clauses unsatisfied, and let S = { v ∈ V ( G ) : τ ( x v ) = 1 } S = \{v \in V(G) : \tau(x_v)=1\} S = { v ∈ V ( G ) : τ ( x v ) = 1 } . We first claim that S S S contains no forbidden pair. Indeed, suppose that { u , v } ⊆ S \{u,v\} \subseteq S { u , v } ⊆ S is forbidden. Then, for every j ∈ [ W ] j \in[W] j ∈ [ W ] , the two corresponding clauses reduce to ( z u v , j ) (z_{uv,j}) ( z uv , j ) and ( ¬ z u v , j ) (\neg z_{uv,j}) ( ¬ z uv , j ) , so at least one of them is unsatisfied. Thus τ \tau τ leaves at least W = n + 1 > n − r = t W=n+1>n-r=t W = n + 1 > n − r = t clauses unsatisfied, a contradiction. Hence S S S contains no forbidden pair.
Therefore, S S S contains at most one vertex from each color class and induces a clique, so ∣ S ∣ ≤ r |S| \le r ∣ S ∣ ≤ r . On the other hand, the unit clauses ( x v ) (x_v) ( x v ) alone contribute exactly n − ∣ S ∣ n-|S| n − ∣ S ∣ unsatisfied clauses. Since τ \tau τ leaves at most n − r n-r n − r clauses unsatisfied, we have n − ∣ S ∣ ≤ n − r n-|S| \le n-r n − ∣ S ∣ ≤ n − r , and hence ∣ S ∣ ≥ r |S| \ge r ∣ S ∣ ≥ r . Thus ∣ S ∣ = r |S|=r ∣ S ∣ = r , so S S S contains exactly one vertex from each color class and is a multicolored clique.
Theorem 6.3. Unless F P T = W [ 1 ] \mathrm{FPT} = W[1] FPT = W [ 1 ] , for every computable function g : N 2 → N g : \mathbb{N}^{2} \to\mathbb{N} g : N 2 → N satisfying g ( k , d ) ≥ k g(k,d) \ge k g ( k , d ) ≥ k , there is no f ( k , d ) N O ( 1 ) f(k,d)N^{O(1)} f ( k , d ) N O ( 1 ) -time algorithm for unweighted Min-Unsat SAT with clause arity at most d d d that, whenever OPT ( I , k ) ≤ t \operatorname{OPT}(I,k) \le t OPT ( I , k ) ≤ t , returns an assignment of Hamming weight at most g ( k , d ) g(k,d) g ( k , d ) and objective value at most t t t . In particular, no finite-factor approximation of the cardinality bound is possible in FPT time parameterized by k k k while preserving the objective target, even for d = 3 d=3 d = 3 .
Proof. By Claim 6.2 , G G G has a multicolored clique if and only if Φ G \Phi_G Φ G has an assignment leaving at most t = n − r t=n-r t = n − r clauses unsatisfied. The forward direction gives such an assignment of Hamming weight exactly r = k r=k r = k . Conversely, the proof of the claim shows that every assignment attaining this bound sets exactly r r r original variables to one. The corresponding n − r = t n-r=t n − r = t unsatisfied unit clauses exhaust the bound, so every gadget clause is satisfied. In particular, every clause ( ¬ z u v , j ) (\neg z_{uv,j}) ( ¬ z uv , j ) is satisfied, and hence every fresh variable is zero. Thus every assignment attaining the bound has Hamming weight exactly k k k .
The hypotheses of Observation 6.1 are therefore satisfied. On a yes-instance an assignment of Hamming weight k k k attains the bound, whereas on a no-instance no assignment of any Hamming weight does. An algorithm with the guarantee in the theorem would consequently decide Multicolored Clique in FPT time by running it on the constructed instance and checking whether its output leaves at most t t t clauses unsatisfied. Since k = r k=r k = r and d = 3 d=3 d = 3 , this is a parameterized reduction, completing the proof. □
Hardness for Bounded-Variable-Frequency Min-Unsat SAT
For bounded variable frequency, we show that approximating the cardinality bound is again impossible. As discussed after Observation 6.1 , we amplify the cost of leaving a clause unsatisfied so that even an assignment of unrestricted Hamming weight cannot attain the target in the no-case. For our purpose, we reduce from an instance of Multicolored Clique to an equivalent instance of Min-Unsat SAT as follows.
Construction. Let ( G , V 1 , … , V r ) (G,V_1,\ldots,V_r) ( G , V 1 , … , V r ) be an instance of Multicolored Clique. If E ( V i , V j ) = ∅ E(V_i,V_j)=\varnothing E ( V i , V j ) = ∅ for some pair of distinct color classes, then G G G is a no-instance; in this case we return the fixed formula ( z ) ∧ ( ¬ z ) (z) \land(\neg z) ( z ) ∧ ( ¬ z ) with cardinality bound and objective target both zero. We may therefore assume that every pair of color classes has at least one edge.
We first apply the bounded-variable-frequency construction from § 4 . By Claims 4.4 and 4.5 , it produces a formula Φ G \Phi_G Φ G and a cardinality bound K = r + ( r 2 ) K=r+\binom{r}{2} K = r + ( 2 r ) such that G G G contains a multicolored clique if and only if Φ G \Phi_G Φ G has a satisfying assignment of Hamming weight at most K K K . Moreover, every variable of Φ G \Phi_G Φ G has frequency at most d 0 = max { r , 3 } d_0=\max\{r,3\} d 0 = max { r , 3 } .
We construct a new formula Ψ G \Psi_G Ψ G as follows.
Set W = K + 1 W=K+1 W = K + 1 . For every clause C C C of Φ G \Phi_G Φ G and every j ∈ [ W ] j \in[W] j ∈ [ W ] , introduce a fresh variable z C , j z_{C,j} z C , j and add the clauses ( C ∨ z C , j ) (C \lor z_{C,j}) ( C ∨ z C , j ) and ( ¬ z C , j ) (\neg z_{C,j}) ( ¬ z C , j ) .
For every original variable x x x of Φ G \Phi_G Φ G , add the unit clause ( ¬ x ) (\neg x) ( ¬ x ) .
Set k = K k=K k = K and t = K t=K t = K .
Note that every original variable has frequency at most W d 0 + 1 Wd_0+1 W d 0 + 1 , while every fresh variable has frequency exactly two.
Claim 6.4. G G G contains a multicolored clique of size r r r if and only if Ψ G \Psi_G Ψ G has an assignment leaving at most t t t clauses unsatisfied.
Proof. ( ⇒ ) (\Rightarrow) ( ⇒ ) Suppose first that G G G contains a multicolored clique. By the forward direction of Claim 4.5, Φ G \Phi_G Φ G has a satisfying assignment of Hamming weight at most K K K . The formula contains exactly K K K selection clauses with pairwise disjoint variable sets, so this assignment has Hamming weight exactly K K K . Extend it by setting every fresh variable z C , j z_{C,j} z C , j to zero. Since every clause C C C of Φ G \Phi_G Φ G is satisfied, both ( C ∨ z C , j ) (C \lor z_{C,j}) ( C ∨ z C , j ) and ( ¬ z C , j ) (\lnot z_{C,j}) ( ¬ z C , j ) are satisfied for every C C C and j j j . Among the unit clauses ( ¬ x ) (\lnot x) ( ¬ x ) , exactly those corresponding to the K K K original variables set to one are unsatisfied. Hence the assignment leaves exactly K = t K = t K = t clauses unsatisfied and has Hamming weight exactly K = k K = k K = k .
( ⇐ ) (\Leftarrow) ( ⇐ ) Suppose that τ \tau τ is an assignment to Ψ G \Psi_G Ψ G leaving at most t = K t = K t = K clauses unsatisfied. We first claim that the restriction of τ \tau τ to the original variables satisfies every clause of Φ G \Phi_G Φ G . Indeed, suppose that some clause C C C of Φ G \Phi_G Φ G is unsatisfied. Then, for every j ∈ [ W ] j \in[W] j ∈ [ W ] , the two corresponding clauses reduce to ( z C , j ) (z_{C,j}) ( z C , j ) and ( ¬ z C , j ) (\lnot z_{C,j}) ( ¬ z C , j ) , so at least one of them is unsatisfied. Thus τ \tau τ leaves at least W = K + 1 > t W = K + 1 > t W = K + 1 > t clauses unsatisfied, a contradiction.
Hence the restriction of τ \tau τ satisfies Φ G \Phi_G Φ G . Let s s s be the number of original variables set to one. The unit clauses ( ¬ x ) (\lnot x) ( ¬ x ) alone contribute exactly s s s unsatisfied clauses. Since τ \tau τ leaves at most K K K clauses unsatisfied, we have s ≤ K s \le K s ≤ K . Thus Φ G \Phi_G Φ G has a satisfying assignment of Hamming weight at most K K K , and hence the reverse direction of Claim 4.5 implies that G G G contains a multicolored clique.
Theorem 6.5. Unless FPT = W[1 ] , for every computable function g : N 2 → N g : \mathbb{N}^{2} \to\mathbb{N} g : N 2 → N satisfying g ( k , d ) ≥ k g(k,d) \ge k g ( k , d ) ≥ k , there is no f ( k , d ) N O ( 1 ) f(k,d)N^{O(1)} f ( k , d ) N O ( 1 ) -time algorithm for unweighted Min-Unsat SAT with maximum variable frequency at most d d d that, whenever OPT( I , k ) ≤ t (I,k) \le t ( I , k ) ≤ t , returns an assignment of Hamming weight at most g ( k , d ) g(k,d) g ( k , d ) and objective value at most t t t . In particular, no finite-factor approximation of the cardinality bound is possible in FPT time parameterized by k + d k + d k + d while preserving the objective target.
Proof. By Claim 6.4, G G G has a multicolored clique if and only if Ψ G \Psi_G Ψ G has an assignment leaving at most t = K t = K t = K clauses unsatisfied. In the forward direction, the constructed assignment has Hamming weight exactly K = k K = k K = k .
For the reverse direction, recall that Φ G \Phi_G Φ G contains exactly K K K selection clauses with pairwise disjoint variable sets. Every satisfying assignment of Φ G \Phi_G Φ G therefore sets at least K K K original variables to one. The proof of Claim 6.4 shows that an assignment to Ψ G \Psi_G Ψ G attaining the bound restricts to a satisfying assignment of Φ G \Phi_G Φ G with at most K K K true variables. It consequently has exactly K K K true original variables. The corresponding K = t K = t K = t unit clauses ( ¬ x ) (\lnot x) ( ¬ x ) exhaust the bound, so all remaining clauses are satisfied. In particular, every clause ( ¬ z C , j ) (\lnot z_{C,j}) ( ¬ z C , j ) is satisfied, and hence all fresh variables are zero. Thus every assignment attaining the bound has Hamming weight exactly K = k K = k K = k .
By Observation 6.1, a no-instance admits no assignment of any Hamming weight attaining the bound. Therefore, an algorithm with the guarantee in the theorem would decide Multicolored Clique in FPT time. Finally, the maximum variable frequency of Ψ G \Psi_G Ψ G satisfies d ≤ ( K + 1 ) d 0 + 1 = O ( r 3 ) d \le(K+1)d_0+1 = O(r^3) d ≤ ( K + 1 ) d 0 + 1 = O ( r 3 ) , while k = K = O ( r 2 ) k = K = O(r^2) k = K = O ( r 2 ) , so the output parameter k + d k+d k + d is bounded by a function of r r r .
The two preceding constructions yield hardness under all the remaining structural restrictions.
Corollary 6.6. Unless FPT = W[1 ] , for every computable function g : N 2 → N g : \mathbb{N}^{2} \to\mathbb{N} g : N 2 → N satisfying g ( k , d ) ≥ k g(k,d) \ge k g ( k , d ) ≥ k , unweighted Min-Unsat SAT admits no f ( k , d ) N O ( 1 ) f(k,d)N^{O(1)} f ( k , d ) N O ( 1 ) -time algorithm that, whenever OPT( I , k ) ≤ t (I,k) \le t ( I , k ) ≤ t , returns an assignment of Hamming weight at most g ( k , d ) g(k,d) g ( k , d ) and unsatisfied weight at most t t t , under any of the following restrictions:
bounded clause or constraint arity;
bounded variable frequency;
K d , d K_{d,d} K d , d -free incidence graphs;
bounded semi-ladder index; or
bounded VC dimension.
The same lower bounds hold for unweighted Min-Unsat CSP. The arity case already holds for d = 3 d = 3 d = 3 . For the last three restrictions, the hardness already holds for K 3 , 3 K_{3,3} K 3 , 3 -free incidence graphs, semi-ladder index at most four, and VC dimension at most two, respectively.
Proof. The bounded-variable-frequency case is Theorem 6.5. All the other claims follow from the arity-three construction in Theorem 6.3, which already has the required exact-cardinality gap.
Its incidence graph is K 3 , 3 K_{3,3} K 3 , 3 -free. Indeed, every fresh variable z u v , j z_{uv,j} z uv , j has degree two and hence cannot lie on the variable side of a K 3 , 3 K_{3,3} K 3 , 3 . The remaining variables are the original variables x v x_v x v , but every clause contains at most two of them, so three such variables cannot have a common clause neighbor.
The clause-degree bound also gives the other two restrictions. A semi-ladder of order ℓ \ell ℓ contains a clause adjacent to at least ℓ − 1 \ell- 1 ℓ − 1 variables, so ℓ ≤ 4 \ell\le4 ℓ ≤ 4 . If ℓ \ell ℓ clauses are shattered by variable neighborhoods, then each of them has at least 2 ℓ − 1 2^{\ell-1} 2 ℓ − 1 distinct variable neighbors. Since every clause has degree at most three, 2 ℓ − 1 ≤ 3 2^{\ell-1} \le3 2 ℓ − 1 ≤ 3 and hence ℓ ≤ 2 \ell\le2 ℓ ≤ 2 .
Finally, every CNF formula is a Boolean CSP instance under the input convention of § 2 , with the cardinality bound, unsatisfied weight, and incidence graph unchanged. □
Thus the additive-one guarantee for coverage on incidence graphs of bounded semi-ladder index contrasts sharply with SAT and Boolean CSP, for which no computable relaxation of the cardinality bound is possible even under bounded arity or bounded variable frequency.
Conclusion
We studied the parameterized approximability of the residual-minimization counterparts of cardinality-constrained coverage and satisfaction problems. Our results reveal a sharp structural distinction between coverage and general satisfaction. Bounded arity yields a deterministic EPAS for weighted Min-Unsat CSP. Via the monotone-CNF encoding, this also gives a deterministic EPAS for weighted Min-UnCoverage when every ground element has bounded frequency. Bounded set size additionally yields an exact FPT algorithm for weighted Min-UnCoverage. For broader restrictions on the incidence graph, bounded semi-ladder index supports a deterministic EPAS for weighted Min-UnCoverage, whereas Min-Unsat SAT and Min-Unsat CSP admit no finite-factor FPT approximation even on unweighted K 3 , 3 K_{3,3} K 3 , 3 -free instances and on instances of semi-ladder index at most four. Bounded VC dimension alone does not permit a finite-factor FPT approximation for any of the three problems.
We also studied relaxing the cardinality bound while maintaining a prescribed upper bound on the uncovered or unsatisfied weight. For weighted Partial Set Cover, bounded semi-ladder index allows an algorithm to meet the same bound using at most k + 1 k + 1 k + 1 sets whenever it can be met using k k k sets. For unweighted Min-Unsat SAT and Min-Unsat CSP, in contrast, no FPT algorithm can preserve the bound under any computable relaxation of the cardinality constraint. This hardness holds under every structural restriction considered here, already for arity three, bounded variable frequency, K 3 , 3 K_{3,3} K 3 , 3 -free incidence graphs, semi-ladder index at most four, and VC dimension at most two. Thus the distinction between coverage and general satisfaction persists both for multiplicative approximation of the residual weight and for relaxation of the cardinality bound.
AI disclosure. OpenAI Codex and Anthropic Claude Opus were used to reorganize and copy-edit the manuscript, formalize the exposition of author-supplied arguments, check proofs for typographical errors and minor logical inconsistencies, suggest clearer phrasing, and draft selected proof passages. The authors are responsible for verifying all mathematical claims, proofs, citations, and the final text.
An Improved EPAS for Unit-Weight Biclique-Free Min-UnCoverage
The EPAS for weighted Min-UnCoverage in Theorem 5.4 applies to K d , d K_{d,d} K d , d -free instances because their semi-ladder index is less than 2 d 2d 2 d . For unit weights, the algorithm in this appendix has better parameter dependence. Throughout this section, every ground element has weight one. Fix d ≥ 2 d \ge2 d ≥ 2 . We describe the algorithm for a current K d , d K_{d,d} K d , d -free instance I = ( U , S , q ) I=(U,S,q) I = ( U , S , q ) , where q q q is the number of sets that may still be selected. The initial instance has q = k q=k q = k . Write m = ∣ U ∣ m=|U| m = ∣ U ∣ , and let N N N denote the input encoding size. Define
OPT m i s s ( I ) = min A ⊆ S ∣ A ∣ ≤ q miss S ( A ) and OPT c o v ( I ) = max A ⊆ S ∣ A ∣ ≤ q cov S ( A ) . \operatorname{OPT}_{\mathrm{miss}}(I)=\min_{\substack{\mathcal{A}\subseteq S\\|\mathcal{A}|\leq q}}\operatorname{miss}_{S}(\mathcal{A}) \quad\text{and}\quad\operatorname{OPT}_{\mathrm{cov}}(I)=\max_{\substack{\mathcal{A}\subseteq S\\|\mathcal{A}|\leq q}}\operatorname{cov}_{S}(\mathcal{A}). OPT miss ( I ) = A ⊆ S ∣ A ∣ ≤ q min miss S ( A ) and OPT cov ( I ) = A ⊆ S ∣ A ∣ ≤ q max cov S ( A ) .
Thus OPT m i s s ( I ) + OPT c o v ( I ) = m \operatorname{OPT}_{\mathrm{miss}}(I)+\operatorname{OPT}_{\mathrm{cov}}(I)=m OPT miss ( I ) + OPT cov ( I ) = m .
If q = 0 q = 0 q = 0 or U U U is empty, the algorithm stops. It also stops and solves the instance exactly when m ≤ 4 d q m \le4dq m ≤ 4 d q . In every other call, it computes two types of solutions. First, it runs a deterministic approximation scheme for Maximum Coverage. This gives the required ( 1 + ε ) (1 + \varepsilon) ( 1 + ε ) -approximation when an optimum solution leaves at least half of U U U uncovered.
Now suppose that an optimum solution leaves fewer than m / 2 m/2 m /2 elements uncovered. It then covers more than m / 2 m/2 m /2 elements with at most q q q sets, so one of its selected sets contains at least m / ( 2 q ) m/(2q) m / ( 2 q ) elements. The algorithm tries every set S S S of at least this size. In the branch for S S S , it selects S S S , removes the elements covered by S S S , and solves the remaining instance recursively with budget q − 1 q - 1 q − 1 . It then lifts the recursive solution back to sets of the current instance. It returns the solution that leaves the fewest elements uncovered.
We first bound the number of large sets that the algorithm may have to try.
Lemma A.1 (Number of large sets). Let ( U , S ) (U,\mathcal{S}) ( U , S ) be a K d , d K_{d,d} K d , d -free set system, where ∣ U ∣ = m |U| = m ∣ U ∣ = m , and let t ≥ 2 d t \ge2d t ≥ 2 d be an integer. Then
∣ { S ∈ S : ∣ S ∣ ≥ t } ∣ ≤ ( d − 1 ) ( 2 m t ) d . \left|\{S \in\mathcal{S}: |S| \ge t\}\right| \le(d - 1)\left(\frac{2m}{t}\right)^d. ∣ { S ∈ S : ∣ S ∣ ≥ t } ∣ ≤ ( d − 1 ) ( t 2 m ) d .
Proof. If t > m t > m t > m , there are no such sets. Assume that t ≤ m t \le m t ≤ m , and let H t = { S ∈ S : ∣ S ∣ ≥ t } H_t = \{S \in\mathcal{S}: |S| \ge t\} H t = { S ∈ S : ∣ S ∣ ≥ t } . Count pairs ( S , D ) (S,D) ( S , D ) such that S ∈ H t S \in H_t S ∈ H t and D D D is a d d d -element subset of S S S . Every set in H t H_t H t contributes at least ( t d ) \binom{t}{d} ( d t ) pairs. Each d d d -element subset of U U U is contained in at most d − 1 d - 1 d − 1 sets, because d d d sets containing the same d d d elements would form a K d , d K_{d,d} K d , d . Therefore,
∣ H t ∣ ( t d ) ≤ ( d − 1 ) ( m d ) . |H_t|\binom{t}{d} \le(d - 1)\binom{m}{d}. ∣ H t ∣ ( d t ) ≤ ( d − 1 ) ( d m ) .
Because t ≥ 2 d t \ge2d t ≥ 2 d , we have t − d + 1 ≥ t / 2 t - d + 1 \ge t/2 t − d + 1 ≥ t /2 . Moreover, for every i ∈ { 0 , … , d − 1 } i \in\{0,\ldots,d - 1\} i ∈ { 0 , … , d − 1 } , we have m − i ≤ m m - i \le m m − i ≤ m and t − i ≥ t − d + 1 t - i \ge t - d + 1 t − i ≥ t − d + 1 . Hence
( m d ) ( t d ) = ∏ i = 0 d − 1 m − i t − i ≤ ( m t − d + 1 ) d ≤ ( 2 m t ) d . \frac{\binom{m}{d}}{\binom{t}{d}} = \prod_{i=0}^{d-1}\frac{m-i}{t-i} \le\left(\frac{m}{t-d+1}\right)^d \le\left(\frac{2m}{t}\right)^d. ( d t ) ( d m ) = i = 0 ∏ d − 1 t − i m − i ≤ ( t − d + 1 m ) d ≤ ( t 2 m ) d .
Combining this inequality with the preceding counting bound proves the lemma.
The second tool solves the instance exactly when the ground set is small.
Lemma A.2 (Exact solution for a small ground set). Given an instance I = ( U , S , q ) I = (U,\mathcal{S},q) I = ( U , S , q ) with m m m ground elements, an optimum solution can be found in 2 O ( m ) N O ( 1 ) 2^{O(m)}N^{O(1)} 2 O ( m ) N O ( 1 ) time.
Proof. For each t ∈ [ m ] t \in[m] t ∈ [ m ] , the deterministic version of Bläser’s color-coding algorithm finds a minimum-cardinality family covering at least t t t elements in 2 O ( t ) N O ( 1 ) 2^{O(t)}N^{O(1)} 2 O ( t ) N O ( 1 ) time [4 , 1 ] . Run it for every t t t and return the solution for the largest t t t achievable with at most q q q sets, or the empty family if no positive t t t is achievable. Since t ≤ m t \le m t ≤ m , all m m m calls together take 2 O ( m ) N O ( 1 ) 2^{O(m)}N^{O(1)} 2 O ( m ) N O ( 1 ) time.
The third tool is the deterministic EPAS for biclique-free Maximum Coverage. Jain et al. established an EPAS directly for Maximum Coverage [21 ] . The improved running time used below follows by applying Manurangsi’s later deterministic scheme for biclique-free Max k k k -Weight SAT to the monotone-CNF encoding [26 ] .
Proposition A.3. Let d ≥ 2 d \ge2 d ≥ 2 and 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 . Given an unweighted K d , d K_{d,d} K d , d -free instance I = ( U , S , q ) I = (U,\mathcal{S},q) I = ( U , S , q ) , a deterministic algorithm returns a subfamily A c o v ⊆ S \mathcal{A}_{\mathrm{cov}} \subseteq\mathcal{S} A cov ⊆ S with ∣ A c o v ∣ ≤ q |\mathcal{A}_{\mathrm{cov}}| \le q ∣ A cov ∣ ≤ q such that
cov ( A c o v ) ≥ ( 1 − ε ) OPT c o v ( I ) . \operatorname{cov}(\mathcal{A}_{\mathrm{cov}}) \ge(1-\varepsilon)\operatorname{OPT}_{\mathrm{cov}}(I). cov ( A cov ) ≥ ( 1 − ε ) OPT cov ( I ) . Its running time is ( d q / ε ) O ( d q ) N O ( 1 ) (dq/\varepsilon)^{O(dq)}N^{O(1)} ( d q / ε ) O ( d q ) N O ( 1 ) .
We now combine Lemmas A.1 and A.2 and Proposition A.3 in the recursive approximation algorithm.
Residual instances. Consider a current instance I = ( U , S , q ) I=(U,\mathcal{S},q) I = ( U , S , q ) with q ≥ 1 q\ge1 q ≥ 1 . Define the branching family H ( I ) = { S ∈ S : ∣ S ∣ ≥ m / ( 2 q ) } H(I)=\{\mathcal{S}\in\mathcal{S}:|\mathcal{S}|\ge m/(2q)\} H ( I ) = { S ∈ S : ∣ S ∣ ≥ m / ( 2 q )} . We next define the instance used after the algorithm selects a set S ∈ H ( I ) \mathcal{S}\in H(I) S ∈ H ( I ) .
Put U S : = U ∖ S U_{\mathcal{S}}:=U\setminus\mathcal{S} U S := U ∖ S and
S S : = { T ∖ S : T ∈ S ∖ { S } } . \mathcal{S}_{\mathcal{S}}:=\{T\setminus\mathcal{S}:T\in\mathcal{S}\setminus\{\mathcal{S}\}\}. S S := { T ∖ S : T ∈ S ∖ { S }} .
If several sets of the current instance give the same member R R R of S S \mathcal{S}_{\mathcal{S}} S S , retain only one copy and fix a representative ρ S ( R ) ∈ S ∖ { S } \rho_{\mathcal{S}}(R)\in\mathcal{S}\setminus\{\mathcal{S}\} ρ S ( R ) ∈ S ∖ { S } satisfying ρ S ( R ) ∖ S = R \rho_{\mathcal{S}}(R)\setminus\mathcal{S}=R ρ S ( R ) ∖ S = R . For B ⊆ S S B\subseteq\mathcal{S}_{\mathcal{S}} B ⊆ S S , write ρ S ( B ) : = { ρ S ( R ) : R ∈ B } \rho_{\mathcal{S}}(B):=\{\rho_{\mathcal{S}}(R):R\in B\} ρ S ( B ) := { ρ S ( R ) : R ∈ B } . Distinct residual sets have distinct representatives, so ∣ ρ S ( B ) ∣ = ∣ B ∣ |\rho_{\mathcal{S}}(B)|=|B| ∣ ρ S ( B ) ∣ = ∣ B ∣ .
Define
I ↓ S : = ( U S , S S , q − 1 ) . I\mathbin{\downarrow}\mathcal{S}:=(U_{\mathcal{S}},\mathcal{S}_{\mathcal{S}},q-1). I ↓ S := ( U S , S S , q − 1 ) .
Its incidence graph is isomorphic to a subgraph of the incidence graph of I I I : delete the vertex S \mathcal{S} S , the element vertices in S \mathcal{S} S , and any set vertices not chosen as representatives. Hence the residual instance remains K d , d K_{d,d} K d , d -free. We write miss I ↓ S ( B ) \operatorname{miss}_{I\mathbin{\downarrow}\mathcal{S}}(B) miss I ↓ S ( B ) for the number of elements in the new ground set that B B B leaves uncovered. For every B ⊆ S S B\subseteq\mathcal{S}_{\mathcal{S}} B ⊆ S S ,
miss S ( ρ S ( B ) ∪ { S } ) = miss I ↓ S ( B ) . (2) \operatorname{miss}_{\mathcal{S}}(\rho_{\mathcal{S}}(B)\cup\{\mathcal{S}\})=\operatorname{miss}_{I\mathbin{\downarrow}\mathcal{S}}(B). \tag*{(2)} miss S ( ρ S ( B ) ∪ { S }) = miss I ↓ S ( B ) . (2)
The recursive algorithm. The full procedure is given in Algorithm 3. If q = 0 q=0 q = 0 or U U U is empty, it returns the empty family. If m ≤ 4 d q m\le4dq m ≤ 4 d q , it uses the exact algorithm from Lemma A.2 . Otherwise, m / ( 2 q ) > 2 d m/(2q)>2d m / ( 2 q ) > 2 d , so Lemma A.1 bounds the size of H ( I ) H(I) H ( I ) . The algorithm computes A c o v A_{\mathrm{cov}} A cov using Proposition A.3 , recursively tries every set in H ( I ) H(I) H ( I ) , and returns the solution that leaves the fewest elements uncovered.
Algorithm 3 ApxMinUnCov( I , d , ε ) (I,d,\varepsilon) ( I , d , ε )
Require: An unweighted K d , d K_{d,d} K d , d -free instance I = ( U , S , q ) I=(U,\mathcal{S},q) I = ( U , S , q ) and ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] .
Ensure: A subfamily A ⊆ S \mathcal{A}\subseteq\mathcal{S} A ⊆ S with ∣ A ∣ ≤ q |\mathcal{A}|\le q ∣ A ∣ ≤ q .
if q = 0 q=0 q = 0 or U = ∅ U=\varnothing U = ∅ then return ∅ \varnothing ∅
if ∣ U ∣ ≤ 4 d q |U|\le4dq ∣ U ∣ ≤ 4 d q then return an optimum solution for budget q q q computed using Lemma A.2
Compute A c o v \mathcal{A}_{\mathrm{cov}} A cov for budget q q q using Proposition A.3
H ← { S ∈ S : ∣ S ∣ ≥ ∣ U ∣ / ( 2 q ) } H\leftarrow\{\mathcal{S}\in\mathcal{S}:|\mathcal{S}|\ge|U|/(2q)\} H ← { S ∈ S : ∣ S ∣ ≥ ∣ U ∣/ ( 2 q )}
A r e c ← ∅ \mathcal{A}_{\mathrm{rec}}\leftarrow\varnothing A rec ← ∅
for all S ∈ H \mathcal{S}\in H S ∈ H do
B S ← ApxMinUnCov ( I ↓ S , d , ε ) \mathcal{B}_{\mathcal{S}}\leftarrow\operatorname{ApxMinUnCov}(I\mathbin{\downarrow}\mathcal{S},d,\varepsilon) B S ← ApxMinUnCov ( I ↓ S , d , ε )
A S ← { S } ∪ ρ S ( B S ) \mathcal{A}_{\mathcal{S}}\leftarrow\{\mathcal{S}\}\cup\rho_{\mathcal{S}}(\mathcal{B}_{\mathcal{S}}) A S ← { S } ∪ ρ S ( B S )
if miss S ( A S ) < miss S ( A r e c ) \operatorname{miss}_{\mathcal{S}}(\mathcal{A}_{\mathcal{S}})<\operatorname{miss}_{\mathcal{S}}(\mathcal{A}_{\mathrm{rec}}) miss S ( A S ) < miss S ( A rec ) then
A r e c ← A S \mathcal{A}_{\mathrm{rec}}\leftarrow\mathcal{A}_{\mathcal{S}} A rec ← A S
return whichever of A c o v \mathcal{A}_{\mathrm{cov}} A cov and A r e c \mathcal{A}_{\mathrm{rec}} A rec leaves fewer elements uncovered
We first prove the approximation guarantee.
Lemma A.4 (Approximation guarantee). Let d ≥ 2 d\ge2 d ≥ 2 , let 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 , and let I = ( U , S , q ) I=(U,\mathcal{S},q) I = ( U , S , q ) be an unweighted K d , d K_{d,d} K d , d -free instance. Then Algorithm 3 returns at most q q q sets that leave at most ( 1 + ε ) OPT m i s s ( I ) (1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) ( 1 + ε ) OPT miss ( I ) ground elements uncovered.
Proof. Fix d ≥ 2 d\ge2 d ≥ 2 and 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 . For q ≥ 0 q\ge0 q ≥ 0 , let P ( q ) P(q) P ( q ) be the following statement: for every unweighted K d , d K_{d,d} K d , d -free instance I = ( U , S , q ) I=(U,\mathcal{S},q) I = ( U , S , q ) , the call ApxMinUnCov( I , d , ε ) (I,d,\varepsilon) ( I , d , ε ) returns at most q q q sets and leaves at most ( 1 + ε ) OPT m i s s ( I ) (1+\varepsilon)\operatorname{OPT}_{\mathrm{miss}}(I) ( 1 + ε ) OPT miss ( I ) elements uncovered. We prove P ( q ) P(q) P ( q ) by induction on q q q . For the base case, let q = 0 q = 0 q = 0 . The algorithm returns the empty family, which is the only feasible solution. Thus it is optimal, and P ( 0 ) P(0) P ( 0 ) holds.
For the inductive step, let q ≥ 1 q \ge1 q ≥ 1 and assume P ( q − 1 ) P(q - 1) P ( q − 1 ) . Fix an unweighted K d , d K_{d,d} K d , d -free instance I = ( U , S , q ) I = (U,\mathcal{S},q) I = ( U , S , q ) , and write m = ∣ U ∣ m = |U| m = ∣ U ∣ . If U U U is empty or m ≤ 4 d q m \le4dq m ≤ 4 d q , the algorithm returns an optimum solution using at most q q q sets. Hence assume that m > 4 d q m > 4dq m > 4 d q .
Every candidate considered by the algorithm uses at most q q q sets. By Proposition A.3, the candidate A c o v \mathcal{A}_{\mathrm{cov}} A cov uses at most q q q sets. For each S ∈ H ( I ) S \in H(I) S ∈ H ( I ) , the residual instance I ↓ S I \mathbin{\downarrow} S I ↓ S remains K d , d K_{d,d} K d , d -free. By the induction hypothesis, the recursive call returns at most q − 1 q - 1 q − 1 residual sets. Since ρ S \rho_S ρ S preserves cardinality, A S = { S } ∪ ρ S ( B S ) \mathcal{A}_S = \{S\} \cup\rho_S(\mathcal{B}_S) A S = { S } ∪ ρ S ( B S ) uses at most q q q sets. Therefore, the family returned by the algorithm is feasible.
We now prove its approximation guarantee. Suppose first that O P T m i s s ( I ) ≥ m / 2 \mathrm{OPT}_{\mathrm{miss}}(I) \ge m/2 OPT miss ( I ) ≥ m /2 . Then O P T c o v ( I ) = m − O P T m i s s ( I ) \mathrm{OPT}_{\mathrm{cov}}(I) = m - \mathrm{OPT}_{\mathrm{miss}}(I) OPT cov ( I ) = m − OPT miss ( I ) is at most O P T m i s s ( I ) \mathrm{OPT}_{\mathrm{miss}}(I) OPT miss ( I ) . The guarantee in Proposition A.3 gives
m i s s S ( A c o v ) = m − c o v S ( A c o v ) ≤ m − ( 1 − ε ) O P T c o v ( I ) = O P T m i s s ( I ) + ε O P T c o v ( I ) ≤ ( 1 + ε ) O P T m i s s ( I ) . \begin{aligned}
\mathrm{miss}_{\mathcal{S}}(\mathcal{A}_{\mathrm{cov}}) &= m - \mathrm{cov}_{\mathcal{S}}(\mathcal{A}_{\mathrm{cov}}) \\
&\le m - (1 - \varepsilon)\mathrm{OPT}_{\mathrm{cov}}(I) \\
&= \mathrm{OPT}_{\mathrm{miss}}(I) + \varepsilon\mathrm{OPT}_{\mathrm{cov}}(I) \\
&\le(1 + \varepsilon)\mathrm{OPT}_{\mathrm{miss}}(I).
\end{aligned} miss S ( A cov ) = m − cov S ( A cov ) ≤ m − ( 1 − ε ) OPT cov ( I ) = OPT miss ( I ) + ε OPT cov ( I ) ≤ ( 1 + ε ) OPT miss ( I ) .
Thus A c o v \mathcal{A}_{\mathrm{cov}} A cov , and therefore the family returned by the algorithm, has the required value.
Now suppose that O P T m i s s ( I ) < m / 2 \mathrm{OPT}_{\mathrm{miss}}(I) < m/2 OPT miss ( I ) < m /2 , and let A ∗ \mathcal{A}^* A ∗ be an optimum solution. It covers more than m / 2 m/2 m /2 elements using at most q q q sets. Therefore, some S ∗ ∈ A ∗ S^* \in\mathcal{A}^* S ∗ ∈ A ∗ contains at least m / ( 2 q ) m/(2q) m / ( 2 q ) elements. Hence S ∗ ∈ H ( I ) S^* \in H(I) S ∗ ∈ H ( I ) , and the algorithm tries the recursive choice that selects S ∗ S^* S ∗ .
Define
B ∗ : = { T ∖ S ∗ : T ∈ A ∗ ∖ { S ∗ } } ⊆ S S ∗ . \mathcal{B}^* := \{T \setminus S^* : T \in\mathcal{A}^* \setminus\{S^*\}\} \subseteq\mathcal{S}_{S^*}. B ∗ := { T ∖ S ∗ : T ∈ A ∗ ∖ { S ∗ }} ⊆ S S ∗ .
Merging duplicate residual sets can only decrease cardinality, so ∣ B ∗ ∣ ≤ q − 1 |\mathcal{B}^*| \le q - 1 ∣ B ∗ ∣ ≤ q − 1 . Moreover, B ∗ \mathcal{B}^* B ∗ leaves exactly the elements left uncovered by A ∗ \mathcal{A}^* A ∗ , and hence O P T m i s s ( I ↓ S ∗ ) ≤ O P T m i s s ( I ) \mathrm{OPT}_{\mathrm{miss}}(I \mathbin{\downarrow} S^*) \le\mathrm{OPT}_{\mathrm{miss}}(I) OPT miss ( I ↓ S ∗ ) ≤ OPT miss ( I ) . Conversely, every solution B \mathcal{B} B for the residual instance lifts to ρ S ∗ ( B ) ∪ { S ∗ } \rho_{S^*}(\mathcal{B}) \cup\{S^*\} ρ S ∗ ( B ) ∪ { S ∗ } , which has the same number of uncovered elements by (2) . Therefore, O P T m i s s ( I ↓ S ∗ ) = O P T m i s s ( I ) \mathrm{OPT}_{\mathrm{miss}}(I \mathbin{\downarrow} S^*) = \mathrm{OPT}_{\mathrm{miss}}(I) OPT miss ( I ↓ S ∗ ) = OPT miss ( I ) .
The residual instance is K d , d K_{d,d} K d , d -free, so the induction hypothesis applies. It returns a solution B S ∗ \mathcal{B}_{S^*} B S ∗ for the residual instance that leaves at most ( 1 + ε ) O P T m i s s ( I ) (1 + \varepsilon)\mathrm{OPT}_{\mathrm{miss}}(I) ( 1 + ε ) OPT miss ( I ) elements uncovered. The lifted solution ρ S ∗ ( B S ∗ ) ∪ { S ∗ } \rho_{S^*}(\mathcal{B}_{S^*}) \cup\{S^*\} ρ S ∗ ( B S ∗ ) ∪ { S ∗ } preserves that number by (2) . The algorithm returns a solution with no larger value. This proves P ( q ) P(q) P ( q ) and completes the induction. □
We can now prove the main result.
Theorem A.5. For every d ≥ 2 d \ge2 d ≥ 2 , unweighted K d , d K_{d,d} K d , d -free Min-UnCoverage admits an EPAS parameterized by k + d k + d k + d . The scheme is deterministic and runs in ( d k / ε ) O ( d k ) N O ( 1 ) (dk/\varepsilon)^{O(dk)}N^{O(1)} ( d k / ε ) O ( d k ) N O ( 1 ) time for 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 , where N N N is the input encoding size.
Proof. It is enough to consider 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 . If ε > 1 \varepsilon> 1 ε > 1 , we run the algorithm with accuracy parameter 1 1 1 ; the resulting approximation factor of 2 2 2 is at most 1 + ε 1 + \varepsilon 1 + ε . Run ApxMinUnCov ( I , d , ε ) \operatorname{ApxMinUnCov}(I,d,\varepsilon) ApxMinUnCov ( I , d , ε ) on the input instance I = ( U , S , k ) I = (U,\mathcal{S},k) I = ( U , S , k ) . The approximation guarantee follows from Lemma A.4.
If k = 0 k = 0 k = 0 , the algorithm stops immediately. Assume therefore that k ≥ 1 k \ge1 k ≥ 1 . We now bound the number of recursive calls. Consider a call on a current instance J = ( U ′ , S ′ , q ) J = (U',\mathcal{S}',q) J = ( U ′ , S ′ , q ) that does not stop, and let m = ∣ U ′ ∣ m = |U'| m = ∣ U ′ ∣ . Since m > 4 d q m > 4dq m > 4 d q , the integer t = ⌈ m / ( 2 q ) ⌉ t = \lceil m/(2q)\rceil t = ⌈ m / ( 2 q )⌉ is at least 2 d 2d 2 d . The family H ( J ) H(J) H ( J ) consists exactly of the sets of size at least t t t . By Lemma A.1,
∣ H ( J ) ∣ ≤ ( d − 1 ) ( 2 m t ) d ≤ ( d − 1 ) ( 4 q ) d ≤ ( d − 1 ) ( 4 k ) d . |H(J)| \le(d - 1)\left(\frac{2m}{t}\right)^d \le(d - 1)(4q)^d \le(d - 1)(4k)^d. ∣ H ( J ) ∣ ≤ ( d − 1 ) ( t 2 m ) d ≤ ( d − 1 ) ( 4 q ) d ≤ ( d − 1 ) ( 4 k ) d .
Each recursive call reduces the remaining budget by one, so there are at most k k k recursive levels. Let B = ( d − 1 ) ( 4 k ) d B = (d - 1)(4k)^d B = ( d − 1 ) ( 4 k ) d . The total number of calls is at most 1 + B + ⋯ + B k ≤ ( 1 + B ) k 1 + B + \cdots+ B^k \le(1 + B)^k 1 + B + ⋯ + B k ≤ ( 1 + B ) k . Every recursive instance, including its representative map, has encoding size O ( N ) O(N) O ( N ) . By Proposition A.3, the Maximum Coverage computation at each nonterminal call therefore takes at most ( d k / ε ) O ( d k ) N O ( 1 ) (dk/\varepsilon)^{O(dk)}N^{O(1)} ( d k / ε ) O ( d k ) N O ( 1 ) time. When the algorithm stops because the ground set is small, it has at most 4 d q ≤ 4 d k 4dq \le4dk 4 d q ≤ 4 d k elements. By Lemma A.2, solving such an instance takes 2 O ( d k ) N O ( 1 ) 2^{O(dk)}N^{O(1)} 2 O ( d k ) N O ( 1 ) time. Constructing branching families and residual instances, and comparing the solutions, takes polynomial time. Therefore, the total running time is at most
( 1 + ( d − 1 ) ( 4 k ) d ) ⋅ ( ( d k / ε ) O ( d k ) + 2 O ( d k ) ) ⋅ N O ( 1 ) = ( d k / ε ) O ( d k ) N O ( 1 ) . \left(1+(d-1)(4k)^d\right)\cdot\left((dk/\varepsilon)^{O(dk)}+2^{O(dk)}\right)\cdot N^{O(1)}=(dk/\varepsilon)^{O(dk)}N^{O(1)}. ( 1 + ( d − 1 ) ( 4 k ) d ) ⋅ ( ( d k / ε ) O ( d k ) + 2 O ( d k ) ) ⋅ N O ( 1 ) = ( d k / ε ) O ( d k ) N O ( 1 ) .
which is fixed-parameter tractable in k + d + 1 / ε k+d+1/\varepsilon k + d + 1/ ε .
For comparison, the unit-weight algorithm of Theorem A.5 runs in ( d k / ε ) O ( d k ) N O ( 1 ) (dk/\varepsilon)^{O(dk)}N^{O(1)} ( d k / ε ) O ( d k ) N O ( 1 ) time. By Observation 2.6, every K d , d K_{d,d} K d , d -free incidence graph has semi-ladder index less than 2 d 2d 2 d . Hence Theorem 5.4 gives, for weighted K d , d K_{d,d} K d , d -free instances, running time
( d k ε ) O ( d 2 k ε log 2 k ε ) N O ( 1 ) . \left(\frac{dk}{\varepsilon}\right)^{O\left(\frac{d^2k}{\varepsilon}\log\frac{2k}{\varepsilon}\right)}N^{O(1)}. ( ε d k ) O ( ε d 2 k l o g ε 2 k ) N O ( 1 ) .
Thus the unit-weight algorithm has better parameter dependence, whereas the weighted algorithm accommodates positive rational weights and applies more generally to incidence graphs of bounded semi-ladder index.
An Exact Algorithm for Weighted Min-UnCoverage with Bounded Set Size
For unweighted Maximum Coverage, fixed-parameter tractability under the combined parameter consisting of the number of selected sets and the maximum set size follows from Bläser’s randomized color-coding algorithm for Partial Set Cover: a family of at most k k k sets of size at most d d d covers at most k d kd k d elements [4 ] . Bonnet et al. gave an alternative deterministic FPT algorithm based on greediness-for-parameterization [13 ] . We adapt Bläser’s color-coding framework to positive rational element weights and make the adaptation deterministic. The proof appears here because it closely follows that framework; the substantive modifications are the treatment of weights and the standard derandomization. This monotone setting is essential: cardinality-constrained Red–Blue Set Cover is W[1 ] -hard parameterized by the number of selected sets plus the red budget, even when every set has size three [2 ] .
Proposition B.1. Weighted Min-UnCoverage on instances in which every set has size at most d d d can be solved exactly by a deterministic algorithm in 2 O ( k d ) N O ( 1 ) 2^{O(kd)}N^{O(1)} 2 O ( k d ) N O ( 1 ) time.
Proof. Let I = ( U , S , w , k ) I=(U,\mathcal{S},w,k) I = ( U , S , w , k ) be such an instance. Since
miss S , w ( A ) = w ( U ) − w ( ⋃ S ∈ A S ) , \operatorname{miss}_{\mathcal{S},w}(\mathcal{A})=w(U)-w\left(\bigcup_{S\in\mathcal{A}}S\right), miss S , w ( A ) = w ( U ) − w ( S ∈ A ⋃ S ) , it suffices to maximize the covered weight. Denote this maximum, over subfamilies of size at most k k k , by OPT c o v ( I ) \operatorname{OPT}_{\mathrm{cov}}(I) OPT cov ( I ) . The cases k = 0 k=0 k = 0 and d = 0 d=0 d = 0 are immediate, so assume k , d ≥ 1 k,d\ge1 k , d ≥ 1 and put p : = k d p:=kd p := k d .
An equivalent disjoint-subset formulation. For every S ∈ S S\in\mathcal{S} S ∈ S and every nonempty T ⊆ S T\subseteq S T ⊆ S , form the ordered pair ( S , T ) (S,T) ( S , T ) . Its first component records the set that will be selected, and its second component records the elements whose weight is counted for that pair. Let
P : = { ( S , T ) : S ∈ S , ∅ ≠ T ⊆ S } , \mathcal{P}:=\{(S,T):S\in\mathcal{S},\ \varnothing\ne T\subseteq S\}, P := {( S , T ) : S ∈ S , ∅ = T ⊆ S } ,
and give ( S , T ) (S,T) ( S , T ) value w ( T ) w(T) w ( T ) . Since ∣ S ∣ ≤ d |S| \le d ∣ S ∣ ≤ d ,
∣ P ∣ ≤ ( 2 d − 1 ) ∣ S ∣ . |\mathcal{P}| \le(2^d-1)|\mathcal{S}|. ∣ P ∣ ≤ ( 2 d − 1 ) ∣ S ∣.
Call a collection of at most k k k pairs from P \mathcal{P} P feasible if their second components are pairwise disjoint, and let O P T p a c k ( I ) \mathrm{OPT}_{\mathrm{pack}}(I) OPT pack ( I ) be the maximum total value of a feasible collection.
We claim that
O P T c o v ( I ) = O P T p a c k ( I ) . \mathrm{OPT}_{\mathrm{cov}}(I) = \mathrm{OPT}_{\mathrm{pack}}(I). OPT cov ( I ) = OPT pack ( I ) .
Indeed, order any coverage solution S 1 , … , S q S_1,\ldots,S_q S 1 , … , S q , where q ≤ k q \le k q ≤ k , and set
T i : = S i ∖ ⋃ j < i S j . T_i := S_i \setminus\bigcup_{j<i} S_j. T i := S i ∖ j < i ⋃ S j .
After discarding the empty T i T_i T i , the resulting pairs ( S i , T i ) (S_i,T_i) ( S i , T i ) are feasible and have total value exactly w ( ⋃ i = 1 q S i ) w\left(\bigcup_{i=1}^q S_i\right) w ( ⋃ i = 1 q S i ) . This proves O P T c o v ( I ) ≤ O P T p a c k ( I ) \mathrm{OPT}_{\mathrm{cov}}(I) \le\mathrm{OPT}_{\mathrm{pack}}(I) OPT cov ( I ) ≤ OPT pack ( I ) . Conversely, from any feasible pairs ( S 1 , T 1 ) , … , ( S q , T q ) (S_1,T_1),\ldots,(S_q,T_q) ( S 1 , T 1 ) , … , ( S q , T q ) , select the distinct sets among S 1 , … , S q S_1,\ldots,S_q S 1 , … , S q . There are at most q ≤ k q \le k q ≤ k of them, and they cover ⋃ i T i \bigcup_i T_i ⋃ i T i . Positivity of the weights and pairwise disjointness give
w ( ⋃ i = 1 q S i ) ≥ w ( ⋃ i = 1 q T i ) = ∑ i = 1 q w ( T i ) , w\left(\bigcup_{i=1}^q S_i\right) \ge w\left(\bigcup_{i=1}^q T_i\right) = \sum_{i=1}^q w(T_i), w ( i = 1 ⋃ q S i ) ≥ w ( i = 1 ⋃ q T i ) = i = 1 ∑ q w ( T i ) ,
which proves the reverse inequality. This conversion also recovers a coverage solution from feasible pairs in polynomial time.
Color coding and the dynamic program. A coloring is a function h : U → [ p ] h: U \to[p] h : U → [ p ] ; we say that h h h is good for X ⊆ U X \subseteq U X ⊆ U if it assigns distinct colors to distinct elements of X X X . For a fixed set X X X of size s ≤ p s \le p s ≤ p , a uniformly random coloring is good for X X X with probability
p ! ( p − s ) ! p s ≥ p ! p p ≥ e − p . \frac{p!}{(p-s)!p^s} \ge\frac{p!}{p^p} \ge e^{-p}. ( p − s )! p s p ! ≥ p p p ! ≥ e − p .
We will derandomize this step after describing the algorithm for one coloring.
Fix h h h and retain the pairs whose second components are colorful:
P h : = { ( S , T ) ∈ P : h ( u ) ≠ h ( v ) for all distinct u , v ∈ T } . \mathcal{P}_h := \{(S,T) \in\mathcal{P} : h(u) \ne h(v)\text{ for all distinct }u,v \in T\}. P h := {( S , T ) ∈ P : h ( u ) = h ( v ) for all distinct u , v ∈ T } .
Enumerate them as ( S 1 , T 1 ) , … , ( S r , T r ) (S_1,T_1),\ldots,(S_r,T_r) ( S 1 , T 1 ) , … , ( S r , T r ) and write
C ℓ : = { h ( u ) : u ∈ T ℓ } ⊆ [ p ] ( ℓ ∈ [ r ] ) . C_\ell:= \{h(u):u \in T_\ell\} \subseteq[p]\qquad(\ell\in[r]). C ℓ := { h ( u ) : u ∈ T ℓ } ⊆ [ p ] ( ℓ ∈ [ r ]) .
For ℓ ∈ { 0 , … , r } \ell\in\{0,\ldots,r\} ℓ ∈ { 0 , … , r } , j ∈ { 0 , … , k } j \in\{0,\ldots,k\} j ∈ { 0 , … , k } , and Q ⊆ [ p ] Q \subseteq[p] Q ⊆ [ p ] , let D ℓ ( j , Q ) D_\ell(j,Q) D ℓ ( j , Q ) be the maximum of
∑ i ∈ L w ( T i ) \sum_{i\in L} w(T_i) i ∈ L ∑ w ( T i )
over all L ⊆ [ ℓ ] L \subseteq[\ell] L ⊆ [ ℓ ] such that ∣ L ∣ = j |L|=j ∣ L ∣ = j , the sets C i C_i C i for i ∈ L i \in L i ∈ L are pairwise disjoint, and their union is exactly Q Q Q . Set D ℓ ( j , Q ) = − ∞ D_\ell(j,Q)=-\infty D ℓ ( j , Q ) = − ∞ if no such L L L exists. Thus, in plain terms, ℓ \ell ℓ is the number of pairs processed, j j j is the number selected, and Q Q Q is the exact set of colors already used; the table entry records the greatest total weight possible under those conditions.
The initialization is
D 0 ( 0 , ∅ ) = 0 , D 0 ( j , Q ) = − ∞ when ( j , Q ) ≠ ( 0 , ∅ ) . D_0(0,\varnothing)=0,\qquad D_0(j,Q)=-\infty\quad\text{when }(j,Q)\ne(0,\varnothing). D 0 ( 0 , ∅ ) = 0 , D 0 ( j , Q ) = − ∞ when ( j , Q ) = ( 0 , ∅ ) .
For ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 ,
D ℓ ( j , Q ) = max { D ℓ − 1 ( j , Q ) , D ℓ − 1 ( j − 1 , Q ∖ C ℓ ) + w ( T ℓ ) } . (3) D_\ell(j,Q)=\max\{D_{\ell-1}(j,Q),D_{\ell-1}(j-1,Q\setminus C_\ell)+w(T_\ell)\}. \tag*{(3)} D ℓ ( j , Q ) = max { D ℓ − 1 ( j , Q ) , D ℓ − 1 ( j − 1 , Q ∖ C ℓ ) + w ( T ℓ )} . (3)
where the second term is interpreted as − ∞ -\infty − ∞ unless j ≥ 1 j \ge1 j ≥ 1 and C ℓ ⊆ Q C_\ell\subseteq Q C ℓ ⊆ Q .
We prove the correctness of the recurrence by induction on ℓ \ell ℓ . For the base case ℓ = 0 \ell= 0 ℓ = 0 , the empty selection is the unique selection using none of the pairs, so it gives D 0 ( 0 , ∅ ) = 0 D_0(0,\varnothing) = 0 D 0 ( 0 , ∅ ) = 0 and every other entry is − ∞ -\infty − ∞ , exactly as initialized. For the induction hypothesis, fix ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 and assume that every entry D ℓ − 1 ( j ′ , Q ′ ) D_{\ell-1}(j',Q') D ℓ − 1 ( j ′ , Q ′ ) has the meaning specified above, for all j ′ ∈ { 0 , … , k } j' \in\{0,\ldots,k\} j ′ ∈ { 0 , … , k } and Q ′ ⊆ [ p ] Q' \subseteq[p] Q ′ ⊆ [ p ] .
For the inductive step, fix j ∈ { 0 , … , k } j \in\{0,\ldots,k\} j ∈ { 0 , … , k } and Q ⊆ [ p ] Q \subseteq[p] Q ⊆ [ p ] . Any selection considered by D ℓ ( j , Q ) D_\ell(j,Q) D ℓ ( j , Q ) either omits or contains the ℓ \ell ℓ th pair. If it omits that pair, the induction hypothesis bounds its value by D ℓ − 1 ( j , Q ) D_{\ell-1}(j,Q) D ℓ − 1 ( j , Q ) . If it contains that pair, then j ≥ 1 j \ge1 j ≥ 1 and C ℓ ⊆ Q C_\ell\subseteq Q C ℓ ⊆ Q ; removing the pair leaves j − 1 j-1 j − 1 pairs whose color sets have union Q ∖ C ℓ Q \setminus C_\ell Q ∖ C ℓ , so the induction hypothesis bounds the remaining value by D ℓ − 1 ( j − 1 , Q ∖ C ℓ ) D_{\ell-1}(j-1,Q \setminus C_\ell) D ℓ − 1 ( j − 1 , Q ∖ C ℓ ) . This gives the two upper bounds on the right-hand side of (3) . Conversely, a selection attaining the first term remains feasible after the ℓ \ell ℓ th pair is processed. When the second term is available, a selection attaining it uses exactly the colors Q ∖ C ℓ Q \setminus C_\ell Q ∖ C ℓ , which are disjoint from C ℓ C_\ell C ℓ ; adding the ℓ \ell ℓ th pair is therefore feasible, gives union Q Q Q , and adds w ( T ℓ ) w(T_\ell) w ( T ℓ ) to its value. Thus the recurrence computes D ℓ ( j , Q ) D_\ell(j,Q) D ℓ ( j , Q ) . Since j j j and Q Q Q were arbitrary, the inductive step holds for every entry in layer ℓ \ell ℓ , completing the induction. Recording which term is chosen in every finite entry permits the selected pairs to be recovered by traceback.
For the fixed coloring h h h , put
V h : = max 0 ≤ j ≤ k Q ⊆ [ p ] D r ( j , Q ) . V_h := \max_{\substack{0 \le j \le k\\ Q \subseteq[p]}} D_r(j,Q). V h := 0 ≤ j ≤ k Q ⊆ [ p ] max D r ( j , Q ) .
Every selection counted by the table yields feasible pairs: if an element belonged to two selected second components, its color would belong to both of their color sets, contradicting their disjointness. Hence V h ≤ OPT p a c k ( I ) V_h \le\operatorname{OPT}_{\mathrm{pack}}(I) V h ≤ OPT pack ( I ) for every h h h .
For the reverse inequality, fix optimum feasible pairs ( S 1 ∗ , T 1 ∗ ) , … , ( S q ∗ , T q ∗ ) (S_1^*,T_1^*),\ldots,(S_q^*,T_q^*) ( S 1 ∗ , T 1 ∗ ) , … , ( S q ∗ , T q ∗ ) and let X : = ⋃ i = 1 q T i ∗ X := \bigcup_{i=1}^q T_i^* X := ⋃ i = 1 q T i ∗ . If h h h is good for X X X , then every optimum pair belongs to P h \mathcal{P}_h P h , and their color sets are pairwise disjoint. The dynamic program can therefore select all these pairs, giving V h ≥ OPT p a c k ( I ) V_h \ge\operatorname{OPT}_{\mathrm{pack}}(I) V h ≥ OPT pack ( I ) . Consequently,
V h = OPT p a c k ( I ) V_h = \operatorname{OPT}_{\mathrm{pack}}(I) V h = OPT pack ( I )
whenever h h h is good for the elements used by an optimum solution.
Derandomization and running time. By the standard color-coding derandomization, construct a p p p -perfect hash family H \mathcal{H} H , meaning that for every X ⊆ U X \subseteq U X ⊆ U with ∣ X ∣ ≤ p |X| \le p ∣ X ∣ ≤ p some h ∈ H h \in\mathcal{H} h ∈ H is good for X X X . Such a family has 2 O ( p ) log ( 2 + ∣ U ∣ ) 2^{O(p)} \log(2+|U|) 2 O ( p ) log ( 2 + ∣ U ∣ ) functions from U U U to [ p ] [p] [ p ] and can be constructed in 2 O ( p ) N O ( 1 ) 2^{O(p)}N^{O(1)} 2 O ( p ) N O ( 1 ) time [1 ] . Since an optimum collection uses at most k d = p kd = p k d = p elements, some h ∈ H h \in\mathcal{H} h ∈ H is good for those elements. Hence max h ∈ H V h = OPT p a c k ( I ) \max_{h \in\mathcal{H}} V_h = \operatorname{OPT}_{\mathrm{pack}}(I) max h ∈ H V h = OPT pack ( I ) , and running the dynamic program for every h ∈ H h \in\mathcal{H} h ∈ H gives a deterministic exact algorithm.
For a fixed coloring, the table has at most ( ∣ P ∣ + 1 ) ( k + 1 ) 2 p (|\mathcal{P}|+1)(k+1)2^p ( ∣ P ∣ + 1 ) ( k + 1 ) 2 p entries. Representing Q Q Q and C ℓ C_\ell C ℓ as p p p -bit vectors makes the subset test and set difference in (3) take O ( p ) O(p) O ( p ) time, so one coloring is processed in
O ( ∣ P ∣ ( k + 1 ) 2 p p ) O(|\mathcal{P}|(k+1)2^p p) O ( ∣ P ∣ ( k + 1 ) 2 p p )
time. Using ∣ P ∣ ≤ ( 2 d − 1 ) ∣ S ∣ |\mathcal{P}| \le(2^d-1)|\mathcal{S}| ∣ P ∣ ≤ ( 2 d − 1 ) ∣ S ∣ , p = k d p=kd p = k d , and ∣ H ∣ = 2 O ( p ) log ( 2 + ∣ U ∣ ) |\mathcal{H}| = 2^{O(p)}\log(2+|U|) ∣ H ∣ = 2 O ( p ) log ( 2 + ∣ U ∣ ) , the total running time is 2 O ( k d ) N O ( 1 ) 2^{O(kd)}N^{O(1)} 2 O ( k d ) N O ( 1 ) . Every finite table entry is a sum of at most k d kd k d input element weights, so exact additions and comparisons of the binary rational values also take polynomial time.
Finally, choose a coloring attaining the maximum and perform the traceback. This yields feasible pairs of value OPT p a c k ( I ) \operatorname{OPT}_{\mathrm{pack}}(I) OPT pack ( I ) . Selecting their distinct first components produces, by the equivalence above, an optimum coverage solution and hence an optimum solution to weighted Min-UnCoverage.