ML Anthology

Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs

Shinwoo An, Yeonsu Chang, Kyungjin Cho, O-joung Kwon, Myounghwan Lee, Eunjin Oh, Hyeonjun Shin
AAAI 2025 pp. 26886-26894
doi:10.1609/AAAI.V39I25.34893 /aaai/2025/an2025aaai-pre/

Abstract

Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph G, to find a minimum set S of vertices in G such that there is a unique minimum vertex cover of G containing S. We show that PAU-VC is fixed parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in polynomial time on split graphs and unit interval graphs.

PDF AAAI Semantic Scholar

Cite

Text

An et al. "Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs." AAAI Conference on Artificial Intelligence, 2025. doi:10.1609/AAAI.V39I25.34893

Markdown

[An et al. "Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs." AAAI Conference on Artificial Intelligence, 2025.](https://mlanthology.org/aaai/2025/an2025aaai-pre/) doi:10.1609/AAAI.V39I25.34893

BibTeX

@inproceedings{an2025aaai-pre,
  title     = {{Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs}},
  author    = {An, Shinwoo and Chang, Yeonsu and Cho, Kyungjin and Kwon, O-joung and Lee, Myounghwan and Oh, Eunjin and Shin, Hyeonjun},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2025},
  pages     = {26886-26894},
  doi       = {10.1609/AAAI.V39I25.34893},
  url       = {https://mlanthology.org/aaai/2025/an2025aaai-pre/}
}