Exact Algorithms for Distance to Unique Vertex Cover
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913683497549824 |
|---|---|
| author | Fioravantes, Foivos Knop, Dušan Melissinos, Nikolaos Opler, Michal Vasilakis, Manolis |
| author_facet | Fioravantes, Foivos Knop, Dušan Melissinos, Nikolaos Opler, Michal Vasilakis, Manolis |
| contents | Horiyama et al. (AAAI 2024) 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 \textsc{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 $Σ^2_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 \textsf{FPT} when parameterized by the combination of treewidth and maximum degree. Finally, we show that MU-VC is in \textsf{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05059 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact Algorithms for Distance to Unique Vertex Cover Fioravantes, Foivos Knop, Dušan Melissinos, Nikolaos Opler, Michal Vasilakis, Manolis Data Structures and Algorithms Computational Complexity Horiyama et al. (AAAI 2024) 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 \textsc{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 $Σ^2_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 \textsf{FPT} when parameterized by the combination of treewidth and maximum degree. Finally, we show that MU-VC is in \textsf{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. |
| title | Exact Algorithms for Distance to Unique Vertex Cover |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2502.05059 |