EUVIMEDEUVIMED entdecken
Crossref

Exact Algorithms for Distance to Unique Vertex Cover

Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos, Michal Opler, Manolis Vasilakis

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (17) · 14217-14224

DOI: 10.1609/aaai.v40i17.38435 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Foivos Fioravantes und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In their AAAI 2024 paper, Horiyama et al. studied the problem of generating graph instances that possess a unique minimum vertex cover under specific conditions. Their approach involved pre-assigning certain vertices to be part of the solution or excluding them from it. Notably, for the Vertex Cover problem, pre-assigning a vertex is equivalent to removing it from the graph. Horiyama et al. focused on maintaining the size of the minimum vertex cover after these modifications. In this work, we extend their study by relaxing this constraint: our goal is to ensure a unique minimum vertex cover, even if the removal of a vertex may not incur a decrease on the size of said cover. Surprisingly, our relaxation introduces significant theoretical challenges. We observe that the problem is Σ²_P-complete, and remains so even for planar graphs of maximum degree 5. Nevertheless, we provide a linear time algorithm for trees, which is then further leveraged to show that MU-VC is in FPT when parameterized by the combination of treewidth and maximum degree. Finally, we show that MU-VC is in XP when parameterized by clique-width while it is fixed-parameter tractable (FPT) if we add the size of the solution as part of the parameter.

Zitieren

APA

Fioravantes, F., Knop, D., Melissinos, N., Opler, M., & Vasilakis, M. (2026). Exact Algorithms for Distance to Unique Vertex Cover. Proceedings of the AAAI Conference on Artificial Intelligence, 40(17), 14217-14224. https://doi.org/10.1609/aaai.v40i17.38435

Vancouver

Fioravantes F, Knop D, Melissinos N, Opler M, Vasilakis M. Exact Algorithms for Distance to Unique Vertex Cover. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(17):14217-14224. doi:10.1609/aaai.v40i17.38435

BibTeX
@article{Fioravantes2026,
  author = {Fioravantes, Foivos and Knop, Dušan and Melissinos, Nikolaos and Opler, Michal and Vasilakis, Manolis},
  title = {Exact Algorithms for Distance to Unique Vertex Cover},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {17},
  pages = {14217--14224},
  doi = {10.1609/aaai.v40i17.38435}
}
Kostenlos starten →