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

Authors

  • Shinwoo An Pohang University of Science and Technology
  • Yeonsu Chang Hanyang University
  • Kyungjin Cho Pohang University of Science and Technology
  • O-Joung Kwon Hanyang University Institute for Basic Science
  • Myounghwan Lee Hanyang University
  • Eunjin Oh Pohang University of Science and Technology
  • Hyeonjun Shin Pohang University of Science and Technology

DOI:

https://doi.org/10.1609/aaai.v39i25.34893

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.
AAAI-25 / IAAI-25 / EAAI-25 Proceedings Cover

Downloads

Published

2025-04-11

How to Cite

An, S., Chang, Y., Cho, K., Kwon, O.-J., Lee, M., Oh, E., & Shin, H. (2025). Pre-Assignment Problem for Unique Minimum Vertex Cover on Bounded Clique-Width Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 39(25), 26886-26894. https://doi.org/10.1609/aaai.v39i25.34893

Issue

Vol. 39 No. 25: AAAI-25 Technical Tracks 25

Section

AAAI Technical Track on Search and Optimization