On Computing a Maximum Minimal Set Cover: Exact Algorithms and (S)ETH-Based Lower Bounds
DOI:
https://doi.org/10.5753/reic.2026.8447Keywords:
Set Cover, Maximum Minimal Set Cover, Exact Exponential Algorithms, Vertex Cover, ETH, SETHAbstract
Maximum Minimal Set Cover is the max-min variant of the classical Set Cover problem, whose goal is to find a minimal set cover of maximum cardinality. This problem generalizes both Max Min Vertex Cover and Upper Domination. Although (Maximum Minimal) Set Cover and (Maximum Minimal) Hitting Set are equivalent under specific parameterizations, differences arise when the size of the universe, denoted by n, is considered. Maximum Minimal Hitting Set trivially admits an O∗(2n)-time algorithm, whereas an exhaustive approach for Maximum Minimal Set Cover requires O∗(2m) time, where m is the number of sets. Since m can be much larger than n, we investigate exact exponential algorithms parameterized by n for the problem. We show that Maximum Minimal Set Cover can be solved in O∗(2n) time, and that a subexponential-time algorithm running in O∗(2o(n)) would imply that ETH fails. Finally, we generalize these results by presenting an O∗(2k)-time algorithm, where k is the size of a minimum vertex cover of the incidence graph, together with a tighter lower bound based on SETH.
Downloads
References
AbouEisha, H., Hussain, S., Lozin, V., Monnot, J., and Ries, B. (2014). A dichotomy for upper domination in monogenic classes. In International Conference on Combinatorial Optimization and Applications, pages 258–267. Springer. DOI: 10.1007/978-3-319-12691-3_20.
Araújo, J., Bougeret, M., Campos, V. A., and Sau, I. (2023). Parameterized complexity of computing maximum minimal blocking and hitting sets. Algorithmica, 85(2):444–491. DOI: 10.1007/s00453-022-01036-5.
Arkin, E. M., Bender, M. A., Mitchell, J. S., and Skiena, S. S. (2003). The lazy bureaucrat scheduling problem. Information and Computation, 184(1):129–146. DOI: 10.1016/S0890-5401(03)00060-9.
Bazgan, C., Brankovic, L., Casel, K., Fernau, H., Jansen, K., Klein, K.-M., Lampis, M., Liedloff, M., Monnot, J., and Paschos, V. T. (2018). The many facets of upper domination. Theoretical Computer Science, 717:2–25. DOI: 10.1016/j.tcs.2017.05.042.
Bender, M. A., Clifford, R., and Tsichlas, K. (2008). Scheduling algorithms for procrastinators. Journal of Scheduling, 11(2):95–104. DOI: 10.1007/s10951-007-0038-4.
Boria, N., Della Croce, F., and Paschos, V. T. (2015). On the max min vertex cover problem. Discrete Applied Mathematics, 196:62–71. DOI: 10.1016/j.dam.2014.06.001.
Bourgeois, N., Della Croce, F., Escoffier, B., and Paschos, V. T. (2013). Fast algorithms for min independent dominating set. Discrete Applied Mathematics, 161(4-5):558–572. DOI: 10.1016/j.dam.2012.01.003.
Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., and Wahlström, M. (2016). On problems as hard as CNF-SAT. ACM Transactions on Algorithms (TALG), 12(3):1–24. DOI: 10.1145/2925416.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms. Springer.
Fomin, F. V., Grandoni, F., Pyatkin, A. V., and Stepanov, A. A. (2008). Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Transactions on Algorithms (TALG), 5(1):1–17. DOI: 10.1145/1435375.1435384.
Fomin, F. V., Kratsch, D., and Woeginger, G. J. (2004). Exact (exponential) algorithms for the dominating set problem. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 245–256. Springer. DOI: 10.1007/978-3-540-30559-0_21.
Halldórsson, M. M. (1993). Approximating the minimum maximal independence number. Information Processing Letters, 46(4):169–172. DOI: 10.1016/0020-0190(93)90022-2.
Hurink, J. L. and Nieberg, T. (2008). Approximating minimum independent dominating sets in wireless networks. Information Processing Letters, 109(2):155–160. DOI: 10.1016/j.ipl.2008.09.021.
Van Rooij, J. M. and Bodlaender, H. L. (2011). Exact algorithms for dominating set. Discrete Applied Mathematics, 159(17):2147–2164. DOI: 10.1016/j.dam.2011.07.001.
Xiao, M. and Nagamochi, H. (2017). Exact algorithms for maximum independent set. Information and Computation, 255:126–146. DOI: 10.1016/j.ic.2017.06.001.
Zehavi, M. (2017). Maximum minimal vertex cover parameterized by vertex cover. SIAM Journal on Discrete Mathematics, 31(4):2440–2456. DOI: 10.1137/16M109017X.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 The authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
