Sobre a Computação de um Set Cover Minimal Máximo: Algoritmos Exatos e Limites Inferiores baseados em (S)ETH
DOI:
https://doi.org/10.5753/reic.2026.8447Keywords:
Set Cover, Maximum Minimal Set Cover, Algoritmos Exatos Exponenciais, Vertex Cover, ETH, SETHAbstract
Maximum Minimal Set Cover é a variante max-min do clássico problema Set Cover, cujo objetivo é encontrar um set cover minimal de cardinalidade máxima. Este problema generaliza Max Min Vertex Cover e Upper Domination. Embora (Maximum Minimal) Set Cover e (Maximum Minimal) Hitting Set sejam equivalentes sob certos parâmetros, diferenças surgem quando o tamanho do universo, denotado por n, é considerado. Maximum Minimal Hitting Set admite trivialmente um algoritmo em tempo O∗(2n), mas uma análise exaustiva para Maximum Minimal Set Cover demanda tempo O∗(2m), onde m é o número de conjuntos. Como m pode ser muito maior que n, investigamos algoritmos exatos exponenciais em função de n para o problema. Mostramos que Maximum Minimal Set Cover pode ser resolvido em tempo O∗(2n) e que um algoritmo subexponencial de tempo O∗(2o(n)) implicaria a falsidade da ETH. Por fim, generalizamos os resultados anteriores apresentando um algoritmo em tempo O∗ (2k), onde k é o tamanho do vertex cover mínimo do grafo de incidência, além de um limite inferior mais apertado baseado na SETH.
Descargas
Citas
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.
Descargas
Published
Cómo citar
Issue
Section
Licencia
Derechos de autor 2026 Os autores
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
