Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
<|reference_start|>Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs: 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 linear time on split graphs and unit interval graphs.<|reference_end|>
@article{an2024pre-assignment,
    title={Pre-assignment problem for unique minimum vertex cover on bounded
  clique-width graphs},
    author={Shinwoo An, Yeonsu Chang, Kyungjin Cho, O-joung Kwon, Myounghwan Lee,
  Eunjin Oh, Hyeonjun Shin},
    journal={arXiv preprint arXiv:2408.09591},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.09591},
    primaryClass={cs.DS}
}