2026-09-10T09:44:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27737 2026-09-09T12:19:36Z ddc:004 open_access

On the Approximability of Parameterized Minimum Monotone Satisfying Assignment Guruswami, Venkatesan Lin, Bingkai Ren, Xuandi Zheng, Xin Parameterized approximation Minimum Monotone Satisfying Assignment Set Cover inapproximability The parameterized Minimum Monotone Satisfying Assignment (k-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most k. The MMSA hierarchy is defined by allowing a bounded number of alternations between AND and OR gates in the circuit. While the polynomial-time approximability of the MMSA hierarchy has been studied extensively, much less is known in the parameterized setting. In particular, k-MMSA₂ is the well-known k-SetCover problem, whose parameterized inapproximability lies in the polylog(n) regime. In contrast, k-MMSA₄ captures k-MinLabel, for which known lower bounds give poly(n) inapproximability. Sandwiched by k-MMSA₂ and k-MMSA₄, the inapproximability of k-MMSA₃ remained comparatively unexplored. In this paper, we give an FPT-time O(2^k log n)-approximation algorithm for k-MMSA₃, suggesting that in the fixed-parameter regime, the third level of MMSA remains surprisingly close to the second level. Complementing this algorithm, we also give an FPT-time gap-preserving reduction from k-MMSA₃ to k-MMSA₂. Thus, stronger inapproximability for k-MMSA₃ would imply new hardness for k-MMSA₂, potentially offering a route around the current barriers for the latter problem. Revisiting Marx’s reduction from k-MMSA_t to gap k-MMSA_{t+2}, we also show that k-MMSA₄ admits no n^o(1)-factor FPT approximation unless W[2]=FPT, and no n^O(1/k)-factor approximation running in n^o(k) time under ETH. These results separate the parameterized approximability behavior of the third and fourth levels and clarify where stronger inapproximability enters the k-MMSA hierarchy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan Guruswami and Bingkai Lin and Xuandi Ren and Xin Zheng 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.20 urn:nbn:de:0030-drops-277379 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode